Lunar Lockout is similar to a standard

sliding puzzle, but with more degrees of freedom. Here's a way to solve Lunar Lockout puzzles using the

answer set solver

clingo. We'll demonstrate the approach on "Advanced Solitaire Puzzle 1" from the link above.

This solution uses a main file to specify how the pieces move (

lunar.lp).

% piece(P). P is a piece.
% piece(T,P,X,Y). piece P is at (X,Y) at the end of turn T
% turn(T). T is a turn.
% reachable(T,P,X,Y). It's possible for piece P to be at (X,Y) at the end of turn T
% move(T,P). piece P moves on turn T.
% move(T,P,X,Y). Piece P moves to (X,Y) on turn T.
% direction(D). D is a direction
turn(0..maxturns).
direction(up;down;left;right).
piece(P) :- init(P,X,Y).
piece(T,P) :- piece(T,P,X,Y).
piece(0,P,X,Y) :- init(P,X,Y).
% Four different types of sub-moves
% 1. slide down
reachable(T+1,P,X,YQ+1) :-
reachable(T+1,P,X,Y),
piece(T,X,YQ), not piece(T,P,X,YQ),
[ piece(T,X,Z) : YQ < Z : Z < Y : coordinate(Z) ] 0,
coordinate(X;Y;YQ;YR),
turn(T;T+1),
piece(P),
YQ+1 < Y.
% 2. slide up
reachable(T+1,P,X,YQ-1) :-
reachable(T+1,P,X,Y),
piece(T,X,YQ), not piece(T,P,X,YQ),
[ piece(T,X,Z) : Y < Z : Z < YQ : coordinate(Z) ] 0,
coordinate(X;Y;YQ;YR),
turn(T;T+1),
piece(P),
Y < YQ-1.
% 3. slide right
reachable(T+1,P,XQ-1,Y) :-
reachable(T+1,P,X,Y),
piece(T,XQ,Y), not piece(T,P,XQ,Y),
[ piece(T,Z,Y) : X < Z : Z < XQ : coordinate(Z) ] 0,
coordinate(X;Y;XQ;XR),
piece(P;R),
turn(T;T+1),
X < XQ-1.
% 4. slide left
reachable(T+1,P,XQ+1,Y) :-
reachable(T+1,P,X,Y),
piece(T,XQ,Y), not piece(T,P,XQ,Y),
[ piece(T,Z,Y) : XQ < Z : Z < X : coordinate(Z) ] 0,
coordinate(X;Y;XQ;XR),
piece(P),
turn(T;T+1),
XQ+1 < X.
move(T,P) :- move(T,P,X,Y).
piece(T,X,Y) :- piece(T,P,X,Y).
% One move must be selected at each turn.
1 { move(T,P,X,Y) : piece(P) : coordinate(X;Y) } 1 :-
turn(T),
T > 0.
% A move must be to a reachable location.
:- move(T,P,X,Y), not reachable(T,P,X,Y).
% Can't leave a piece in the same place
:- move(T+1,P,X,Y), piece(T,P,X,Y), turn(T;T+1).
% Ships disappear when they reach the goal.
shipdisappears(T,P) :- move(T,P,X,Y), ship(P), goal(X,Y).
% If a piece is moved to (X,Y), and it's not a ship that disappears on
% that move, then it ends up at (X,Y) a the end of that turn.
piece(T,P,X,Y) :- move(T,P,X,Y), not shipdisappears(T,P).
% Anything that didn't move on a particular turn is in the same place
% at the beginning of the next turn.
piece(T+1,P,X,Y) :-
not move(T+1,P),
piece(T,P,X,Y),
piece(P),
coordinate(X;Y),
turn(T;T+1).
% A piece can stay in the same location to the next turn.
reachable(T+1,P,X,Y) :- piece(T,P,X,Y), turn(T;T+1).
% The puzzle is solved when every ship has disappeared (by reaching
% the goal cell)
notsolved(T) :- piece(T,P), ship(P).
solved :- not notsolved(T), turn(T).
:- not solved.
#hide.
#show move/4.

There is also a file to specify the initial location of the pieces for a particular puzzle (

advsolitaire1.lp).

coordinate(-3..3).
ship(x).
goal(0,0).
init(x,-1,3).
init(1,1,1).
init(2,-1,0).
init(3,2,-1).
init(4,-1,-3).
init(5,0,-3).

Running the solver:

$ clingo -c maxturns=2 advsolitaire1.lp lunar.lp
Answer: 1
move(1,4,0,-2) move(2,x,0,0)
SATISFIABLE

According to the solver, the puzzle can be solved in two moves, as follows:

- move piece 4 to (0,-2)

- move piece x to (0,0).

In our coordinate system, the goal is in the center of the grid at (0,0), so the first move locates piece 4 two squares below the goal, and the second move takes the ship home. I challenge anyone to solve "

advanced solitaire #30" in the minimum number of moves (18) without using a computer.

## No comments:

## Post a Comment