On cycles in Scarne’s Challenge

August 28, 2002 | My Projects | By: Mark VandeWettering

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.)