Subgoal Strategies for Solving Board Puzzles

We show that a few simple search strategies can solve a variety of difficult puzzles ranging from the 15-puzzle to central solitaire, Rubiks cube, and several of its variants. One of these strategies automatically generates subgoals; another finds efficient sets of rules for the subgoals. The subgoals are based on the reversal of simple logical implications. With these strategies and a simple learning algorithm, we not only solve particular instances of these problems but automatically generate programs that solve all instances of the problem with reasonable efficiency. Our automatically generated program for Rubiks cube can solve a fully scrambled cube in about two minutes on a 66 Mhz 486 PC.