Knight Rider

December 2, 2011

A classic problem in computing is the Knight’s Tour, in which a knight visits every square on a chessboard; the objective is to list the knight’s moves in order. There are two types of tours: cyclic (or closed), in which the final square is a knight’s jump away from the starting square, and acyclic (or open), where the final square is unconstrained. Knight’s tours are often given for generalized chessboards, such as 5-by-5 or 10-by-12, in addition to the standard 8-by-8 chessboard.

The simple solution is via backtracking: Make any valid move. Then make another move. And so on, until you have completed the tour. If at any point there are no valid moves, backtrack and choose an alternate move. The diagram below shows a sample 8-by-8 cyclic tour, and the list below the board shows the list of squares using row and column coordinates in the order they are visited:

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

0/0 1/2 0/4 1/6 3/7 5/6 7/7 6/5
5/7 7/6 6/4 7/2 6/0 4/1 2/0 0/1
1/3 0/5 1/7 2/5 0/6 2/7 4/6 6/7
7/5 6/3 7/1 5/0 6/2 7/0 5/1 3/0
1/1 0/3 1/5 0/7 2/6 4/7 6/6 7/4
5/5 3/6 4/4 3/2 2/4 4/5 5/3 3/4
2/2 1/0 0/2 1/4 3/5 4/3 3/1 2/3
4/2 5/4 7/3 6/1 4/0 5/2 3/3 2/1

Since the number of possible tours is very large, the simple solution will likely take a long time. In 1823, H. C. von Warnsdorff proposed the following heuristic: sort the valid moves according to the number of their successor moves, choosing first the move that has the least number of successors (choose randomly in the event of a tie). On small chessboards, say less than 10-by-10, Warnsdorff’s heuristic frequently eliminates backtracking entirely.

Your task is to write a program that finds a single Knight’s Tour on an n-by-n chessboard. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
1 Comment »

One Response to “Knight Rider”

  1. Jos Koot said
    December 5, 2011 at 4:30 PM

    You can find a somewhat more elegant version on http://www.telefonica.net/web2/koot/knight-rider-0.rkt. It requires DrRacket though. In this version the path-finder is abstracted from the actual problem. It could also be used for other computations requiring backtracking. It should not be too difficult to adapt the code to programming praxis.
    Best wishes, Jos Koot

Leave a comment