Lunar Lockout

Lunar Lockout is a simple logic game, which was shown to me by a primary school teacher who bought it for the kids in her class. A few pieces are placed on a 5x5 board. The goal is to place a particular piece at the center, while being allowed to move any piece only if it can be blocked by another piece. It's a classic example of a game that can be solved by brute-force search.

I programmed a simple solver in Python. The method by which I programed this solver could be used to solve many other logic games. In fact, you could easily abstract the pieces away. You need:
  1. a representation for a state of game (here, I use a list of cartesian coordinates, one per piece, the first element being for the piece that has to be moved to the center),
  2. a function to generate all legal moves for a given state game,
  3. a function that applies a move to a given game state, returning a new game state (it's easier than mutating the given game state for searching many alternatives at once).
  4. a predicate to test whether a game state is a solution (here, I simply check whether the first coordinate is the center of the board).

With this pieces, it's easy to do a brute-force search (here, I use a breath-first search which skips already seen game states).

3 comments:

Light Knight said...

Hi. I stumbled upon this excellent site on a Lunar Lockout solver:

http://www.cz.j.th.schule.de/neueseite/fachbereiche/informatik/lunar_lockout/doku%5Ben%5D.htm

I've managed to create a few puzzles that require 14(!) steps to solve.
Have you ever encountered any LL puzzles that required more than 14 steps?

I wish that there were a program that could display all possible positions with N steps as the solution. That would be great huh?


Frankie Kam
frankie@stamford.edu.my

Light Knight said...

The website link I posted has a download exe for XP or Win2000. Try it.

Frankie Kam
Melaka, Malaysia

Light Knight said...

Here's ANOTHER Lunar Lockout Solver. So the cat's out of the bag. Anyway it looks interesting. Check it out!

http://www.pds.ewi.tudelft.nl/~iosup/personal_projects.html

Labels