# Knight's Tour using Warnsdorff's Rule
# http://en.wikipedia.org/wiki/Knight's_tour
# FB - 20121216
from heapq import heappush, heappop # for priority queue
import random
import string
cbx = 8; cby = 8 # width and height of the chessboard
cb = [[0 for x in range(cbx)] for y in range(cby)] # chessboard
# directions the Knight can move on the chessboard
dx = [-2, -1, 1, 2, -2, -1, 1, 2]
dy = [1, 2, 2, 1, -1, -2, -2, -1]
# start the Knight from a random position
kx = random.randint(0, cbx - 1)
ky = random.randint(0, cby - 1)
for k in range(cbx * cby):
cb[ky][kx] = k + 1
pq = [] # priority queue of available neighbors
for i in range(8):
nx = kx + dx[i]; ny = ky + dy[i]
if nx >= 0 and nx < cbx and ny >= 0 and ny < cby:
if cb[ny][nx] == 0:
# count the available neighbors of the neighbor
ctr = 0
for j in range(8):
ex = nx + dx[j]; ey = ny + dy[j]
if ex >= 0 and ex < cbx and ey >= 0 and ey < cby:
if cb[ey][ex] == 0: ctr += 1
heappush(pq, (ctr, i))
# move to the neighbor that has min number of available neighbors
if len(pq) > 0:
(p, m) = heappop(pq)
kx += dx[m]; ky += dy[m]
else: break
# print cb
for cy in range(cby):
for cx in range(cbx):
print string.rjust(str(cb[cy][cx]), 2),
print