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

Solves Knight's Tour Problem using Warnsdorff's Algorithm for every square on the chessboard of arbitrary size.

It colors each initial square with a color that depends on the final square coordinates. (This is a method used to create fractals.) Many different formulas maybe used for coloring (based on abs/rel x/y/dist/ang).

Calculating each tour in full creates a highly chaotic image (and takes hours). So I added maxItPercent to cut-off tours earlier. (Using %10 creates an image that has both ordered and chaotic regions.)

Python, 57 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 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57``` ```# 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") ``` Created by FB36 on Tue, 18 Dec 2012 (MIT)