Consider the following sliding-blocks puzle, consisting of three
black tiles, three white tiles, and an empty space.
The initial configuration for the puzzle consists of all the black tiles to
the left, all of the white tiles to the right, and the empty space in the
middle. For example, the following shows the initial configuration:
The goal is to reverse the locations of the tiles, i.e., have all white
tiles to the left and all black tiles to the right, with the space in the
middle. There are two types of moves allowed. A tile can move into an
adjacent empty space, or it can jump over two adjacent tiles into the empty space.
- Define a state space for this problem by specifying the representation
of a state and listing all possible moves from one state to another.
- Attempt to solve this problem using the uninformed search control strategies:
DFS-nocycles, BFS-nocycles, and DFS-deepening.
Describe and compare your results.
- Now devise a heuristic that you think would help lead to
a solution. Implement your heuristic as a Scheme function and solve the
problem using best first search. Compare the performance of best first
search using your heuristic with that of the uninformed strategies.