knight_tour.py

import random
n = 8


def printBoard(n, board):
    for i in range(n):
        for j in range(n):
            print(board[i][j], end=' ')
        print()


def validMove(next_move_x, next_move_y, board):
    if (not next_move_x < 0 and not next_move_y < 0 and next_move_x < n and next_move_y < n and board[next_move_x][next_move_y] == -1):
        return True
    return False


def validNeighbor(neighbor_x, neighbor_y, new_move_x, new_move_y):
    if (neighbor_x != new_move_x and neighbor_y != new_move_y):
        return True 
    return False 


def countNeighbors(new_move_x, new_move_y, moves_x, moves_y, board):
    neighbors = 0

    for i in range(8):
        neighbor_x = new_move_x + moves_x[i]
        neighbor_y = new_move_y + moves_y[i]

        if (validMove(neighbor_x, neighbor_y, board)):
            if (validNeighbor(neighbor_x, neighbor_y, new_move_x, new_move_y)):
                neighbors += 1

    return neighbors


def findNextMove(moves_x, moves_y, curr_pos_x, curr_pos_y, tour, board, neighbors_availability):
    if (tour == 8 ** 2):
        return True

    next_move_x = None
    next_move_y = None

    # walk through board
    for i in range(8):
        new_move_x = curr_pos_x + moves_x[i]
        new_move_y = curr_pos_y + moves_y[i]

        if (validMove(new_move_x, new_move_y, board)):
            # look for available move with less possible future moves
            neighbors_available = countNeighbors(new_move_x, new_move_y, moves_x, moves_y, board)
            if (neighbors_available < neighbors_availability):
                neighbors_availability = neighbors_available
                next_move_x = new_move_x
                next_move_y = new_move_y

    tour += 1
    board[next_move_x][next_move_y] = tour

    return findNextMove(moves_x, moves_y, next_move_x, next_move_y, tour, board, 8)


def solveKnight():
    moves_x = [-2, -2, -1, -1, 2, 2, 1, 1]
    moves_y = [-1, 1, -2, 2, -1, 1, -2, 2]

    board = [[-1 for i in range(n)]for j in range(n)]

    # set knight on first tour and start position traveled to 1
    starting_pos_x = random.randint(0, 7)
    starting_pos_y = random.randint(0, 7)

    tour = 1
    board[starting_pos_x][starting_pos_y] = 1

    findNextMove(moves_x, moves_y, starting_pos_x, starting_pos_y, tour, board, 8)
    return printBoard(n, board)

if __name__ == '__main__':
    solveKnight()