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

Tags: algorithms, python, programming, tutorial
Published: 2021-11-16 22:47:47

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;

![board moves](https://media.graphcms.com/resize=,width:335,height:338/a9Z1BlNS03Vkui7BdOwM)

 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.
 
 ```python
    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
```python
    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.

![exemplo moves](https://media.graphcms.com/resize=,width:700,height:700/E5Zf0O49QM6E9BYtqqOc)

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`

```python
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

```python
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()`

```python
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  
```python
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()`

```python
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
```python
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:

```python
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](https://gist.github.com/joaovitorzv/20898d0e9f781a731a111cf3d9ff3615)