O Problema das n Rainhas (Backtracking)

Prévia do material em texto

Bruno Marques e Danielly Queiroz
UFRPE – Projeto e Análise de Algoritmos 2015.1
 Organizar um número n de rainhas em um 
tabuleiro n x n (tipo xadrez) de forma que 
elas não se ataquem.
 Isso significa que duas rainhas não podem 
dividir a mesma linha, coluna e diagonal.
2
 Quando n = 1, no tabuleiro só existirá 
apenas uma rainha.
1x1
3
 Quando n = 2 ou n = 3, não existe solução, 
pois é impossível que as rainhas não 
compartilhem a mesma diagonal.
3x3
?
2x2
?
4
 O problema está definido para n > 3. 
 Pode existir mais de uma solução.
5
 Aborda problemas complexos de busca 
combinatória.
Utilizado para encontrar conjuntos que 
satisfaçam algumas restrições.
6
 As soluções são encontradas quando uma 
rainha fica na posição correta (sem atacar 
nenhuma das outras).
 Cada solução parcial é avaliada como 
promissora ou não promissora.
7
 Se uma solução parcial é promissora, 
selecionamos a próxima rainha.
 Senão, o algoritmo retrocede (backtrack) e 
substitui a última posição da rainha por 
sua próxima opção de posição.
8
 Posição:
Localização de cada uma das n rainhas. 
Chamaremos de P𝑖 a coluna ocupada por 
uma determinada rainha.
Observe que não poderá existir rainhas na 
mesma linha.
9
 Index:
Valores possíveis para posicionar uma 
rainha no tabuleiro.
 Restrições:
Conjunto de index permitidos para as 
posicionar as rainhas de forma que não se 
ataquem.
Qj Qi e Qj −Qi |𝑖 − 𝑗|
10
 Testaremos para n = 4
 Inicialmente todas as posições possuem os 
valores da Index (valores possíveis), já que 
as restrições ainda não foram verificadas.
 P1 = {1, 2, 3, 4}
 P2 = {1, 2, 3, 4}
 P3 = {1, 2, 3, 4}
 P4 = {1, 2, 3, 4}
4x4
11
 Vamos escolher um valor para a posição P1
(coluna que a rainha da primeira linha irá 
ocupar)
 P1 = 1
12
4x4
 Aplicando as restrições temos:
 P2 = {3, 4} P2 P1 e P2 P1 + 1
13
4x4
 Aplicando as restrições temos:
 P3 = {2, 4} P3 P1 e P3 P1 + 2
14
4x4
 Aplicando as restrições temos:
 P4 = {2, 3} P4 P1 e P4 P1 + 3
15
4x4
 Já que temos um valor possível para P1
escolhemos o valor da próxima posição P2.
 P2 = 3
16
4x4
 Aplicando as restrições temos:
 P3 = {} P3 P2 e P3 P2 + 1 e P3 P2 - 1
 Logo, não existe solução
para P1 = 1 e P2 = 3.
 Sendo assim, iremos
procurar outro valor
para P2, ou seja
P2 = 4.
17
4x4
 Escolhemos outro valor da posição P2.
 P2 = 4
18
4x4
 Aplicando as restrições temos:
 P3 = {2} P3 P2 e P3 P2 - 1
19
4x4
 Já que temos um valor possível para P2
escolhemos o valor da próxima posição P3.
 P3 = 2
20
4x4
 Aplicando as restrições temos:
 P4 = {} P4 P3 e P4 P3 + 1 e P4 P3 - 1
 Logo, não existe solução
para P1 = 1 e P2 = 4 e 
P3 = 2.
 Sendo assim, teremos
que reiniciar o 
processo selecionando 
outro valor para P1 .
21
4x4
 Reinicialização das posições. 
 P1 = {1, 2, 3, 4}
 P2 = {1, 2, 3, 4}
 P3 = {1, 2, 3, 4}
 P4 = {1, 2, 3, 4}
4x4
22
 Vamos escolher outro valor para a posição P1
 P1 = 2
23
4x4
 Aplicando as restrições temos:
 P2 = {4} P2 P1 e P2 P1 + 1 e P2 P1 - 1
24
4x4
 Vamos escolher o valor para a posição P2
 P2 = 4
25
4x4
 Aplicando as restrições temos:
 P3 = {1} P3 P2 e P3 P2 - 1
26
4x4
 Vamos escolher o valor para a posição P3
 P3 = 1
27
4x4
 Aplicando as restrições temos:
 P4 = {3} P4 P3 e P4 P3 +1
28
4x4
 Vamos escolher o valor para a posição P4
 P4 = 3
29
4x4
 Encontramos a solução!
30
4x4
 O algoritmo começa alocando a primeira 
rainha na primeira posição do tabuleiro.
 Depois posiciona a segunda rainha na 
segunda linha procurando a primeira coluna 
de forma que as rainhas não se ataquem.
 Repete o processo para a terceira rainha em 
relação às duas primeiras, até que a solução 
seja encontrada ou ocorra falha.
31
 Se não existir posição para a rainha 
analisada, o algoritmo procura outra posição 
na mesma linha para ela.
 Achando a posição, o algoritmo continua o 
processo para as outras linhas, se não 
encontrar, ele retorna para a linha anterior.
 O algoritmo para quando a última linha for 
preenchida com a última rainha.
32
33
 Tabela de testes n x t
34
Quantidade n de rainhas Tempo s de execução
1 muito menos de 1s
2 bem menos de 1s
4 pouco menos de 1s
8 menos de 1s
16 1s
32 7:19 min
64 34:17 min
?
 Backtracking - Dr. Leandro Balby Marinho/UFCG
http://www.dsc.ufcg.edu.br/~lbmarinho/slides/atal_2012_2/backtracking.pdf
 N Rainhas - Inês de Castro Dutra/UFRJ
http://www.cos.ufrj.br/~ines/courses/cos740/leila/N%20Rainhas.ppt
36