Knight tours on a chess board using MAPLE

The knight package contains several routines designed to find knight tours on a chess board.

A knight tour is a sequence of legal knight moves which does not move onto a square previously occupied. A complete knight tour is one in which every square of the chess board has been visited exactly once. A closed knight tour is a complete tour which returns to the square it began. An open knight tour is a complete tour which does not return to it's starting position. The routines in this package only search for open knight tours (there is a technique due to Bertrand-Euler for obtaining a closed tour from an open one - see the book by Ball and Coxeter listed at the end of this worksheet). Some of the procedures in this package include

1. a routine to list all legal moves from a given square to a square it hasn't been to before,

2. some interactive routines to perform random searches for open knight tours,

3. implementations of Warnsdorff's rule (which says, roughly speaking, you should always make the "worst" move possible to get a complete knight tour),

4. a procedure to draw a knight tour as an array of numbers representing the move number,

5. a procedure to add to a graph the vertices representing the moves it can make next,

6. some backtracking routines.

We shall illustrate some of these. First, load the package

> with(networks):
with(share):
readshare(knight,games); #in MAPLEV4

See ?share and ?share,contents for information about the share library

A simple initialization routine defines some global variables, such as a beginning position AT :

> knighttour():
AT;
Been;

The procedure cango tells you the moves you can visit from a given position. It returns a list of moves which are (a) legal, and (b) have not been visited before (in the sense that they do not belong to the list of moves specified by the gobal variable Been ). The order of the moves in the list returns by cango is as follows: from [x,y], begining with the upper right-hand square at [x+1,y+2] and continuing clockwise, cango returns all moves satisfying (a) and (b).

We may manually change the global variable Been to draw an example tour:

> cango(AT);
This tells you where you can go from AT .
Been:=[AT];
This resets Been so that cango knows where you've been for the next move.
cango([2,3]);
This tells you where you can go from [2,3] (it knows you've been to [1,1]).
Been:=[AT,[2,3]];
drawtour();

We have already created (in knighttour(); ) a graph called KnightTree:

> vertices(KnightTree);
edges(KnightTree);

There is a procedure to add the vertices and edges associated to all the moves returned by the procedure cango :

> Been:=[]:
(We must reset the global variable Been so that cango thinks we are just starting our tour.)
addnodes(AT);
vertices(KnightTree);
edges(KnightTree);
draw(KnightTree);

Notice that the vertices are indexed by the position on the chess board. The graph of possible moves after only two moves is already getting to look complicated:

> Been:=[1,1]:
addnodes([3,2]);
addnodes([2,3]);
vertices(KnightTree);
edges(KnightTree);
draw(KnightTree);

The nextmove routine randomly picks a move (and changes the random "seed" each time) and then updates the global variable Been :

> Been:=[];
nextmove([1,1]);
Been;

You may want to try running the above sequence several times to convince yourself that it really can choose different moves each time.

The routine knightmoves simply tries to reiterate the nextmove procedure until either it finds a complete tour or no more moves are found. For example, to try to find a tour 60 moves long, simply type:

> Been:=[]:
knightmoves(60,AT);
drawtour();

The number of moves it actually found is obtained by either finding the largest number in the above array or by entering nops(Been);

You may run the above sequence several times to see what different kinds of knight tours are possible. There is a procedure to do this for us. To ask MAPLE to run knightmoves(60,AT); say 20 times and return the largest tour found, use the interactive findtour routine. You must enter the number of search tries (in this case 20) yourself:

> Been:=[];
findtour(60,AT);

Enter number of searches: 20;

Incidently, I don't know what the expected length of a random tour is or even if the expected value of this random (Markov?) process exists. If it exists, some experiments suggest it appears to be approximately 33, 34, or maybe 35.

In any case, to find the picture of the largest tour found in the above search, you can use drawtour(); as before.

> drawtour();

So far, these routines have been simple random move strategies. The searchknightmoves routine combines this random move strategy with a backtracking routine. To try to find a move say 55 moves long, type (note you must enter the number of search tries, in this case 10, yourself):

> Been:=[]:
searchknightmoves(55,AT);

How many tries? (use semicolon) 10;

What is the maximum tour found and what does it look like? Enter nops(Been);drawtour();

In general, the list of knight moves returned by cango is of length between 0 (if it is empty) and 8. Recall that the ordering in this list is clockwise, starting at the upper right-hand square. We may specify a knight tour by an initial position [x0,y0] and a sequence of integers m1, m2, ... (with each integer taken between 1 and 8 inclusive) as follows. We define the tour inductively: The 0-th move is [x0,y0]. Suppose we are now at the i-th move [x,y] and suppose that M:=cango([x,y]); has m elements with m>0 (if m=0 then we can go no further and our tour is at an end). Then the (i+1)-st move is then k-th element of the list M, where k=m.i (mod m) (the representatives of the residue classes of m are taken to be 1, ..., m so this move always exists). Let us call this notation for a knight tour the list notation .

There is a knight routine to try to move a knight along any given list. For example, to try to make the "first move" 30 times starting from [1,1], simply type:

> L:=[seq(1,i=1..30)]:
listmove(L,AT);
drawtour();

We cannot choose the "first move" 64 times in a row. More generally, we will have to have incredible luck to find a complete knight tour by guessing its list. However, we can combine this listmove routine with a backtracking routine:

> Been:=[];
L:=[seq(1,i=1..40)]:
listmove(L,AT);
Been:=[];
listmove_with_bt(L,AT,5);
The routine will try to make all 40 moves by backtracking 5 times .
drawtour();

Last but not least, we can get a complete tour using the warnsdorff routines. There are two versions, each using Warnsdorff's rule : at each stage one should make a move which has the fewest alternatives to choose from. Sometimes this still leaves several moves to choose from. One routine, warnsdorff , always chooses the the first such move:

> warnsdorff(AT);
(The global variable Been is automatically reset.)
drawtour();

The second routine, random_warnsdorff , randomly chooses one of them:

> random_warnsdorff(AT);
drawtour();

REFERENCES

W.W. R. Ball and H.S.M. Coxeter, Mathematical Recreations and Essays , 13th ed, Dover, New York, 1987