Games: Rubik's Cube and the Sliding-Tile Puzzle

The trade-off between search and knowledge is illustrated using two popular puzzles: Rubik’s Cube and the sliding-tile puzzle. Given a puzzle position that you want to solve (Start), you need to manipulate it to reach the solution (Goal). This can be done using search alone, but the number of possible scenarios to consider might be enormous. Instead, we usually enhance the search with knowledge. A little knowledge can reduce the search required, often by an enormous amount. This chapter shows two ways in which human reason can be used to create a piece of knowledge to improve the search. A famous formula in AI is this: F = G + H. F is the minimum number of moves needed to solve the puzzle, G is how far along the solution path we are already, and H is our knowledge (heuristic) that says at least how far we have yet to go to reach a solution. We can use F to logically eliminate (large) parts of the search.