Quebra-cabeça do desafio das rainhas do xadrez

De Augusto Baffa Wiki
Ir para navegação Ir para pesquisar

O desafio é colocar N rainhas em um tabuleiro NxN de forma que nenhuma rainha possa "atacar" qualquer outra rainha. As rainhas podem se mover horizontalmente, verticalmente ou ao longo de uma diagonal (45%). O diagrama a seguir mostra uma solução para N=4 rainhas. 

________________
|   |   | Q |   |
|___|___|___|___|
| Q |   |   |   |
|___|___|___|___|
|   |   |   | Q |
|___|___|___|___|
|   | Q |   |   |
|___|___|___|___|

Uma solução para este quebra-cabeça pode ser representada como uma permutação especial da lista [1,2,3,4]. Por exemplo, a solução ilustrada acima pode ser representada como [3,1,4,2], o que significa que, na primeira linha coloque uma rainha na coluna 3, na segunda linha coloque uma rainha na coluna 1, etc. Para testar se uma dada permutação é uma solução, é necessário calcular se a permutação tem (ou representa uma situação onde) duas ou mais rainhas estão na mesma diagonal. A própria representação evita duas ou mais rainhas na mesma linha ou coluna. Duas rainhas estão na mesma / diagonal se e somente se a soma da linha e coluna for a mesma para cada uma; eles estão na mesma diagonal se e somente se a diferença de sua linha e coluna for o mesmo número. O programa Prolog a seguir contém os detalhes; assuma que os predicados 'perm' e 'takeout' são definidos como na seção 2.7. 

solve(P) :-
     perm([1,2,3,4,5,6,7,8],P), 
     combine([1,2,3,4,5,6,7,8],P,S,D),
     all_diff(S),
     all_diff(D).

combine([X1|X],[Y1|Y],[S1|S],[D1|D]) :-
     S1 is X1 +Y1,
     D1 is X1 - Y1,
     combine(X,Y,S,D).
combine([],[],[],[]).

all_diff([X|Y]) :-  \+member(X,Y), all_diff(Y).
all_diff([X]).

Observe a inclusão do arquivo 'lists.pro' discutido na seção 2.6. Esta é uma especificação simples e tranquila que usa 'perm' para gerar soluções possíveis para o quebra-cabeça. Um exemplo de objetivo é 

?- solve(P).
P = [5,2,6,1,7,4,8,3] ;
P = [6,3,5,7,1,4,2,8] ;
...

?- setof(P,solve(P),Set), length(Set,L).
...
L = 92

O último objetivo reflete o fato de que existem 92 soluções distintas para o quebra-cabeça do desafio das rainhas para um tabuleiro 8x8. Uma ineficiência que esse programa sofre é que cada permutação é completamente calculada antes de ser verificada para ver se representa uma solução para o quebra-cabeça. É fácil perceber que isso não é necessário. Por exemplo, suponha que uma "solução parcial" P = [1,3,2, ...] seja considerada. Os cálculos de linha e coluna já mostram que o "2" não é um movimento seguro! Uma solução que evita essa ineficiência é considerada na seção 2.13.

Veja Também

Disponível em “http://www.augustobaffa.pro.br/wiki/index.php?title=Quebra-cabeça_do_desafio_das_rainhas_do_xadrez&oldid=314”