Prof Richard Mitchell School of Systems Engineering

Home

Research

Teaching

Admin

Local IET

IEEE SMC

On Backtracking

The example programs given on the main demos page are interesting puzzles all of which can be solved by a trial and error technique. The pentominos puzzle is to place all of the 12 pentominoes (the unique shapes made from joining five squares) into a given area of 60 squares. The n-queens problem is to place n queens on an n*n chessboard such that no queen is 'in check' of any other - i.e. there is no more than one queen in each row, column or diagonal. The hexagon puzzle, has seven hexagons comprising six differently coloured triangles, and the problem is to place them such that the colour of each triangle is the same as that of the adjacent triangle on a different hexagon. Other examples, like maze solving and sudoku puzzles are also shown.

The programs show how a computer solves the problem as it goes along, using backtracking. The programs can operate such that you have to press a button after each move, or they can run continually until one (or all) solutions to the puzzle is found - when the program can be slowed or speeded up.

(The sudoku program also enables you to solve the puzzle with build in rules)

Each problem has different stages - for the n-queens it is to put a queen somewhere in one row; for the hexagons it is to find a hexagon which can be placed in the next position; for pentominoes it is to find a pentomino which can be placed in the next free square.

The backtracking algorithm works by trying to find a solution to the current stage

In the n-queens problem the algorithm searches along the row to find a square where the queen could (as far as can be determined) be placed. In the hexagons problem it tries each unused hexagon in turn until one can be placed there. In each case the queen or hexagon is placed there.

If the last stage has been reached - last row in n-queens or the last hexagon, the problem is solved, otherwise, the algorithm tries to solve the next stage (place queen in next row or find hexagon in next position)

If a solution has been solved, that is fine. Otherwise, the current choice (square where the queen is placed, or chosen hexagon) is not valid for the problem to be solved, so it is removed and the next possible 'part solution' is found.

This is best implemented by defining a part program (often called a procedure or function) which tries to solve the current stage, which can be defined as follows

procedure Try (stage)

Choice variable

Initialise Choice

REPEAT

    IF it is acceptable to use current Choice for this stage THEN

        place piece at this choice

        IF at last stage THEN Solution Found ELSE Try (next stage)

        IF NOT Solution Found THEN remove piece from this choice

   END IF

   Move to next Choice

UNTIL Solution Found OR tried all Choices

Note, the procedure Try calls itself - a recursive call. The key to understanding such calls is to accept that the Try procedure does what it says (i.e. it tries to put a piece at the next stage) - and not worry how it does it. For more information on recursion, please see the Towers of Hanoi program on the main demos page.

When you view the programs you will see pieces positioned and later removed, until a solution is found.

Note, the pentominos puzzle is slightly more complicated, as there are two choices to be made - to find a pentomino to fit in the next place and to choose which of up to 8 orientations of the pentomino.

Backtracking can be used for many other problems.

The Knight's Tour is one : here a Knight is placed on one position of the board and has to move using its usual 2+1 moves such that it lands on each square of the chess board once only. An extension is for the final position to be such that the Knight can then move back to the start position.

Mazes can also be solved using the method - though other algorithms may be better.