KnightsTour.py

import time


# Prints the board for display purposes
def printBoard(board):
    for i in board:
        for j in i:
            print(j, end="\t")
        print()
    return


# Calculates knights possibilities of movement at certain position
# Runs recursively, and stops when there are no options left for the knight to move
def solveKnightsTourPosition(board, curr_x, curr_y, pos):

    # printBoard(board)

    # All options that a knight can move
    move_x = [2, 1, -1, -2, -2, -1, 1, 2]
    move_y = [1, 2, 2, 1, -1, -2, -2, -1]
    if pos == len(board) ** 2:
        return True

    # Evaluating all options of which a knight can move
    for i in range(8):
        new_x = curr_x + move_x[i]
        new_y = curr_y + move_y[i]
        if 0 <= new_x < len(board) and 0 <= new_y < len(board) and board[new_x][new_y] == -1:
            board[new_x][new_y] = pos
            if solveKnightsTourPosition(board, new_x, new_y, pos + 1):
                return True
            board[new_x][new_y] = -1
    return False


# Main function to run the knights tour
# Inputs one size of the board
# Returns 2D array of integers which represent the order of the knights tour
def knightsTour(size):
    board = [[-1 for _ in range(size)] for _ in range(size)]

    board[0][0] = 0
    pos = 1

    # Makes sure there is at least
    if not solveKnightsTourPosition(board, 0, 0, pos):
        return []
    else:
        return board


if __name__ == "__main__":
    print('Start')
    size = 6
    try:
        print("-----------------------")
        start = time.time()
        result = knightsTour(size)
        printBoard(result)
        print("-----------------------")
        print(f"{size} Duration:  {time.time() - start: 5} seconds")
    except:
        print(f"Failed: {size}")