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.

tour

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
Advertisements

One thought on “Knight’s Tour and Warnsdorff’s Rule

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s