The Knight’s Tour

I saw an online game around the knight’s tour problem the other day and it made me think of mathematics of chess puzzles. You know… Domination, independence (eight queens) etc. I thought it would be a good way to go back to writing some Python code after a long break.

The “Knight’s Tour” is a problem in which the objective is to move a knight, starting from any square on a chessboard to every other square landing on each square only once. Euler is said to be the first one to study this problem in 1759 on a 8 x 8 board. A knight’s tour is  a Hamiltonian path. A closed tour  is a Hamiltonian cycle i.e. the last square visited is also reachable from the first square by a single knight’s move. For all even n >= 6 there exists a closed knight’s tour on an n x n chessboard and an open knight’s tour if n >= 5.

We can create a matrix of size n x n with not visited cells filled with zeroes and every other cell to be filled with the order visited in the tour.

board = []
board_size = -1

def initiateBoard (board_dimensions):
    global board
    global board_size
    global knights_moves
    board_size = board_dimensions
    for i in range(0, board_size):
        board.append(board_size*[0]) #untouched board

Given knight’s behavior the possible moves relative to knight’s location are

knights_moves = ((-2,-1),(1,2),(2,-1),(-2,1),(2,1),(-1,2),(1,-2),(-1,-2))

But depending on where knight is on the board, not all moves will work so we should check whether a certain point is on the board and not visited.

def isAvailable(x, y):
    if x < len(board) and y < len(board[0]) and \
       x >= 0 and y >= 0 and board[x][y]==0:
        return True
    else:
        return False

Naïve backtracking is a possible solution but for an 8×8 board, there exist 33,439,123,484,294 un-oriented paths so instead I will use Warnsdorff’’s rule to get to the solution a bit quicker. According to this heuristic method, knight always proceeds to the square from which it will have the fewest onward moves.

def getPossibleMoves(x, y):
     possible_moves = []
     for move in knights_moves:
        cx,cy = x+move[0], y+move[1]
        if isAvailable(cx,cy):
            possible_moves.append((move[0],move[1]))
     return possible_moves  

def getNumMoves(x, y):
     return len(getPossibleMoves(x, y))
 
def getNextMove (numMoves):
    smallestIndex = 0
    if not numMoves:    #Nowhere to go
        drawBoard()    #Show the results                     
        sys.exit(1)
    smallest = numMoves[0]
    for i in range(len(numMoves)):
        if numMoves[i] < smallest:
            smallest = numMoves[i]
            smallestIndex = i

    return smallestIndex

And finally the recursion to find the complete path

def solve (x,y,num_move):
    assert board[x][y] == 0
    board[x][y] = num_move                                 
    possible_moves = getPossibleMoves(x,y)
    numOfMoves = []     
    for move in possible_moves:
        numOfMoves.append(getNumMoves(x+move[0],y+move[1]))
    nextMove = possible_moves[getNextMove(numOfMoves)]
    solve(x+nextMove[0],y+nextMove[1],num_move+1)   

def getKnightsPath (board_dimensions):
    initiateBoard (board_dimensions)
    solve(0,0,1)

I’m leaving drawBoard() function to your imagination, but here is what I got using matplotlib.path.

For scaling to very large boards a divide-and-conquer solution would be necessary. If I can find some time, I’d also like to share a parallel implementation here.

Advertisements