spurious_ai wrote:Looking at your code Remi, not quite sure of the difference between a breadth search and a beam search.
I think "beam search" is basically a breadth-first search, but discarding nodes beyond a limit.
I am not sure how these mod tables are designed Luke. There is something to be said for mechanics and speed, but finding the heuristic is the true spirit of the contest.
Well, the idea for the rotations table is this. First, solving the actual puzzle means that you have also solved the puzzle modulo 4. So, the minimum number of rotations needed for the actual puzzle, is at least the number needed for the mod 4 puzzle. Now, we can create a lookup table of all mod 4 puzzles -- there are 4^25 of them. However, since we allow unlimited additions, we can zero out the first row & column with additions, leaving only 4^16 that we actually need. (You could further reduce this with symmetries.) That's just within reach if you give 4 bits per entry.
Creating the table was nothing terribly exciting, performance was the main issue (both memory access and CPU speed are major bottlenecks!). Starting with the solved puzzle, give it a value of 0. Then, compute all possible puzzles one move away, and give them values of 1. Then for each puzzle with value 1, compute all puzzles one move away and give them value 2. Et cetera. As I mentioned, it was disappointing, but only 4 rotations ever seem to be necessary. However, it's just enough to make puzzles requiring ~20 moves solvable.