Knight's Tour

THE KNIGHT’S TOUR

If you place a knight on the chess board and move him so that he lands on every square just once, then you have made a Knights Tour. You can use the moves to encipher a message by transposition.

There are two sections in this article:
- a description of the Knight’s Tour and how it may be created and used for encryption;
- a working programs that makes the tour of your choice.

1.0 Description
There are over 10 million million different ways for the Knight to make his tour. Below is an example. The Knight was placed initially in row=4,column=6 which is shown as position 00. He moves to position 01 at [6,7] then to 02 at [7,5] and so on until he ends at position 63 [1,4].

     0  1  2  3  4  5  6  7
0   56 25 40 11 36 23 62 13
1   41 10 55 24 63 12 35 22
2   26 57 52 39 48 37 14 61
3   09 42 27 54 51 60 21 34
4   28 53 58 47 38 49 00 15
5   05 08 43 50 59 18 33 20
6   44 29 06 03 46 31 16 01
7   07 04 45 30 17 02 19 32

There are two types of Knight‘s Tour: ‘closed’ where the final position is within a move of the initial position; and the ‘open’ Tour when the Knight finishes up at some other location. There are more open Tours than closed ones, by a factor of approximately six.

1.1 Using the Knight’s Tour for encryption

A plaintext can be transposed by following the Tour. The text is written in row by row and then taken out in order of the Knight’s Tour, from position 00 to position 63. Here is an example using the Tour above:

Plaintext    
NEARLYEV      
ERYINVEN      
TOROFACI      
PHERSYST      
EMFIRMLY     
BELIEVES      
ITISIMPR      
EGNABLEX      

Plaintext: NEARLY EVERY INVENTOR OF A CIPHER SYSTEM FIRMLY BELIEVES IT IS IMPREGNABLE X.
Ciphertext: LRLSG BIEEP RRVVC YPBVE SSNYI ETEET AMXET ELARO AEHLI NIIFM ISRMR YNOFE YIEN.

1.2 How to make a Knight’s Tour.

Warndorff proposed a rule that works in most cases. Start anywhere on the board. Move to a square from which there are the fewest number of further moves. If there are two or more such moves then choose one at random.
This rule gives a complete tour in some 98% of cases. Because it can fail it is strictly a ‘heuristic’ rather than an ‘algorithm’. Other people have found slight modifications that increase the success rate: for example when more than one square qualifies, choose the square furthest from the centre.

It is a simple task to program the computer to follow Warndorff’s rule. In the very infrequent occasion that it fails to make a complete Tour, then the program just repeats until it does.

My program is an interactive one and the interface looks like this:

The user chooses whether an open or closed Tour is required, inputs the start row and column and also inputs a seed for the random number generator. Different seeds produce different squares. You may run the program here. 

The program may produce a closed or an open Tour. On testing over a wide range of starting positions, I have found:

Open Tour typically 84%
Closed Tour         14
Failure              2