Welcome, guest | Sign In | My Account | Store | Cart
# Knight's Tour Map using Warnsdorff's Rule
# http://en.wikipedia.org/wiki/Knight's_tour
# FB - 20121217
from heapq import heappush, heappop # for priority queue
import random
import time
from PIL import Image
imgx
= 500; imgy = 500 # width and height of the image
cbx
= 100; cby = 100 # width and height of the chessboard
maxItPercent
= 10 # %100 => calculate the full tours
maxIt
= cbx * cby * maxItPercent / 100
image
= Image.new("RGB", (cbx, cby))
pixels
= image.load()
while True:
    mr0
= 2 ** random.randint(3, 6); mr1 = 256 / mr0
    mg0
= 2 ** random.randint(3, 6); mg1 = 256 / mg0
    mb0
= 2 ** random.randint(3, 6); mb1 = 256 / mb0
   
if mr0 != mg0 and mr0 != mb0 and mg0 != mb0: break
# 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]
t
= time.time()
for cy in range(cby):
    pc
= 100.0 * cy / (cby - 1) # percent completed
    tp
= time.time() - t # time passed in seconds
   
print "%" + str(int(pc)), "in " + str(int(time.time() - t)) + "s.",
   
if pc > 0:
       
print str(int(100.0 * tp / pc - tp)) + "s remains..."
   
else: print
   
for cx in range(cbx):
        cb
= [[0 for x in range(cbx)] for y in range(cby)] # chessboard
        kx
= cx; ky = cy # initial position of the knight
       
for k in range(maxIt):
            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
       
# color the initial position according to final position
       
# (its absolute/relative coordinates/distance/direction maybe used)
        c
= 256 * (cbx * ky + kx) / (cbx * cby - 1)
        pixels
[cx, cy] = (c % mr0 * mr1, c % mg0 * mg1, c % mb0 * mb1)
image
= image.resize((imgx, imgy))
image
.save("KnightsTourMap.png", "PNG")

History