2  INTRODUCTION  The Knight’s Tour §1

1. Introduction. The following program is based on the “Knight’s Tour” algorithm found on pages 137– 142 of Niklaus Wirth’s Algorithms + Data Structures = Programs, translated into the WEB language.

2. This program has no input, because we want to keep it rather simple. The result of the program will be the solution to the problem, which will be written to the output file.

In true top-down tradition, we lay out the entire program as a skeleton which will be filled in later. program knights tour (output );

const ⟨ Constants of the program 6 ⟩

type ⟨ Types of the program 7 ⟩

var ⟨ Variables of the program 8 ⟩ ⟨ Recursive procedure definitions 12 ⟩ begin ⟨ Initialize the data structures 18 ⟩; ⟨ Perform the knight’s tour and print the

results 19 ⟩; end.

3. Here are some macros for common programming idioms.

define incr (#) ≡ # ← # + 1

{ increase a variable by unity }

define decr (#) ≡ # ← # − 1 { decrease a variable by unity }

4. We shall proceed to build the program in pieces, following the text of Wirth’s book and describing the structures and algorithms in more or less the same order that he describes them. Part of the time we will be designing top-down; at other times, bottom-up; but always in the order that contributes most to the understanding of the program. One difference between this description and Wirth’s is that we will use meaningful variable names (rather than names such as u, v, a, b, c). We can get away with this because we don’t have to worry about the entire program being listed in one place at one time in narrow columns. It is broken up into small pieces and spread over several pages.

§5  The Knight’s Tour  THE KNIGHT’S TOUR 3

5. The knight’s tour. For those not familiar with the knight’s tour, it is a classic computer science problem involving a knight, moving according to the rules of chess, which attempts to move to every square of a chessboard once and only once. To implement it, we use what is known as a “backtracking” algorithm, which is a trial-and-error search for a solution, sometimes referred to as a “brute force” approach. We start at a beginning position and try every path leading from that position (there are 8 possible knight moves from a given position) and then every path from each of those positions, etc. We follow every path until either a complete solution is found or the first failure occurs (the square is not on the board or has already been visited). If we get a failure, we “backtrack” to the previous good move and start again from there.

6. The board is a max × max square and the number of squares is max^{2}. Since this program has no input, we declare the value max = 5 as a compile-time constant. ⟨ Constants of the program 6 ⟩ ≡

max = 5; number of squares = 25;

This code is used in section 2.

7. The obvious way to define the board is as a array of two dimensions where the indexes range from 1 to max . ⟨ Types of the program 7 ⟩ ≡

index = 1 . . max ;

This code is used in section 2.

8. Boolean values for the squares would be sufficient if we only wanted to know which squares had been visited, but we also wish to know the order of the visits as well, so we define board as a two-dimensional array of integers. If the value at board [row , col ] = 0 then the square at that position has not been visited and is a candidate for a visit. Otherwise board [row , col ] = i, which indicates that the square was visited on the ith move. The total number of moves (including the first one) = number of squares .

define empty = 0 ⟨ Variables of the program 8 ⟩ ≡ board : array [index , index ] of

empty . . number of squares ;

See also sections 17 and 24. This code is used in section 2.

4  THE KNIGHT’S TOUR  The Knight’s Tour §9

9. Here we initialize all positions on the board to empty . This code is placed in a program scrap separate from all of the other initialization code for reasons explained later. ⟨ Initialize the knights tour board 9 ⟩ ≡

for i ← 1 to max do

for j ← 1 to max do board [i, j] ← empty ;

This code is used in sections 19 and 20.

10. Two local variables, targ row and targ col , are the coordinates of target square, the one we wish to move to next. Before we attempt the move, we must first ensure that target square is on the board (1 ≤ targ row ≤ max and 1 ≤ targ col ≤ max ). Then we must determine if it is available for knight placement (target square = empty ). We provide some macros for manipulation of target square.

Side note: in Wirth’s book, the target position valid test is later changed to be a check for inclusion in the set [1 . . max ] rather than discrete comparisons to 1 and max . While this is more efficient, it does not necessarily aid understanding of the algorithm, so we will not bother.

define valid row or column(#) ≡

((1 ≤ #) ∧ (# ≤ max ))

define target position valid ≡ (valid row or column(targ row ) ∧ valid row or column(targ col ))

define target square ≡ board [targ row , targ col ] define target empty ≡ (target square = empty ) define set square to(#) ≡ target square ← #

⟨ Local variables of the knight’s tour procedure 10 ⟩ ≡ targ row , targ col : integer ;

{ row and column of target square }

See also section 11. This code is used in section 12.

11. There are eight possible knight moves from any given position. Since we normally are going to attempt all eight, we will define candidate move to hold the move index.

define number of legal knight moves = 8 ⟨ Local variables of the knight’s tour procedure 10 ⟩ +≡ candidate move: 0 . . number of legal knight moves ; 12. We are ready to define the procedure which actually does the search. It must be declared as a procedure rather than as simple inline code, since it is recursive. As the procedure is entered for a particular move number and current position, the moves possible from that position are attempted. The procedure passes the value of successful code back to the calling procedure, which will pass it to its own caller, etc., all the way back up to the original call. ⟨ Recursive procedure definitions 12 ⟩ ≡ procedure try knight move(move number : integer ;

row , col : index ; var successful : boolean); var ⟨ Local variables of the knight’s tour

procedure 10 ⟩ begin ⟨ Try the moves possible from the current

position until solution found or all have been tried 13 ⟩;

end;

This code is used in section 2.

13. Each of the 8 possible moves is attempted. If the move can be made, it is recorded and a move from the new position is attempted. If successful is ever true, it can only mean that a complete solution has been found and the search is terminated. If successful is false, the remaining candidate moves are tried.

define no more candidates ≡ (candidate move =

number of legal knight moves )

⟨ Try the moves possible from the current position until

solution found or all have been tried 13 ⟩ ≡ candidate move ← 0; repeat incr (candidate move); successful ← false;

⟨ Set the coordinates of the next move as defined

by the rules of chess 16 ⟩; ⟨ Record the move if acceptable and try to make further moves; set successful if solution found 14 ⟩;

until successful ∨ no more candidates ;

This code is used in section 12.

14. The condition move is acceptable is equivalent to the combination of target position valid ∧target empty . Because of the realities of computer memory addressing, if we find that the condition target position valid is not true, then we cannot perform the second test because the array indexes targ row or targ col are not valid and the contents of target square cannot be accessed. We have to test these two conditions with separate nested if statements (“ if target position valid then if target empty ”).

Once we have determined that the move is acceptable we record it. If board not full is true, we try the next knight move. If board not full is false, it means we have found a solution to the problem, so we set successful to true, which will terminate the tour.

define board not full ≡

move number < number of squares

define record move ≡ set square to(move number ) ⟨ Record the move if acceptable and try to make further

moves; set successful if solution found 14 ⟩ ≡

if target position valid then
if target empty then

begin record move;

if board not full then

⟨ Try further knight moves and erase this move if not successful 15 ⟩

else successful ← true;

end;

This code is used in section 13.

15. Here we try the next move by having the procedure call itself recursively, with the move number incremented by one and targ row , targ col as the position of the move. If a failure occurs on that move or any move that follows it (successful = false), we erase the move we just made (this is the “backtracking” part) and continue looking.

Important note: the begin and end statements are critical for this particular section, since it is used as a then clause and the program text is simply inserted verbatim. Without the begin and end the call to the try knight move procedure alone becomes the then clause, which will cause a syntax error when the dangling else clause is processed.

define next move ≡ move number + 1

define erase move ≡ set square to(empty ) ⟨ Try further knight moves and erase this move if not

successful 15 ⟩ ≡ begin try knight move(next move, targ row ,

targ col , successful ); if ¬successful then erase move; end

This code is used in section 14.

16. We now consider the moves a knight is allowed to make. From any given position there are 8 possible moves, not all of which are neccessarily on the board. Rather than go through a complicated algorithm, we simply initialize a pair of tables, row deltas and col deltas , containing values to be added to the current position to get the target position. For each of the 8 moves which are possible from the current position, row deltas [candidate move] is added to the current row to get targ row and col deltas [candidate move] provides the same service for targ col . ⟨ Set the coordinates of the next move as defined by

the rules of chess 16 ⟩ ≡ targ row ← row + row deltas [candidate move]; targ col ← col + col deltas [candidate move];

This code is used in section 13.

17. If we are going to use these arrays, it might be helpful to define them to keep the Pascal compiler from complaining bitterly. ⟨ Variables of the program 8 ⟩ +≡ row deltas , col deltas : array

[1 . . number of legal knight moves ] of −2 . . 2; 18. Even though the compiler is now happy, if we don’t initialize the arrays with the proper delta values, we will take the knight on a route more like the Drunkard’s Walk than the Knight’s Tour. ⟨ Initialize the data structures 18 ⟩ ≡

row deltas [1] ← 2; col deltas [1] ← 1;

row deltas [2] ← 1; col deltas [2] ← 2;

row deltas [3] ← −1; col deltas [3] ← 2;

row deltas [4] ← −2; col deltas [4] ← 1;

row deltas [5] ← −2; col deltas [5] ← −1;

row deltas [6] ← −1; col deltas [6] ← −2;

row deltas [7] ← 1; col deltas [7] ← −2;

row deltas [8] ← 2; col deltas [8] ← −1;

This code is used in section 2.

19. Now it’s time to actually start the tour. For starting position x_{0}y_{0} we select (1,1). Since this is the first move, we set board [1, 1] = 1. We then call the try knight move procedure with the proper parameters to set events in motion. After all of the moves have been completed, we print out the board. The result should be the same as the first part of Table 3.1 on page 141 of Wirth’s book, which is reproduced here.

1  6 15 10 21
14 9 20 5 16
19 2 7 22 11
8  13 24 17 4
25 18 3 12 23

We define a macro to initialize the first move and start the tour. Note: the call to try knight move in the macro definition appears to have the wrong number of parameters. This procedure requires four parameters and we seem to be passing only three. However, since a macro parameter is really just a simple string substitution, we will really be replacing the # character with two parameters at once: the row and column of the starting position. Since the comma is included in the substitution, the expanded text will have the proper four parameters.

define do the tour starting at (#) ≡ board [#] ← 1;

try knight move(2, #, successful );

⟨ Perform the knight’s tour and print the results 19 ⟩ ≡ ⟨ Initialize the knights tour board 9 ⟩; do the tour starting at (1, 1); ⟨ Print the results of the knight’s tour 23 ⟩;

See also section 20. This code is used in section 2.

20. Since Table 3.1 in the book shows a second solution obtained with a different first move (3,3),

23 10 15 4 25
16 5 24 9 14
11 22 1 18 3
6  17 20 13 8
21 12 7 2 19

we decide to run the tour again to duplicate that result as well. We decline the third test in Table 3.1, because it requires a different value of max , which we cannot change at run-time as the program is currently designed. Before rerunning the test, we must remember to reinitialize the board. This is the reason that the board initialization code was separated from all of the other initializations; it is executed twice. We use the same name when defining the code for this section as for the previous section, which will cause the second test to follow immedately after the first in the Pascal program. ⟨ Perform the knight’s tour and print the results 19 ⟩ +≡

⟨ Initialize the knights tour board 9 ⟩; do the tour starting at (3, 3); ⟨ Print the results of the knight’s tour 23 ⟩;

10  THE OUTPUT PHASE  The Knight’s Tour §21

21. The output phase. The job of printing is not as interesting as the problem itself, but it must be done sooner or later, so we might as well get it out of the way.

22. In order to keep this program reasonably free of notations that are uniquely Pascalesque, a few macro definitions for low-level output instructions are introduced here. All of the output-oriented commands in the remainder of the program will be stated in terms of three simple primitives called new line, print string , and print integer .

define width = 3 { width of an integer field } define print string (#) ≡ write(#)

{ put a given string into the output file }

define print integer (#) ≡ write(# : width) { print

an integer of width character positions }

define new line ≡ write ln { advance to a new line in the output file }

23. ⟨ Print the results of the knight’s tour 23 ⟩ ≡

if successful then

for i ← 1 to max do

begin for j ← 1 to max do print integer (board [i, j]);

new line; end

else print string (´ ␣ ´ );

new line; new line;

This code is used in sections 19 and 20.

24. We define a few more odd variables. ⟨ Variables of the program 8 ⟩ +≡ i, j: index ; { temporary index variables } successful : boolean;

{ The Knight’s Tour was successful }

§25  The Knight’s Tour  INDEX 11

25. Index. Every identifier used in this program is shown here together with a list of the section numbers where that identifier appears. The section number is underlined if the identifier was defined in that section. However, one-letter identifiers are indexed only at their point of definition, since such identifiers tend to appear almost everywhere.

This index also refers to other topics that appear in the documentation (e.g., ‘backtracking algorithm’).

backtracking algorithm: \underline{5}, 15. board : \underline{8}, 9, 10, 19, 23. board not full : \underline{14}. boolean: 12, 24. candidate move: \underline{11}, 13, 16. col : 8, \underline{12}, 16. col deltas : 16, \underline{17}, 18. decr : \underline{3}. do the tour starting at : \underline{19}, 20. Drunkard’s Walk: 18. empty : \underline{8}, 9, 10, 15. erase move: \underline{15}. false: 13, 15. i: \underline{24}. incr : \underline{3}, 13. index : \underline{7}, 8, 12, 24. integer : 10, 12. j: \underline{24}. Knight’s Tour: 1, \underline{5}, 18, 19, 20. knights tour : \underline{2}. max : \underline{6}, 7, 9, 10, 20, 23. move number : \underline{12}, 14, 15. new line: \underline{22}, 23. next move: \underline{15}. no more candidates : \underline{13}. number of legal knight moves : \underline{11}, 13, 17. number of squares : \underline{6}, 8, 14. output : \underline{2}, 22. print integer : \underline{22}, 23. print string : \underline{22}, 23. record move: \underline{14}. row : 8, \underline{12}, 16. row deltas : 16, \underline{17}, 18. set square to: \underline{10}, 14, 15. successful : \underline{12}, 13, 14, 15, 19, 23, \underline{24}. targ col : \underline{10}, 14, 15, 16. targ row : \underline{10}, 14, 15, 16. target empty : \underline{10}, 14. target position valid : \underline{10}, 14. target square: \underline{10}, 14. true: 13, 14. try knight move: \underline{12}, 15, 19. valid row or column: \underline{10}.

: 1. width: \underline{22}. Wirth, Niklaus: 1. write: 22. write ln: 22.

12  NAMES OF THE SECTIONS  The Knight’s Tour §25

⟨ Constants of the program 6 ⟩ Used in section 2. ⟨ Initialize the data structures 18 ⟩ Used in section 2. ⟨ Initialize the knights tour board 9 ⟩ Used in sections 19 and 20. ⟨ Local variables of the knight’s tour procedure 10, 11 ⟩ Used in section 12. ⟨ Perform the knight’s tour and print the results 19, 20 ⟩ Used in section 2. ⟨ Print the results of the knight’s tour 23 ⟩ Used in sections 19 and 20. ⟨ Record the move if acceptable and try to make further moves; set successful if solution found 14 ⟩

Used in section 13.

⟨ Recursive procedure definitions 12 ⟩ Used in section 2. ⟨ Set the coordinates of the next move as defined by the rules of chess 16 ⟩ Used in section 13. ⟨ Try further knight moves and erase this move if not successful 15 ⟩ Used in section 14. ⟨ Try the moves possible from the current position until solution found or all have been tried 13 ⟩

Used in section 12.

⟨ Types of the program 7 ⟩ Used in section 2. ⟨ Variables of the program 8, 17, 24 ⟩ Used in section 2.

The Knight’s Tour

Section Page

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 The knight’s tour . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3 The output phase . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 10 Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 11