You can swap two pieces in place in Scarne’s challenge, but not in the normal 8 or 15 puzzles. This is because there are no odd length cycles in the 8 or 15 puzzles, but there are cycles of length three in Scarne’s challenge. The easiest way to see this is to draw the graphs out The 15 puzzle has no triangles in the graph, but Scarne’s Challenge does. (Does this mean that Scarne’s challenge is in some sense easier? I’ll have to think about it some more.)

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.
Continue reading →