Brute forcing the touring knight problem

The touring knight problem is a maths problem that takes the movement of a knight in chess and attempts to find a path around a two dimensional board such that every single square is visited exactly once.

There are more sofisicated solutions but as you might have imagined, brute forcing is the most naive approach to solving this problem.

By trying every possible combination of legal move from your current position you can follow through every legal path and check whether you've completed the board or not.

It starts with a board.

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

Which combined with the number of squares we've so far visited allows us to determine if we've visited everywhere.

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

Simples. Now we need a method to determine out possible options from any square.

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

The main logic of the tour is a recursive function that attempts every path and upon completion appends the path to a list of successful paths. We carry around how many paths we've calculated for fun.

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

We initialise and kick things off by iterating over every possible starting position to get every possible way to complete our board.

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()

This is something I toyed with on one of my long journeys to London and back that I have to do every week.

Full source code