One of the problems studied early on in the development of artificial intelligence was that of solving permutation puzzles. These include, among many others, the well known Rubiks Cube and 15puzzle. With their clear states and actions permutation puzzles provided a fertile testbed for the development and testing of discrete search algorithms. One approach that has proven to be effective for finding shortest solutions for permutation puzzles is that of using parts of the problem as a heuristic, i.e. realizing that the entire puzzle needs at least as many moves as any of it’s parts and using this to eliminate non-optimal paths in the search tree. In practice these subproblems are usually solved exhaustively beforehand and the results stored in a so called pattern database. (More on this in AIMA 3.6.3)
For difficult problem these pattern databases are quickly limited by the available memory. Thus the question arises to which degree the entire search can be sped up by adopting a multi stage approach. Here some subproblems, which are still larger than the pattern databases, would be solved optimally to potentially eliminate some paths in the overall search early on.
The objective of this thesis would be to implement, benchmark and tune this approach for the Rubik’s Revenge puzzle, the 4x4x4 version of the Rubiks Cube.