# 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.
```

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

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.