brainwagon

After a couple more hours of typing, I managed to get a start on Scarne’s Challenge. I’ve got a simple version of IDA* with transposition tables working, along with a simple heurstic based entirely on summing the shortest path distance between where a node is and its desired final position. It is smart enough to find solutions to simple problems. For example, if you start with the board in the goal position except with 2 and 1 swapped, it finds the 22 move sequence that reverses their position after searching 411,573 nodes. For the official challenge position of course, it fairly quickly determines that the path must be at least 66 moves long (not suprising), but the combinatorial explosion is working pretty hard there. I obviously need to use a smarter heuristic (perhaps based upon the ideas that Korf used in solving random instances of the 5×5 puzzle) to have any hope of finding the answer to this problem in non geologic time.