Monday, April 12, 2010

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). There is also a file to specify the initial location of the pieces for a particular puzzle (advsolitaire1.lp).

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.

No comments:

Post a Comment

Followers

Contributors