'''
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)
            if not found:
                print "There are no solutions for this board when starting from", y, x, "tried", tries, "combinations"
            else:
                print "Found", len(found), "complete boards after", tries, "tries when starting from", y, x
                for board in found:
                    print board
                sys.exit()