Neste módulo veremos:
O problema das oito rainhas, também conhecido pelo termo inglês The
Eight Queens Problem
, é um dos quebra-cabeças ocidentais clássicos.
O problema consiste em posicionar, num tabuleiro de xadrez (8 × 8)
oito rainhas de modo a não se conflitarem. Sabemos que, pelas regras
do xadrez, uma rainha pode se movimentar, ou seja atacar,
em qualquer direção movendo-se usando
qualquer número de posições, logo, uma rainha deve ser posicionada
em sua própria coluna, linha e diagonal para não ser alvo das demais.
Existem 92 soluções possíveis para este problema. Desta 92 soluções, 12 soluções são únicas e 80 são tidas como variações destas 12. Ainda não existe uma formulação matemática para a solução deste problema. As soluções são algoritmicas, na base da tentativa e erro e, sendo assim, são um modelo ideal para ser implementado por computador. Haja paciência para testar estas soluções manualmente!
Sabe-se que este problema foi formulado pelo famoso cientista computacional Nicklaus Wirth em duas de suas publicações em que ele afirma que o problema foi considerado por Gauss por volta de 1850. Mais recentemente Timothy Budd também sugeriu este problema como uma abordagem educacional para programação em linguagens orientadas a objetos e é nesta abordagem que solucionaremos este problema.
Este problema é também muito utilizado na Inteligência Artificial
como aplicação de soluções usando backtracking
. Bem, mas como seria
uma solução em linguagem imperativa? Neste tipo de linguagem provavelmente
haveria uma estrutura de dados (matriz, vetores) para manter as posições
das peças e o programa chegaria a uma solução procurando acomodar as
rainhas nesta estrutura de maneira a não conflitar com as demais,
ou seja, de modo que uma rainha não pudesse atacar as demais.
Numa solução OO usa-se e atribui-se o conceito de responsabilidade a cada objeto dando poderes às peças de poderem solucionar o seu problema de conflito, ou seja, ao invés aplicarmos um controle a todas as peças como faríamos na abordagem imperativa vamos distribuir a responsabilidade para que cada peça analise a situação em que está, se vulnerável ou não a um ataque, e se movimente caso necessário. A solução será encontrada pela interação entre estes agentes, estes objetos.
A solução do problema é baseada em duas fases:
Vamos detalhar o último passo, o refino da solução, pois é mais fácil de analisar
Será que a rainha pode ser atacada?
O código abaixo recebe as coordenadas de linha e coluna,
(tlin, tcol), e verifica se há possibilidade de haver
um ataque desta posição para a posição atual da rainha. O retorno
é um valor lógico, falso ou verdadeiro. O teste é feito para as condições
de igualdade de linha e de um possível taque pelas diagonais, caso em
que testa o gradiente
da linha imaginária formada entre
a posição atual da rainha e a posição para teste.
private boolean podeAtacar(int tlin, int tcol) {
int colDif = tcol - col;
if ( (lin == tlin) || (lin + colDif == tlin) ||//
(lin - colDif == tlin))
return true;
if (viz != null)
return viz.podeAtacar(tlin, tcol);
return false;
}
Cabe aqui o processo de atribuição de posições iniciais para as rainhas. Notem que desejamos colocá-las todas na mesma linha, ligá-las às suas vizinhas a esquerda mas, como o valor da coluna é passado como parâmetro, poderemos colocá-las cada uma numa coluna distinta, o que é um facilitador imediato para a solução deste problema. Sendo assim, bastará alterar as linhas (ou seja, as camadas horizontais) em que as rainhas estão posicionadas.
public Queen (short c, Queen q)
{
col = c;
lin = 1;
viz = q;
}
Este é o foco das decisões, as chamadas recursivas aos vizinhos para verificar a possibilidade de ataque. Vejam que simples esta abordagem, observar o vizinho para ver se será atacado. Se sim, a rainha avança uma posição. Quando os vizinhos dizem que não atacarão uma solução é encontrada.
public boolean achaSolucao()
{
while (viz!=null && viz.podeAtacar(lin, col))
if (!avanca())
return false;
return true;
}
No meu entender, este é o módulo mais complexo. Aqui ocorre a busca por uma nova posição da rainha, ou seja, uma nova linha. Notem que este método também lança mão da recursão para avançar as posições. Duas são as situações: se não esta no final do tabuleiro, avança uma posição; outra, não encontrando uma posição adequada a saída é voltar a linha inicial, 1.
public boolean avanca()
{
if ( lin<8 ) {
lin++;
return achaSolucao();
}
if (viz != null) {
if (!viz.avanca())
return false;
if (!viz.achaSolucao())
return false;
}
else
return false;
lin = 1;
return achaSolucao();
}
Resta ainda a impressão do resultado que pode obedecer ao modo gráfico ou não.
public String toString()
{
return("("+col + ", "+lin+")");
}
public void imprime()
{
if(viz != null)
viz.imprime();
System.out.println(this);
}
//usa se applet
public void paint(Graphics g) {
if (viz != null)
viz.paint(g);
int x = (lin-1)*50;
int y = (col-1)*50;
g.drawOval(x+20, y+20, 10,10);
}
/** Queen.java
* basedao no codigo de Timothy Budd
*/
import java.awt.Graphics;
public class Queen {
private short lin;
private short col;
private Queen viz;
public Queen (short c, Queen q)
{
col = c;
lin = 1;
viz = q;
}
public boolean achaSolucao()
{
while (viz!=null && viz.podeAtacar(lin, col))
if (!avanca())
return false;
return true;
}
public boolean avanca()
{
if ( lin<8 ) {
lin++;
return achaSolucao();
}
if (viz != null) {
if (!viz.avanca())
return false;
if (!viz.achaSolucao())
return false;
}
else
return false;
lin = 1;
return achaSolucao();
}
private boolean podeAtacar(int tlin, int tcol) {
int colDif = tcol - col;
if ( (lin == tlin) || (lin + colDif == tlin) ||//
(lin - colDif == tlin))
return true;
if (viz != null)
return viz.podeAtacar(tlin, tcol);
return false;
}
public String toString()
{
return("("+col + ", "+lin+")");
}
public void imprime()
{
if(viz != null)
viz.imprime();
System.out.println(this);
}
//usa se applet
public void paint(Graphics g) {
if (viz != null)
viz.paint(g);
int x = (lin-1)*50;
int y = (col-1)*50;
g.drawOval(x+20, y+20, 10,10);
}
}//Queen
Para testar...
/** TQueen.java
* soluciona o problema
*/
public class TQueen {
public static void main (String[] xyz) {
Queen ultima;
ultima = null;
for (short i=1; i<=8; i++)
{
ultima = new Queen(i, ultima);
ultima.achaSolucao();
}
ultima.imprime();
}
}
Veja a versão originalmente proposta por Timothy Budd.
(evandro at usp ponto br)