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 action predicate. The final predicate is true when the goal is reached, and false otherwise. The 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.

GitHub: https://github.com/kit1980/sdymchenko-com/blob/master/pentagonal-peg-solitare-picat/PentagonalPegSolitare.pi

At the begging of the program there is a bunch of move predicate facts that define lines of neighboring holes on the board. The 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 1^st and 2^nd 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.

The 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. Use of foreach loop and if-then-else construct if very similar to many modern programming languages.

The 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/.