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
Top comments (0)