File information
Filename: knight.py Uploaded: Sun, 12th Sep 2010 17:48:31
Size (bytes): 3.78 KiB md5 checksum: 5fc0cc10ef6a01eb14861dc9b943ccc1
Description:

A brute force implementation of the touring knight problem.

```'''
Created on 4 Sep 2010

@author: doug@neverfear.org
'''
import sys

class Board(object):
def __init__(self, height = 8, width = 8, board = None):
self._board = []
if board is None:
self.height = height
self.width  = width
for y in xrange(self.height):
self._board.append([False] * self.width)
else:
self.height = board.height
self.width  = board.width
for y in xrange(self.height):
row = list()
for x in xrange(self.width):
row.append(board.get(y, x))
self._board.append(row)

def set(self, y, x, value):
self._board[y][x] = value

def get(self, y, x):
return self._board[y][x]

def __len__(self):
return width * height

def copy(self):
return Board(board = self)

def isValidPosition(self, (y, x)):
return (width > 0) and (y >= 0 and y < height) and (x >= 0 and x < width)

def isValidMove(self, (y, x)):
if self.isValidPosition((y, x)):
return not bool(self.get(y, x))
return False

def __str__(self):
s = ""
for y in xrange(self.height):
s += ("+---" * self.width) + "+\n"
row = "|"
for x in xrange(width):
row += "% 3d|" % (board.get(y, x))
s += row + "\n"
s += ("+---" * width) + "+\n"
return s

def IsBoardComplete(board, depth):
return len(board) == depth

def PossibleMoves(board, position):
# +-+-+-+-+-+
# | |x| |x| |
# +-+-+-+-+-+
# |x| | | |x|
# +-+-+-+-+-+
# | | |o| | |
# +-+-+-+-+-+
# |x| | | |x|
# +-+-+-+-+-+
# | |x| |x| |
# +-+-+-+-+-+

y, x  = position
Moves = []
for yoffset in [-1, 1]:
for xoffset in [2, -2]:
newPosition = y + yoffset, x + xoffset
if board.isValidMove(newPosition):
Moves.append(newPosition)
for yoffset in [-2, 2]:
for xoffset in [1, -1]:
newPosition = y + yoffset, x + xoffset
if board.isValidMove(newPosition):
Moves.append(newPosition)
return Moves

def Tour(board, position, tryCount = 0, found = None, sequence = 1):
y, x        = position
board.set(y, x, sequence)
tryCount   += 1

if found is None:
found = []

if IsBoardComplete(board, sequence):
if board in found:
return tryCount, found
found.append(board.copy())
print "Board complete"
print board
board.set(y, x, False) # unset last position
return tryCount, found

Moves = PossibleMoves(board, position)
for newPosition in Moves:
tries, _ = Tour(board, newPosition, tryCount, found, sequence + 1)
tryCount += tries

board.set(y, x, False)
return tryCount, found

if __name__ == '__main__':
width, height = 3, 4
for y in xrange(height):
for x in xrange(width):
startPosition = (y, x)
board = Board(width = width, height = height)
print "Starting from position", y, x
tries, found = Tour(board, startPosition)