Solving Pentagonal Peg Solitaire puzzle with Picat
Recently I saw a blog post by Imre Pólik with a description of a pentagonal peg solitaire puzzle and a solution using integer linear programming and SAS/OR.
In this puzzle all holes A–P, except the center hole H, initially have pegs. A peg can jump over nearby peg to the next empty hole, and the peg that was jumped over is eliminated (somewhat similar to checkers). The goal is to eliminate all pegs except one, leaving the last one in the center.
As soon as I saw the puzzle I realized that it is very suitable for solving as a planning problem in Picat.
Picat (http://picat-lang.org/) is a new multiparadigm logic-based programming language. In many ways, Picat is similar to Prolog, especially B-Prolog, but it has some features of modern functional and imperative languages: pattern-matching instead of unification, destructive assignment, loops… In this blog post I use the currently latest version Picat 0.9.
Picat has a
planner module for declarative solving of planning problems.
I have written a blog post with a description and examples of using the
planner module: Artificial intelligence planning with Picat.
Basically, to solve a planning problem with Picat one needs to define a
final predicate and an
final predicate is true when the goal is reached, and false otherwise.
action predicate defines all possible actions and how they transform the problem state.
Here is my complete Picat program to solve the puzzle:
import planner. index (+,-,-) (-,-,+) move(h, m, o). move(h, i, k). move(h, e, b). move(h, f, c). move(h, j, l). move(m, i, d). move(m, j, g). move(i, m, p). move(i, e, a). move(e, i, n). move(e, f, g). move(f, e, d). move(f, j, p). move(j, m, n). move(j, f, a). move(n, k, d). move(n, o, p). move(d, b, a). move(a, c, g). move(g, l, p). final(Pegs) => foreach(Char in Pegs.keys()) if Char == h then Pegs.get(Char) == 1 else Pegs.get(Char) = 0 end end. action(Pegs, NewPegs, Action, Cost) ?=> member(End, Pegs.keys()), Pegs.get(End) == 0, ( move(Begin, Middle, End) ; move(End, Middle, Begin) ), Pegs.get(Begin) == 1, Pegs.get(Middle) == 1, NewPegs = copy_term(Pegs), NewPegs.put(Begin, 0), NewPegs.put(Middle, 0), NewPegs.put(End, 1), Action = [Begin, ' ', Middle, ' ', End], Cost = 1. main => Pegs = new_map(), foreach(I in 0'a..0'p) Char = chr(I), if Char == h then Pegs.put(Char, 0) else Pegs.put(Char, 1) end end, plan(Pegs, Plan), foreach(Move in Plan) println(Move) end.
At the begging of the program there is a bunch of
move predicate facts that define lines of neighboring holes on the board.
index declaration tells how the facts can be used. We want to be able to make moves in both directions;
so either is the first parameter is input, and the second and third are output,
or the third is input, and the 1st and 2nd are output.
Note that we are using low-case letters for the holes names: this way we don't need to put them in quotes. Capital case letters represent variables in Picat (as in Prolog), so we would have to put them in quotes to represent literal symbols.
final predicate takes
Pegs – a hash map where the keys are letters a–p and the values are 0 (there is no peg in this hole) and 1 (there is a peg) – as a parameter.
The predicate succeeds if all holes except the center one are empty.
foreach loop and
if-then-else construct if very similar to many modern programming languages.
action predicate defines the only available type of actions in the puzzle.
The first parameter
Pegs – the same as in
final – is an input parameter, the other three are output parameters.
Here is the
action predicate with every line commented:
action(Pegs, NewPegs, Action, Cost) ?=> member(End, Pegs.keys()), % choose a hole, call it End Pegs.get(End) == 0, % End must be empty ( move(Begin, Middle, End) ; move(End, Middle, Begin) ), % choose a move Begin -> Middle -> End (2 possible directions) Pegs.get(Begin) == 1, Pegs.get(Middle) == 1, % Begin and Middle must be non-empty NewPegs = copy_term(Pegs), % NewPegs is a copy of Pegs NewPegs.put(Begin, 0), % Begin is empty in NewPegs - the peg has moved to End NewPegs.put(Middle, 0), % Middle is empty - the peg has been eliminated NewPegs.put(End, 1), % End is not empty Acion = [Begin, ' ', Middle, ' ', End], % string description of the action Cost = 1. % cost doesn't matter for the problem
Note that the
action predicate is non-deterministic (which is denoted by
Picat will backtrack and choose a different
End hole until the whole plan succeeds or all possibilities are exhausted.
main just constructs the initial
Pegs hash table, calls the
plan predicate from the
planner module, and outputs the result.
The whole program is very declarative: we only described initial state, possible actions, and the goal.
The program completes instantaneously (
time reports about 0.01s on my laptop) with and outputs this plan:
o m h d i m p m i g j m h m o n o p e i n a c g n k d g f e d e f p l g g f e b e h
For more info about the
planner module see "Planning Problems" at http://picat-lang.org/projects.html and
Zhou, Neng-Fa, and Hakan Kjellerstrand. "Solving several planning problems with Picat." Control and Decision Conference (2014 CCDC), The 26th Chinese. IEEE, 2014.
For more info about Picat in general see the documentation in the distribution and http://www.hakank.org/picat/.