Previous examples of recursion (procedures that call themselves either directly or by calling a second procedure that directly or indirectly calls the first) included the recursive factorial procedure, tower of Hanoi and the cardinal/binary conversion program in chapter 4.
Another application of recursion comes in programs that have to perform trial-and-error steps through some kind of pattern, perhaps at times retracing the logical path to the last success and then following a different branch.
This technique is known as backtracking, and is similar to the methods one might use in finding the way through a maze. When one arrives at a dead end, backtracking back to the last known branch in the maze with an untried turn and trying another path is sure to produce a way through the maze if there is one. The advantage of using a computer to solve such problems is that the very large number of trials can all be properly kept track of, and new ones can be tried very quickly. In the example that follows, this (inherently recursive) technique is used to solve an old chess problem.
On a chess board, a knight can move one space in any direction and two spaces at right angles to the first part of the move, or the other way around. Figure 11.1 illustrates the (as many as) eight possible moves a knight may make, in this case on a five by five grid. Starting at the position K the knight may be moved to any one of the numbered squares on its first move.
A Knight's Tour is a sequence of legal knight moves in which every square of the board is visited exactly once (that is, a covering of the board.)
Depending on the size of the board (and possibly the starting position,) it may or may not be possible to conduct a knight's tour. Figure 11.2 illustrates a covering of the five by five grid above with legal knight's moves starting at the indicated position, and beginning with move 2a. The reader should verify that on a three by three grid, it is impossible to conduct a Knight's tour, regardless of the starting position. If the piece starts in the centre square, it cannot move at all, and if it starts on an outside square, it can never reach the centre.
Question: Starting with an n by n board and a chess knight located at a specific position, find a covering of the board consisting of n2-1 subsequent legal knight's moves.
First (recursive) cut: Reduce the problem to that of either performing a next move or finding that one is impossible.
KnightsTour
initialize a selection of possible moves
PROCEDURE TryNextMove
BEGIN
REPEAT
select next candidate from the possible next moves
IF acceptable
THEN
record move
IF board not covered
THEN
TryNextMove
IF not successful
THEN
erase previous recording
END
END
END
UNTIL (move was successful) OR (no more candidates)
To make this precise:
TYPE
Index [1..n];
Board = ARRAY Index, Index OF INTEGER;
Decisions:
Of course, not all these will produce legal moves. Some might put the piece off the board. For instance, if the piece were on the right hand edge of the board, the relative horizontal move must be negative, and similarly for other positions on the edges. Additional restrictions must be made if the piece was one square from an edge, for then it cannot move two squares in that direction. There are several ways these checks can be expressed; a difficulty is to find one that is efficient.
Other moves might be legal (on the board), but land the piece on a square previously visited. The legal moves, and the checking of them could be expressed as:
KnightsTour
initialize a matrix dX of possible horizontal moves
initialize a matrix dY of possible vertical moves
initialize all the board positions b[i, j] to zero
procedure TryMove (input : moveNumber, currentCoordinates,
output: moveOK)
set count to 0
repeat
Increment count
set moveOK to false
set m (new x-coordinate) to (old x-coordinate + dX [count])
set n (new y-coordinate) to (old y-coordinate + dY [count])
if (m >= 1) & (m <= size) & (n >= 1) & (n <= size) & (board [m, n] = 0)
then
set board [m, n] to moveNumber;
set moveOK to true;
if moveNumber < totalSquares (* if the board is not filled *)
then (* try the next move *)
TryMove (moveNumber + 1, m, n, moveOK);
if not moveOK
then
set board [m, n] to 0; (* erase move *)
endif
endif
endif
until moveOK or (count = 8)
end TryMove
Note the necessity to have the coordinates as integers because the values dX and dY that will be added are often negative. Also, it is relatively easy to write out the final result in a form that allows the user to see the actual tour in a matrix form. Here is the whole code:
MODULE Knight;
(* Written by R.J. Sutcliffe *)
(* to illustrate backtracking *)
(* last revision 1994 06 08 *)
(* This program calculates the path a knight would take, starting from any square on a chessboard, which covers the entire board and does not re-visit a square--the "Knight's Tour" *)
FROM STextIO IMPORT
WriteString, WriteLn, SkipLine;
FROM SWholeIO IMPORT
ReadInt, WriteInt;
CONST
size = 7; (* number of squares each way; change as desired *)
totalSquares = size * size; (* total # of squares to cover *)
TYPE
Index = [1..size];
VAR
rowCount, colCount : CARDINAL; (* counting variables *)
rowStart, colStart : INTEGER; (* starting position *)
pathFound : BOOLEAN; (* outermost level success variable *)
dX, dY : ARRAY [1..8] OF INTEGER; (* store possible moves *)
board : ARRAY Index, Index OF INTEGER; (* the chessboard *)
PROCEDURE TryMove (moveNumber, x, y : INTEGER; VAR moveOK : BOOLEAN);
(* Pre: board must be initialized correctly and (x, y) must be on the board
Post: moveOK is FALSE if a path was not found from (x, y), TRUE if a path was found
Note: this procedure is recursive, and will find an entire path starting from (x, y) *)
VAR
count, m, n : INTEGER;
BEGIN
count := 0; (* counter for the legal moves *)
REPEAT
INC (count);
moveOK := FALSE; (* default value *)
m := x + dX [count]; (* calculate next move *)
n := y + dY [count];
IF (m >= 1) & (m <= size) & (n >= 1) & (n <= size) & (board [m, n] = 0)
(* if next move is on the board and to an empty square *)
THEN
board [m, n] := moveNumber; (* mark the square *)
moveOK := TRUE;
IF moveNumber < totalSquares (* board is not filled *)
THEN
TryMove (moveNumber + 1, m, n, moveOK);
(* try next move *)
IF NOT moveOK
THEN
board [m, n] := 0; (* erase move to backtrack *)
END;
END;
END;
UNTIL moveOK OR (count = 8);
END TryMove;
PROCEDURE PrintBoard;
VAR
rowCount, colCount : CARDINAL;
BEGIN
FOR colCount := 1 TO size
DO
FOR rowCount := 1 TO size
DO
WriteInt (board[rowCount,size+1-colCount], 5);
END;
WriteLn;
WriteLn;
END;
END PrintBoard;
BEGIN (* main program *)
(* initialize move increments *)
dX[1] := 1; dX[2] := 2; dX[3] := 1; dX[4] := 2;
dX[5] := -1; dX[6] := -2; dX[7] := -1; dX[8] := -2;
dY[1] := 2; dY[2] := 1; dY[3] := -2; dY[4] := -1;
dY[5] := 2; dY[6] := 1; dY[7] := -2; dY[8] := -1;
FOR rowCount := 1 TO size
DO
FOR colCount := 1 TO size
DO
board[rowCount, colCount] := 0; (* initialize board *)
END;
END;
(* get starting information *)
WriteString ("Start at x = ");
ReadInt (rowStart);
SkipLine;
WriteLn;
WriteString ("Start at y = ");
ReadInt (colStart);
SkipLine;
WriteLn;
board[rowStart, colStart] := 1; (* set first position *)
TryMove (2, rowStart, colStart, pathFound);
(* call recursive procedure *)
IF pathFound
THEN (* display final results *)
PrintBoard;
WriteString ("path found!");
WriteLn;
ELSE
WriteString ("no path found");
WriteLn;
END;
END Knight.
This module was run with the constant size set first to 5 (twice), then 6, and finally seven. Here are the results:
** Run log starts here **
Start at x = 3
Start at y = 3
23 12 7 2 21
6 17 22 13 8
11 24 1 20 3
16 5 18 9 14
25 10 15 4 19
path found!
** Run log starts here **
Start at x = 1
Start at y = 1
25 18 3 12 23
8 13 24 17 4
19 2 7 22 11
14 9 20 5 16
1 6 15 10 21
path found!
** Run log starts here **
Start at x = 1
Start at y = 1
36 31 34 21 4 7
33 20 3 6 11 22
30 35 32 23 8 5
19 2 27 10 15 12
26 29 14 17 24 9
1 18 25 28 13 16
path found!
** Run log starts here **
Start at x = 4
Start at y = 4
49 22 19 44 17 10 3
46 43 48 21 2 7 16
23 20 45 18 9 4 11
42 47 32 1 6 15 8
33 24 35 38 29 12 5
36 41 26 31 14 39 28
25 34 37 40 27 30 13
path found!