peg-solitaire-solver

#!/usr/bin/perl

# This program solves the (English) peg solitaire
# Perl translate from Go code (see __END__)
# Translator: Trizen
# Date: 27 February 2012

use 5.010;
use strict;
use warnings;

use utf8;
binmode *STDOUT, ':encoding(utf-8)';

my $N = 11 + 1;    # length of a board row (+1 for \n)

# The board must be surrounded by 2 illegal fields
# in each direction so that move() doesn't need to
# check the board boundaries. Periods represent
# illegal fields, ● are pegs, and ○ are holes.
my @board = unpack(
    'C*',
    '...........
...........
....●●●....
....●●●....
..●●●●●●●..
..●●●○●●●..
..●●●●●●●..
....●●●....
....●●●....
...........
...........
'
                  );

# center is the position of the center hole if
# there is a single one; otherwise it is -1.
my $center;

{
    my $n = 0;
    for (my $i = 0 ; $i <= $#board ; ++$i) {
        if (chr $board[$i] eq '○') {
            $center = $i;
            $n++;
            last;
        }
    }

    if ($n != 1) {
        $center = -1;    # no single hole
    }
}

my $moves;               # number of times move is called

# move tests if there is a peg at position pos that
# can jump over another peg in direction dir. If the
# move is valid, it is executed and move returns true.
# Otherwise, move returns false.
sub move {
    my ($pos, $dir) = @_;
    ++$moves;
    if (chr $board[$pos] eq '●' and chr $board[$pos + $dir] eq '●' and chr $board[$pos + 2 * $dir] eq '○') {
        $board[$pos]            = ord '○';
        $board[$pos + $dir]     = ord '○';
        $board[$pos + 2 * $dir] = ord '●';
        return 1;
    }
    return 0;
}

# unmove reverts a previously executed valid move.
sub unmove {
    my ($pos, $dir) = @_;
    $board[$pos]            = ord '●';
    $board[$pos + $dir]     = ord '●';
    $board[$pos + 2 * $dir] = ord '○';
    return 1;
}

# solve tries to find a sequence of moves such that
# there is only one peg left at the end; if center is
# >= 0, that last peg must be in the center position.
# If a solution is found, solve prints the board after
# each move in a backward fashion (i.e., the last
# board position is printed first, all the way back to
# the starting board position).
sub solve {
    my ($last, $n);

    foreach my $pos (0 .. $#board) {

        # try each board position
        if (chr $board[$pos] eq '●') {

            # found a peg
            foreach my $dir (-1, -$N, +1, +$N) {

                # try each direction
                if (move($pos, $dir)) {

                    # a valid move was found and executed,
                    # see if this new board has a solution
                    if (solve()) {
                        unmove($pos, $dir);
                        say map { chr } @board;
                        return 1;
                    }
                    unmove($pos, $dir);
                }
            }
            $last = $pos;
            $n++;
        }
    }

    # tried each possible move
    if ($n == 1 && ($center < 0 || $last == $center)) {

        # there's only one peg left
        say map { chr } @board;
        return 1;
    }

    # no solution found for this board
    return 0;
}

if (!solve()) {
    say "no solution found";
}

say "$moves moves tried";

__END__
// This program solves the (English) peg solitaire
// board game.  See also:
//   https://en.wikipedia.org/wiki/Peg_solitaire

package main

import "fmt"

const N = 11 + 1 // length of a board row (+1 for \n)

// The board must be surrounded by 2 illegal fields
// in each direction so that move() doesn't need to
// check the board boundaries. Periods represent
// illegal fields, ● are pegs, and ○ are holes.
var board = []int(
    `...........
...........
....●●●....
....●●●....
..●●●●●●●..
..●●●○●●●..
..●●●●●●●..
....●●●....
....●●●....
...........
...........
`)


// center is the position of the center hole if
// there is a single one; otherwise it is -1.
var center int

func init() {
    n := 0
    for pos, field := range board {
        if field == '○' {
            center = pos
            n++
        }
    }
    if n != 1 {
        center = -1 // no single hole
    }
}


var moves int // number of times move is called

// move tests if there is a peg at position pos that
// can jump over another peg in direction dir. If the
// move is valid, it is executed and move returns true.
// Otherwise, move returns false.
func move(pos, dir int) bool {
    moves++
    if board[pos] == '●' && board[pos+dir] == '●' && board[pos+2*dir] == '○' {
        board[pos] = '○'
        board[pos+dir] = '○'
        board[pos+2*dir] = '●'
        return true
    }
    return false
}


// unmove reverts a previously executed valid move.
func unmove(pos, dir int) {
    board[pos] = '●'
    board[pos+dir] = '●'
    board[pos+2*dir] = '○'
}


// solve tries to find a sequence of moves such that
// there is only one peg left at the end; if center is
// >= 0, that last peg must be in the center position.
// If a solution is found, solve prints the board after
// each move in a backward fashion (i.e., the last
// board position is printed first, all the way back to
// the starting board position).
func solve() bool {
    var last, n int
    for pos, field := range board {
        // try each board position
        if field == '●' {
            // found a peg
            for _, dir := range [...]int{-1, -N, +1, +N} {
                // try each direction
                if move(pos, dir) {
                    // a valid move was found and executed,
                    // see if this new board has a solution
                    if solve() {
                        unmove(pos, dir)
                        println(string(board))
                        return true
                    }
                    unmove(pos, dir)
                }
            }
            last = pos
            n++
        }
    }
    // tried each possible move
    if n == 1 && (center < 0 || last == center) {
        // there's only one peg left
        println(string(board))
        return true
    }
    // no solution found for this board
    return false
}


func main() {
    if !solve() {
        fmt.Println("no solution found")
    }
    fmt.Println(moves, "moves tried")
}