Você já jogou xadrez? Se sim, você já sabe que a rainha é a peça mais importante e que ela pode mover qualquer número de quadrados verticalmente, horizontalmente ou diagonalmente. Se ainda não o fez, não se preocupe: hoje, só aprenderemos a colocar 8 rainhas no tabuleiro de xadrez de tal forma que nenhuma rainha seja capaz de se deslocar para uma casa ocupada por outra rainha. No jargão do xadrez, dizemos que as rainhas não serão capazes de se atacarem umas às outras. Como é que fazemos isto? Usamos o backtracking.
O algoritmo de backtracking encontra uma solução para problemas em que algumas restrições devem ser respeitadas. Ele testa todas as soluções possíveis até encontrar a solução correta. Vamos tentar um exemplo, com quatro rainhas e uma pequena tábua. Vamos começar colocando a primeira rainha:
The second step is to place the second queen in a safe position, and then the third one:
At this point, there is no safe square on which we can place the last queen. So, we will change the position of the previous one. This is backtracking!
As you can see, there is no other square to safely place the third queen, different than the one we tried. Hence, this will require multiple backtracks. We will have to go back again and change the position of the second queen we placed.
We will have to perform multiple backtracks again to place all queens correctly and finally obtain a solution:
If you want to learn more how multiple backtracking steps inevitably lead you to a solution, check out Computer Science Distilled. Também lhe mostrará muitas outras estratégias computacionais que o ajudarão a resolver problemas interessantes!
Agora que sabe como funciona o backtracking, podemos resolver o problema das 8 rainhas em tamanho real. Abaixo, há um tabuleiro de xadrez com o qual você pode jogar para praticar suas habilidades e encontrar uma solução. Comece colocando a primeira rainha clicando no quadrado superior esquerdo do tabuleiro de xadrez. Você verá que a rainha que você colocou será listada na lista “Current queens”.
Current queens
Você pode agora colocar outra rainha em uma posição que irá evitar que elas se ataquem umas às outras. A nossa primeira rainha está em a8, a segunda, por exemplo, pode ser colocada em c7. Continue colocando as rainhas até que não haja mais nenhum quadrado seguro no tabuleiro de xadrez. Nesse momento, é hora de recuar, clicando em “desfazer”. Isto irá limpar a última rainha que colocou e permitir-lhe-á escolher outra casa para a colocar. Você também pode remover uma rainha do tabuleiro, clicando diretamente sobre ela.
Ao jogar o jogo interativo, você pode começar a ter uma sensação de retrocesso. Como humanos, pode tornar-se difícil para nós manter um registo de todas as colocações de rainha anteriores. É aqui que a programação ajuda! Abaixo, você pode encontrar uma animação gerada por um programa demonstrando suas habilidades de backtracking sem falhas:
Pseudocode:
- Inicie colocando a primeira rainha no quadrado superior esquerdo do tabuleiro.
- Se nós colocamos as 8 rainhas, nós terminamos. Caso contrário, é possível colocar outra rainha numa posição segura?
- Se sim, então marque isto como parte da solução, e volte ao ponto 2.
- Se não, então mude a posição da rainha anterior (backtracking) e volte ao ponto 2.