So, baited me successfully. I decided to give it a go with my own code. This is more of a dynamic programming approach, and I wanted to use Boost's Graph library, which wasn't strictly necessary but it let me flex those otherwise atrophied muscles. The first little bit it spends just building up the solution tables (if I persisted this information I could speed startup a fair bit, although it is still pretty darn fast). The code could definitely use a lot of cleanup (there is at least one class that is basically screaming to be built), but it works and (given enough memory) can even solve bigger grids. Here's a sample run:
$ ./solvepuzzle Vertex size: 1 moves=edges(g)=(0,3)(0,1)(1,4)(1,2)(2,5)(3,6)(3,4)(4,7)(4,5)(5,8)(6,7)(7,8) Total permutations:362880 Total reachable permutations:181440 Added: 2 new positions that require 1 to solve Added: 4 new positions that require 2 to solve Added: 8 new positions that require 3 to solve Added: 16 new positions that require 4 to solve Added: 20 new positions that require 5 to solve Added: 39 new positions that require 6 to solve Added: 62 new positions that require 7 to solve Added: 116 new positions that require 8 to solve Added: 152 new positions that require 9 to solve Added: 286 new positions that require 10 to solve Added: 396 new positions that require 11 to solve Added: 748 new positions that require 12 to solve Added: 1024 new positions that require 13 to solve Added: 1893 new positions that require 14 to solve Added: 2512 new positions that require 15 to solve Added: 4485 new positions that require 16 to solve Added: 5638 new positions that require 17 to solve Added: 9529 new positions that require 18 to solve Added: 10878 new positions that require 19 to solve Added: 16993 new positions that require 20 to solve Added: 17110 new positions that require 21 to solve Added: 23952 new positions that require 22 to solve Added: 20224 new positions that require 23 to solve Added: 24047 new positions that require 24 to solve Added: 15578 new positions that require 25 to solve Added: 14560 new positions that require 26 to solve Added: 6274 new positions that require 27 to solve Added: 3910 new positions that require 28 to solve Added: 760 new positions that require 29 to solve Added: 221 new positions that require 30 to solve Added: 2 new positions that require 31 to solve Added: 0 new positions that require 32 to solve Total positions: 181440 Most moves: 31 Please enter the configuration you'd like to solve, 0 is the space 4 1 2 8 5 3 0 6 7 Board layout: 4 1 2 8 5 3 0 6 7 Move: 3->6 Board layout: 4 1 2 0 5 3 8 6 7 Move: 0->3 Board layout: 0 1 2 4 5 3 8 6 7 Move: 1->0 Board layout: 1 0 2 4 5 3 8 6 7 Move: 2->1 Board layout: 1 2 0 4 5 3 8 6 7 Move: 5->2 Board layout: 1 2 3 4 5 0 8 6 7 Move: 8->5 Board layout: 1 2 3 4 5 7 8 6 0 Move: 7->8 Board layout: 1 2 3 4 5 7 8 0 6 Move: 6->7 Board layout: 1 2 3 4 5 7 0 8 6 Move: 3->6 Board layout: 1 2 3 0 5 7 4 8 6 Move: 4->3 Board layout: 1 2 3 5 0 7 4 8 6 Move: 5->4 Board layout: 1 2 3 5 7 0 4 8 6 Move: 8->5 Board layout: 1 2 3 5 7 6 4 8 0 Move: 7->8 Board layout: 1 2 3 5 7 6 4 0 8 Move: 4->7 Board layout: 1 2 3 5 0 6 4 7 8 Move: 3->4 Board layout: 1 2 3 0 5 6 4 7 8 Move: 6->3 Board layout: 1 2 3 4 5 6 0 7 8 Move: 7->6 Board layout: 1 2 3 4 5 6 7 0 8 Move: 8->7 Board layout: 1 2 3 4 5 6 7 8 0 Solved!!! --Chris -- [email protected] http://www.kernel-panic.org/cgi-bin/mailman/listinfo/kplug-lpsg
