17 December 2005

A few months back Randy Kimmerly posted a blog about one the puzzles on my desk.

Twisted in the correct way it will form a 3x3x3 cube. It is a snake cube puzzle that goes by the commercial name of Cubra©. Randy got excited about the puzzle not for the puzzle itself but by the challenge of writing a program that will produce the solution. He wrote a very clever C# program to produce a solution. I thought the solution would be more concise in Prolog so I volunteered to produce a Prolog version. I had to dust off my Prolog skills, I hadn't used Prolog since I used to support Turbo Prolog for Borland, so my skills are a bit rusty. Here is my solution,

The clause linkTurns/1 represents where the string of blocks turns and where it doesn't. inrange/1 represents the valid ranges the coordinates of a block can have, 0, 1 or 2. This is used to build cell/3 which represents the locations the blocks can occupy in a 3x3 result. move/3 calculates how to get from one block to another.  legalTurn/2 generates legal turns. free/2 helps decide if a cell is already occupied.  solution/5 calculates the solution; and solution/2 is a simplified wrapper around solution/5. print_solution/2 is a utility clause to help print the solution in a some what readable form. Finally goal is a clause that kicks off the whole process (a dead giveaway to Turbo Prolog roots).

This will only print one solution (because of the implied cut in using I/O) even though there are two possible. To see both use,

You will notice that both solutions are reflexive of each other so you could say there is really only one solution.

I found an interesting site here that discusses these puzzles as well as gives a break down of how many of these kinds of puzzle there can be.