Purple And Green

Here is another of my attempts at using a computer to solve puzzles. I created this in 2002 to solve the “Purple and Green” puzzle. I don’t know the actual name of the puzzle as I no longer have the packaging. Edit: Apparently it is called Mind Lock. There is a comprehensive description of the puzzle and solution here

The puzzle is purple on one side and green on the other. It contains four purple squares which can slide within the frame and four similar green squares. Hidden between the squares, or at least, hidden to start with, are three yellow squares.

Pieces may be moved into the space created by only having three yellow squares. This then allows pieces to slide around the grid. The puzzle starts off as shown in the pictures but can soon end up with green pieces on the purple side of the frame, purple in the middle and yellow on the green side, etc.

I decided that this puzzle could be solved by computer using what is known as God’s Algorithm. Although it appears complex, there are a limited number of possible states the puzzle can have - 16,777,216, in fact, of which we can exclude the ones where spaces appear in the centre of the puzzle, leaving us with only 92,400 possible puzzle configurations.

Note that we exclude the configurations where the space piece is in the centre of the puzzle as these configurations are equivalent to having the space on the top or bottom face. With the space in the middle face it is impossible to slide any pieces around the puzzle. It is this optimisation that makes the God’s Algorithm solution practical for this puzzle.

My software solution to this puzzle runs very quickly indeed. This high performance is achieved by cheating. The bulk of the work is done up front in creating a re-usable data table for the code to read from. This only needs to be done once as it contains all possible solutions for the puzzle. To solve any given puzzle all that needs to be done is to look the solution up in the table.

Of course, creating the table takes a little time. The table contains a highly compressed representation of all possible puzzle states and the links between them. It does this by using a hashing scheme. Each index position in the table represents a possible state for the puzzle. The contents of the table at any given index position show the index position of the next step towards the solution. By using a bit-level representation for puzzle states (explained in the source code comments) the table size is reduced to under a megabyte.

The solution to any given starting state of the puzzle is found by looking up that state in the table. The entry for that state will point to another entry for a state closer to the solution. This entry is then looked up and the process repeated until the solution is reached.

To create the table, the computer doesn’t have to know anything about solving the puzzle. Instead a rather sneaky trick is employed. The code works backwards, starting from a solved puzzle and scrambling it up. The table-creating algorithm is equivalent to a Breadth First Search.

From a starting state of the puzzle we work out all possible moves from that state and enter the results of making those moves into the table. If we’ve seen a state already, then we don’t enter the move, as the fact we have already seen that state means we know we have a shorter route to that state. This is how we end up with God’s Algorithm - the very best possible solution for any possible puzzle configuration.

Calculating all possible moves from any given puzzle state is a trivial matter as no matter what state the puzzle is in there are always three possible moves.

View the source code here