Como resolver o Knight's Tour Problem com a Warnsdorff's Rule

O Knight's Tour problem é um problema que se baseia em uma sequência de movimentos num tabuleiro de xadrez, os movimentos são feitos apenas pelo Cavalo (Knight) e seguindo as regras do xadrez o objetivo é fazer um "Tour", ou seja, visitar todas as casas do tabuleiro, porém, só é permitido passar pelas casas apenas uma ÚNICA vez.

Existem várias maneiras de resolver esse problema algumas delas são:

• Brute Force
• Divide-and-conquer Algorithms
• Neural Network
• Warnsdorff's Rule

Warnsdorff's Rule é uma heurística (procedimento que auto-descobre e aplica um método, sem a garantia de ser perfeito ou racional, mas que é suficiente para chegar a um resultado seja ele aproximado ou imediato).

Imagine o seguinte cenário: Um tabuleiro padrão 8x8 e a posição inicial do Cavalo atribuída randomicamente, partindo da posição inicial vamos olhar para todas as casas que o Cavalo pode se mover, partindo dessas casas disponíveis vamos olhar novamente ao redor do cavalo e contar quantas casas temos disponíveis. A casa que tiver o menor numero de futuras casas disponíveis (vamos chama-las de Neighbors) é a vencedora e o Cavalo se move até ela, faremos isso até o Tour ser finalizado;

O nosso tabuleiro será representado por um Array 2D, se quiséssemos posicionar o Cavalo igual na imagem acima (na casa B4) em um Array 2D, seria assim board[4][1]. Você pode ver que temos um Array board com 8 Arrays representando o eixo X e cada Array com 8 elementos representando o eixo Y.

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

Iniciamos todas as casas do tabuleiro com o valor -1 assim fica fácil na hora de saber se o Cavalo ja passou ou por aquela casa.

No xadrez o Cavalo faz um movimento em L e para representar isso no nosso código vamos utilizar 2 arrays moves_x = [] e moves_y = [] neles teremos todos os possiveis movimentos que o Cavalo pode fazer

    moves_x = [-2, -2, -1, -1, 2, 2, 1, 1]
    moves_y = [-1, 1, -2, 2, -1, 1, -2, 2]

esses números parecem aleatórios e podem soar um pouco confuso, mas calma... tudo fará sentindo.

na ilustração acima fica bem fácil de entender nela temos todos os movimentos em L possiveis, também está destacado em verde o movimento do Cavalo para a casa C7. Todos os movimentos são formados pelo calculo dos valores moves_x e moves_y sobre o os valores X e Y da casa que o Cavalo estiver. Por exemplo para mover da casa D5 (board[3][3]) para a C7 teriamos: X = 3 - 2, Y = 3 - 1 pronto agora já temos nossa nova posição board[1][2].

O movimento que fizemos acima só foi válido porquê o cavalo está no centro do tabuleiro, se o Cavalo estiver nas bordas o tabuleiro "acaba" ou se já tivesse passado pela casa C7 não poderiamos passar por lá novamente, para verificar isso utilizaremos a seguinte função que recebe next_move como o resultado do cálculo dos moves sobre o valor X, Y da posição atual, sendo esse um possivel movimento valido e o tabuleiro board

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

Tanto no eixo X ou Y caso o Cavalo tente fazer um movimento que ultrapasse o limite do tabuleiro o resultado do calculo será negativo e falhara na verificação acima e se esse movimento for feito na borda da direita ou para baixo o resultado será maior que o tamanho do tabueleiro; n representa o tamanho do tabuleiro (8)

solveKnight() é a nossa função principal

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

    # posição inicial aleatoria
    starting_pos_x = random.randint(0, 7)
    starting_pos_y = random.randint(0, 7)

    # começar a contagem de tours 
    # e definir que já passamos por essa posição
    tour = 1
    board[starting_pos_x][starting_pos_y] = 1

    # procurar os proximos movimentos
    findNextMove(moves_x, moves_y, starting_pos_x, starting_pos_y, tour, board, 8)
    return printBoard(n, board)

aqui chamamos a função findNextMove()

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

    # andar pelo 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)):
            # contar quantos neighbors estão disponíveis
            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)

Para encontrar a próxima casa vamos definir temporariamente um new_move que será um possivel movimento válido, a partir deste new_move vamos contar quantas outras possiveis casa diponíveis (neighbors) existem, o new_move que tiver o menor numero de neighbors passa a ser o next_move

Precisamos fazer isso até o Cavalo visitar todas as casas, para isso o retorno da nossa função será ela mesma, tornando-a recursiva. A cada movimento válido que o Cavalo faz estamos adicionando +1 na variável tour, quando o seu total for igual a 8 ** 2 (64) que é o total de casas que existem no nosso tabuleiro saberemos que o Tour foi completo

para contar os neighbors faremos o seguinte

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

Iteramos por todos os moves válidos, como estamos manipulando o new_move que é uma posição temporaria apenas para contar quantas casas disponíveis existem não podemos contar a casa que o cavalo realmente está, e esse é o papel do validNeighbor()

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 

Todos os movimentos que passarem são contados e retornados pela função countNeighbors().

Agora que o Cavalo já passou por todas as 64 casas precisamos printar na tela todo o caminho feito por ele

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

Para printar tudo isso iteramos pelo board e para cada elemento do eixo X printamos com o parametro end=' ', porquê o python por padrão cria uma nova linha e o resultado que esperamos é que fiquem um ao lado do outro, assim:

5 20 3 26 7 22 31 36 
2 27 6 21 30 37 8 23 
19 4 29 50 25 32 35 38 
28 1 48 33 56 51 24 9 
45 18 57 62 49 34 39 52 
60 63 44 47 42 55 10 13 
17 46 61 58 15 12 53 40 
64 59 16 43 54 41 14 11 

esse é o caminho feito pelo Cavalo em um tabuleiro de 8x8.

você pode acessar o código completo neste gist