Solving sliding-block puzzles
Ruben Grønning Spaans · 2009
We take a look at the complex domain of sliding-block puzzles, which offers significant challenges for the field of artificial intelligence. By analysing the properties of this domain, as well as similar domains where more published literature exists, we develop new domain-specific methods in an attempt to overcome the combinatorial explosion of this domain. We implement a sliding-block puzzle solving program that uses the traditional search algorithms BFS, A* and IDA* in combination with our domain-specific enhancements. We evaluate the performance of our program against a state-of-theart implementation of BFS, and show that we can reduce the search work by several orders of magnitude using domain-specific enhancements. We conclude our work by suggesting new techniques and areas that can be researched in order to further combat the complexity of solving sliding-block puzzles.