Well, I decided to start my exploration of the Scarne’s challenge by writing a simpler program to test out my recollection of how the A* algorithm worked. I chose to implement a simple version of iterative deepening A* for the 8-puzzle, the simple 3×3 sliding tile puzzle that perhaps might be more familiar as a 4×4 puzzle. I spent a little less than two hours writing the first version, which did manage to find minimal solutions to the search problem, but seemed to search too many nodes to do so, even allowing for the simple heuristic that I used.

After a few hours of intermittent pondering, I determined that my heuristic function was not admissible: it overestimated the cost of reaching the goal node. The bug was in the handling of the space: every move changes the space, so it doesn’t actually “cost” anything to move. Once I got this straight, it generated solutions to randomized instances of the 8 puzzle fairly quickly.

My next step will be to be a bit more intelligent about other aspects of the system: using transposition tables, pruning inverse move sequences, and use of a heuristic which includes linear conflict resolution. Using these extensions, 4×4 puzzles should be doable.

The 5×5 sliding tile puzzle is a trillion times more complicated than the 4×4 case, and is close to the limit that we could hope to achieve using computers. The real Scarne’s Challenge has roughly the same complexity, and may take several months (or as little as a few hours) to crack. I may create a 13 node mini-challenge to work on, just to get a feeling for the puzzle. This will be intermediate in complexity between the 3×3 sliding block puzzle and the 4×4 puzzle.

One other interesting thing to note is that while half of the possible permutations of the sliding block puzzles are unreachable from the goal state, this property is not shared by Scarne’s puzzle. It is possible to swap the positions of any two tiles in Scarne’s challenge without moving any other tiles.