11.2 Recursion Revisited

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.

AKnight's Touris a sequence of legal knight moves in which every square of the board is visited exactly once (that is, acoveringof 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 n^{2}-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:

- represent the board as a matrix
- index the board [1..n] on each dimension

TYPEIndex [1..n]; Board =ARRAYIndex, IndexOFINTEGER;

Decisions:

- suppose b is of type Board
- let b[x,y] be zero if the square has not been visited
- enter the number i into cell b[x,y] if it was visited on turn number turn
- call the initial position turn one
- then the condition board not full is (i < n
^{2}) - a potential move from the current position can have local coordinate changes (relative to the current position) of u and v
- acceptable u and v are

1. (1, 2) 5. (-1, 2)

2. (2, 1) 6. (-2, 1)

3. (1, -2) 7. (-1, -2)

4. (2, -1) 8. (-2, -1).

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:

MODULEKnight; (* 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" *)FROMSTextIOIMPORTWriteString, WriteLn, SkipLine;FROMSWholeIOIMPORTReadInt, WriteInt;CONSTsize = 7; (* number of squares each way; change as desired *) totalSquares = size * size; (* total # of squares to cover *)TYPEIndex = [1..size];VARrowCount, colCount :CARDINAL; (* counting variables *) rowStart, colStart :INTEGER; (* starting position *) pathFound :BOOLEAN; (* outermost level success variable *) dX, dY :ARRAY[1..8]OFINTEGER; (* store possible moves *) board :ARRAYIndex, IndexOFINTEGER; (* the chessboard *)PROCEDURETryMove (moveNumber, x, y :INTEGER;VARmoveOK :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) *)VARcount, m, n :INTEGER;BEGINcount := 0; (* counter for the legal moves *)REPEATINC(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 *)THENboard [m, n] := moveNumber; (* mark the square *) moveOK :=TRUE;IFmoveNumber < totalSquares (* board is not filled *)THENTryMove (moveNumber + 1, m, n, moveOK); (* try next move *)IFNOTmoveOKTHENboard [m, n] := 0; (* erase move to backtrack *)END;END;END;UNTILmoveOKOR(count = 8);ENDTryMove;PROCEDUREPrintBoard;VARrowCount, colCount :CARDINAL;BEGINFORcolCount := 1TOsizeDOFORrowCount := 1TOsizeDOWriteInt (board[rowCount,size+1-colCount], 5);END; WriteLn; WriteLn;END;ENDPrintBoard;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;FORrowCount := 1TOsizeDOFORcolCount := 1TOsizeDOboard[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 *)IFpathFoundTHEN(* display final results *) PrintBoard; WriteString ("path found!"); WriteLn;ELSEWriteString ("no path found"); WriteLn;END;ENDKnight.

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!