# 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