Knights Tour with Backtracking

Question

I'm trying to write a Python program which will solve the Knight's Tour problem using backtracking. For those unfamiliar: "The knight is placed on the first square of an empty chess board and, moving according to the rules of chess, must visit each square exactly once."

My code works mostly but not completely. It usually gets the 7th move and then returns an unfinished board. Why?

board = [
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0]]

def move(x, y, count, move_x, move_y):
    if count == len(board)**2:
        return True
    for i in range(8):
        if is_valid(x + int(move_x[i]), y + int(move_y[i]), board):
            if move(x + move_x[i], y + move_y[i], count + 1, move_x, move_y):
                board[x][y] = count
                return True
    return False
    

def print_board(bo):
    for i in range(len(bo)):
        for j in range(len(bo[0])):
            if j == (len(board[0]) - 1):
                print(bo[i][j])
            else:
                print(bo[i][j], end = " ")


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



def solve(bo):
    print_board(board)
    move_x = [1, 2, 2, 1, -1, -2, -2, -1]
    move_y = [2, 1, -1, -2, -2, -1, 1, 2]
    counter = 1
    x_loc = 0
    y_loc = 0

    if not(move(x_loc, y_loc, counter, move_x, move_y)):
        print("No solution")
    else:
        print("                 ")
        print_board(board)

solve(board)
    

Answer 1

• The recursive call to move() should come after setting board[x][y] = count.
  • Moreover, if move() returns false, then you should have board[x][y] = 0
• In fact, count does not need to be stored in each board cell. It just needs to be passed and incremented in each recursive call. You can use a boolean indicating whether a cell has been visited or not.
• Final thoughts: There are 2^64 board states and many more paths to hit failure states repeatedly. As such, the failure states should be stored in a hash to avoid searching the failed paths repeatedly.