Welcome, guest | Sign In | My Account | Store | Cart

Knight's Tour using Warnsdorff Algorithm.

Python, 40 lines
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40``` ```# 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 ```
 Created by FB36 on Mon, 17 Dec 2012 (MIT)

### Required Modules

• (none specified)