[Next] [Up] [Previous]

Solving a Jigsaw

We shall now give a completely different example of a problem that demands a search method. It is a small puzzle, but is analogous to many problems in the real world where a resource must be divided up subject to some constraints. In this case a frame must be divided up into sections subject to the constraint that the shapes of the sections correspond to the shapes of jigsaw pieces.

The problem is to fit the shaped pieces shown in figure 4.4 into the frame. A larger version of this puzzle, involving 27 pieces, is almost impossible to solve in any reasonable time by hand, but a modest computer running a search program can find the answer in a few minutes. How does the search proceed? Essentially, it tries questions of the form ``What if this piece goes in in this position?'' until it finds a combination that fits. It starts from one corner of the frame, and uses the fact that some corner of a piece must fit there in order to generate the possibilities to test. From that first position it carries out a depth first search of possible placings. At each stage a corner with an acute angle in the free space is selected, and a piece that can cover the corner is tried out there. The process is repeated, going down each branch of the tree in turn, until there is no piece that can fit the chosen corner, or until all the pieces have been fitted. If we reach a point where all the pieces fit, then the puzzle has been solved.

  [IMAGE ]
Figure 4.4: A jigsaw puzzle to be solved by search. The 4 pieces must be fitted into the frame.

If no piece can be fitted in the corner chosen, then the program removes the last piece fitted from its internal representation of the frame and tries it in a different orientation, or else it tries a different piece in the same corner. This behaviour is known as backtracking.

Try out the puzzle for yourself. Cut out the pieces from cardboard and, starting at the top left corner, place the pieces using a systematic, depth first, strategy, backtracking if you cannot place a piece, until you have solved the puzzle.

The tree structure for the first few attempts at the puzzle is shown in figure 4.5. Each node in the tree represents the current state of the frame. If the program happens to try the pieces in the order corresponding to the figure (trying the left branch first each time), then it will have to backtrack four times before it finds a solution. The nodes are numbered in the order that they are examined.

  [IMAGE ]
Figure 4.5: Part of the search tree for the jigsaw puzzle.

[Next] [Up] [Previous]