Welcome, guest | Sign In | My Account | Store | Cart
# 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

History