Lunar Lockout

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:

1. move piece 4 to (0,-2)
   
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.