O Problema das 8 Rainhas

Uma Abordagem Passo a Passo

Aléssio Miranda Júnior

Introdução

O que é o Problema das 8 Rainhas?

  • É um problema clássico da computação e da matemática (proposto em 1848).
  • Objetivo: Posicionar exatamente 8 rainhas em um tabuleiro de xadrez padrão (\(8 \times 8\)).
  • Regra: Nenhuma rainha pode atacar outra rainha.

Como uma Rainha ataca?

No xadrez, a Rainha é a peça mais poderosa. Ela pode se movimentar (e atacar) em qualquer direção:

  • Horizontalmente (Linha)
  • Verticalmente (Coluna)
  • Diagonalmente (Ambas as diagonais: Principal e Secundária)

Para vencer o problema, duas rainhas nunca podem compartilhar a mesma linha, coluna ou diagonal.

A Abordagem Inicial

Tentativa e Erro “Cega”

  • Se tentarmos colocar 8 rainhas aleatoriamente em 64 espaços, existem impressionantes \(4.426.165.368\) combinações possíveis.
  • Checar todas essas combinações, embora possível para o computador, é ineficiente (força bruta \(O(n!)\) ou pior).
  • Precisamos de uma estratégia mais inteligente.

Simplificando o Problema

Temos 8 rainhas a colocar. Se duas rainhas não podem compartilhar a mesma coluna: - Cada coluna do tabuleiro (da 1 a 8) DEVE conter exatamente 1 rainha. - Sabendo disso, o nosso problema não é “escolher 8 quadrados de 64”. - É apenas: Em qual linha colocaremos a rainha para cada coluna?

O Problema Simplificado: 4 Rainhas

Para entender como o algoritmo pensa, as vezes é mais fácil reduzir o problema. Veja uma solução para um tabuleiro menor (\(4 \times 4\) com 4 rainhas):

Explorando Etapa por Etapa

A Estratégia Base (Algoritmo Algébrico)

O computador resolve isso utilizando uma técnica chamada Backtracking (Retrocesso/Tentativa e Erro Estruturado). A ideia base é:

  1. Vamos colocar a primeira rainha na primeira coluna (esquerda).
  2. Avançamos para a coluna seguinte (direita).
  3. E se encontrarmos um “beco sem saída”? Volte uma coluna e mova a rainha anterior.

Passo 1: A Primeira Coluna

  • Começamos na Coluna 1.
  • Tentamos colocar a rainha na Linha 1.
  • Checagem: Ela está em perigo?
  • Não, pois o tabuleiro ainda está vazio.
  • Colada a primeira rainha! Avançamos para a Coluna 2.

Passo 2: A Segunda Coluna

  • Estamos na Coluna 2.
  • Linha 1? -> Perigo (A mesma linha da rainha 1).
  • Linha 2? -> Perigo (A mesma diagonal da rainha 1).
  • Linha 3? -> Seguro! Nenhuma rainha cruza esse caminho.
  • Colada a segunda! Avançamos para a Coluna 3.

Passo 3: E se chegarmos num Culpado?

  • Continuamos esse processo. Mas, em determinado momento (ex: Coluna 6), podemos não encontrar NENHUMA linha segura de 1 a 8.
  • Todas as posições dessa coluna são atacadas pelas rainhas anteriores.
  • O que fazemos? O tabuleiro faliu?

A Inteligência do Backtracking

  • Quando falhamos na Coluna 6, o computador entende que o erro não começou na Coluna 6. O erro ocorreu numa escolha passada.
  • Ele “dá um passo atrás” (Backtrack) e volta para a Coluna 5.
  • Na Coluna 5, ele retira a rainha da sua posição atual e tenta movê-la para a próxima linha segura.
  • E se a Coluna 5 não tiver mais linhas? O computador volta para a Coluna 4.

Conclusão e Preparação

O Resumo do Ciclo

  1. Avança: Coloca rainha numa posição segura da coluna N. Vai para coluna N+1.
  2. Checa: Procura casas seguras testando horizontais e diagonais voltados “para a esquerda”, já que a direita ainda está vazia.
  3. Recua (Backtrack): Se não achar espaço, retira a rainha e pede para a coluna N-1 tentar outra alternativa.

Implementando em Código (Prévia)

A nossa missão prática, programando isso, será construir uma função recursiva:

  • posicionarRainha(coluna)
  • Um loop para testar de linha 0 a 7.
  • Uma subfunção casaEhSegura(linha, coluna) que checa se as ameaças estão vazias.
  • Se for segura: marca o tabuleiro e invoca posicionarRainha(coluna + 1).

Dúvidas até aqui?

Prontos para programar o nosso Algoritmo Retratil (Backtracking)?