Knight's tour puzzle with Warnsdorff's rule heuristic

knights_tour.py

#
# knights_tour.py - knight's tour puzzle
#
# 2014-02-06 Steven Wart created this file
#

from sys import stdout
from math import sqrt

# Print out an 8x8 chessboard showing the positions of the pieces
def draw_board(board):
	n = int(sqrt(len(board)))
	stdout.write("   ")
	for col in range(n):
		stdout.write("  %d  " % col)

	for cell in range(len(board)):
		if ((cell % n) == 0):
			stdout.write('\n')
			stdout.write("   +")
			for col in range(n):
				stdout.write("----+")
			stdout.write('\n')
			stdout.write("{0:>2} |".format(cell / n))

		# traversal path starts at 1
		if (board[cell] > 0):
			stdout.write("{0:>3} |".format(board[cell]))
		else:
			stdout.write("    |")

	stdout.write('\n')
	stdout.write("   +")
	for col in range(n):
		stdout.write("----+")
	stdout.write('\n')


# Add a set of coordinates to the move list, if it is a valid location
def append_move(row, col, moves, n):
	if row >= 0 and row < n and col >= 0 and col < n:
		moves.append(row * n + col)
 
# Make a list of possible destinations for each cell on the board
def initialize_knight_moves(n):
	relative_moves = [[-2, -1],[-1, -2],[1, -2],[2, -1],[-2, 1],[-1, 2],[1, 2],[2, 1]]
	knight_moves = [[] for x in range(n * n)]

	for src in range(n*n):
		row = src % n
		col = src / n
		for rel in relative_moves:
			append_move(rel[0]+col, rel[1]+row, knight_moves[src], n)

	return knight_moves

# display all possible knight moves for an 8x8 board
def display_knight_moves(knight_moves):
	n = 8
	for pos in range(n*n):
		board = [0 for x in range(n*n)]
		board[pos] = 1
		for dest in knight_moves[pos]:
			board[dest] = 2
		draw_board(board)

# knight_moves = initialize_knight_moves(8)
# for cell in range(len(knight_moves)):
# 	print cell, knight_moves[cell]

# tour from a starting point to traverse the entire board
# step is the step number of the traversal
# return True if the traversal can complete, False otherwise
def traverse(start, board, step=1, visited=[]):

	visited.append(start)
	board[start] = step

	if step == len(board):
		return True

#
# Warnsdorff's rule: search the paths with the smallest out-degree first
#
	def sort_key(dest):
		return len(knight_moves[dest])

	paths = [dest for dest in knight_moves[start] if dest not in visited]
	sorted_paths = sorted(paths, key=sort_key)

	for dest in sorted_paths:
		if not dest in visited:
			if traverse(dest, board, step+1, visited):
				return True

	visited.pop()
	board[start] = 0
	return False

#
# This works well for n up to 7, but according to http://en.wikipedia.org/wiki/Knight's_tour
# A brute-force search for a knight's tour is impractical on all but the smallest boards;
# for example, on an 8x8 board there are approximately 4x10^51 possible move sequences, and
# it is well beyond the capacity of modern computers (or networks of computers) to perform
# operations on such a large set.
#
# However, by employing Warnsdorff's rule, where we search the paths with the smallest out-degree
# first, the 8x8 tour returns in 0.6 seconds. Without this optimization it ran for over 2 hours
# without returning a result. With this optimization even an 11x11 board can be traversed in 
# less than one second. 10x10 is slower, but it finishes in 12.3 seconds
#
def knights_tour(n):
	global knight_moves

	knight_moves = initialize_knight_moves(n)
	board = [0 for x in range(n*n)]
	if not traverse(0, board):
		print "No traversal found"
	else:
		draw_board(board)

knights_tour(8)