Part A--Programming Techniques

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.

11.2.1 The Knight's Tour--An Extended Example

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!

Contents