Twisting Puzzles
Puzzle Menus
Twisting Puzzles
Solving Puzzles With A Computer
Introduction
Since most solutions to puzzles require logic and thought, it makes sense that a computer might be a useful tool when it comes to solving one. Obviously there is no challenge if you download a computer program, input the position of the puzzle using your mouse and keyboard, click a button and get an algorithm that solves it outright. There is, however, considerable challenge in writing such a computer program yourself and then working out a method that works every time.
God's Algorithm
In cubing, the term, God's Algorithm is used to refer to a method of solving a puzzle using the shortest possible sequence of moves for any given position. In practical terms, we are looking for a table of unique positions and the sequences of moves (or algorithms) that generate them. Each entry is the optimal (shortest) method of generating that state. When the number of positions for a puzzle is relatively small, it is easy to perform the calculation on a computer. For some puzzles though, there are just too many positions to calculate and store in reasonable time and using standard equipment.
How To Calculate God's Algorithm
I usually use an array of integers to store the positions of the pieces that move in a puzzle. If pieces have more than one orientation, I use another array of integers to store the orientations. Each unique position is described by a string of numbers representing the positions followed by a string of numbers representing the orientations.
Make a table to store postions and the moves that make them
Add the solved position to the table
For each possible turn from this position
Do the turn
If this position has not been entered into the table
Enter the position into the table and the sequence that generated it
Repeat the previous step for all of the new positions this generated
The Do The Turn part involves a bit of work. I use arrays of numbers to store the effect of each turn on the positions and orientations of the pieces.
This algorithm starts from a solved puzzle and finds out all of the possible positions generated by a single turn. It then looks at each of these positions and works out all of the positions that can be generated with two turns and so on. Once the program finds that an extra turn will not generate any new positions, it's job is done and it can stop looking.
As the number of positions increases, the program has to do a lot more work and can get quite slow in debug mode. It's worth compiling programs before running them.
Fixed Point Of Reference
You do need to have a fixed point of reference when doing this. There needs to be something that stays fixed on the puzzle or you will find positions which are effectively the same as other positions. For example, with the pocket cube, you can assume that the back bottom left corner does not move (and use only F, R and U turns). For the slim tower, assume that one of the centre pieces remains fixed - and do only F, R, U and D moves.
God's Algorithm Calculations
The following table shows God's algorithm calculations that I have made for some of my puzzles,
| Turns | Floppy Cube | Slim Tower | Pocket Cube | Pyramorphix* |
|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 1 |
| 1 | 4 | 8 | 9 | 9 |
| 2 | 10 | 35 | 54 | 54 |
| 3 | 24 | 157 | 321 | 321 |
| 4 | 53 | 678 | 1847 | 1835 |
| 5 | 64 | 2527 | 9992 | 9716 |
| 6 | 31 | 7442 | 50136 | 39536 |
| 7 | 4 | 17088 | 227536 | 68424 |
| 8 | 1 | 31568 | 870072 | 16120 |
| 9 | 44704 | 1887748 | 64 | |
| 10 | 47216 | 623800 | ||
| 11 | 29024 | 2644 | ||
| 12 | 11104 | |||
| 13 | 576 | |||
| Total | 192 | 192128 | 3674160 | 136080 |
* The pyramorphix is a 2x2x2 puzzle where 4 of the pieces have no orientation markings. To generate these figures, all I did was to adapt my 2x2x2 program to wipe out orientation changes for these 4 pieces before checking the position in the table.
You can find the figures in my tables published in all sorts of places on the WWW. If you are looking for the GA table for a different puzzle that this can be done for, you are most likely going to find it on Jaap's Puzzle Page. I would also recommend checking any of your own calculations with those on Jaap's site. The table above shows only those figures that I have calculated myself with computer programs - mainly console programs written in C#.
The source code for the floppy cube program is available on this site spread across a few pages in the C# console section, starting with Floppy Cube Project - The Problem
I also have a table of positions for the bandaged cube. The figures aren't shown because my program came up a little short of the number I know to be true - about 0.01% of positons missing. Still, I did generate all but 5 of the 2520 positions that have all the pieces correctly oriented - giving me the optimal algorithms for everything I would ever do with the puzzle.
Using The Table
The tables shown above are useful enough in themselves. They give a sense of how complex a solution to the puzzle needs to be and a rough idea of the number of moves to solve it. Remember that these positions are reached with optimal algorithms, so a human method is going to require a lot more turns than the puzzle diameter. For example, a method for the floppy cube which breaks the solution down into memorable steps might require a maximum of 14 turns, nearly twice the diameter of the puzzle.
Some puzzles have lots of positions and a lot of turns to generate them, but don't make for a puzzle with that much challenge. The rainbow cube is an example of this. It has about 240 million positions but is solved by repeatedly applying the same simple strategy - you don't need to work hard to avoid messing up what you have already done.
What I do with the table depends on the numbers. When the overall number of entries is a few hundred thousand or fewer, I tend to output the tables in a format that I can import into a database program. I then use queries and regular expressions to find the patterns or positions that I want to solve. If the number is in the millions, as it is with the pocket cube, I create the most compact file I can and write a program to read and use the data.
I check the table in all sorts of ways and still get a buzz out of finding the solution in my database to any scrambled position. After that, I think about the method I'm using for the puzzle, and the lengths of algorithms I do at each stage.
The solution to the Slim Tower on this site uses the shortest algorithms I could find (in face turn metric - a double turn of one face counts as 1) in my database. It means that a solution will take a maximum of 24 turns and have a decent average length. Using the same 3 stages for that method, I'm not going to snip any more moves off the method.