# Knight’s Tour and Warnsdorff’s Rule

In class, we briefly discussed the Knight’s Tour in the context of Steve Wozniak’s anecdote about his first program. The Knight’s Tour, as you may remember, allows a knight to traverse the entire chessboard while touching each square exactly once. At first, Wozniak implemented a brute-force solution but realized that it would take approximately $10^{25}$ years to complete, which is much longer than the estimated age of the universe $13.82$ billion years old. Wozniak’s experience quickly taught him that a good algorithm vastly trumps a fast computer.

How do we go about solving the Knight’s Tour then?

Warnsdorff’s Rule

One approach to solving the Knight’s Tour is Warnsdorff’s rule, which stipulates that we move the knight such that it advances to a square which has the fewest onward moves from that particular starting location. Drawing from an excellent paper by Doug Squirrel, I was able to calculate a Knight’s Tour for a board of standard size 8×8.

A example of an open Knight’s Tour on a standard 8×8 board.

Extensions
Warnsdorff’s Rule applies to boards of size 50 or less but experiences difficulty finding an tour past that point. Two improvements (W+ and W2) have been introduced as better methods that draw on the same principles as Warnsdorff’s Rule.

Additionally, in the event of a tie between two squares, various tie-breaking algorithms have been developed to address that situation.

```# Knight's Tour using Warnsdorff's Rule
# http://en.wikipedia.org/wiki/Knight's_tour

# height and width of the chessboard
height = 8
width = 8

cb = [[0 for x in xrange(height)] for y in xrange(width)] # chessboard

# possible direction combinations for knight
dx = [-2, -1, 1, 2, -2, -1, 1, 2]
dy = [1, 2, 2, 1, -1, -2, -2, -1]

# start the Knight randomly on board
kx = random.randint(0, width - 1)
ky = random.randint(0, height - 1)

for k in xrange(width * height):
cb[ky][kx] = k + 1
p_queue = [] # available neighbors queue
for i in xrange(8):
nx = kx + dx[i]; ny = ky + dy[i]
if nx >= 0 and nx < width and ny >= 0 and ny < height:
if cb[ny][nx] == 0:
# count the available neighbors of the potential next stops
ctr = 0
for j in xrange(8):
ex = nx + dx[j]
ey = ny + dy[j]
if ex >= 0 and ex < width and ey >= 0 and ey < height:
if cb[ey][ex] == 0:
ctr += 1
heappush(p_queue, (ctr, i))
# move to the neighbor that has min number of available neighbors
if len(p_queue) > 0:
(p, m) = heappop(p_queue)
kx += dx[m]
ky += dy[m]
else: break

# print cb
for cy in xrange(height):
for cx in xrange(width):
print string.rjust(str(cb[cy][cx]), 2),
print
```