7. AED-I-N-Rainhas

Prévia do material em texto

José Augusto Baranauskas
Departamento de Computação e Matemática – FFCLRP-USP
augusto@usp.br
http://dcm.ffclrp.usp.br/~augusto
Algoritmos e
Estruturas de Dados I
Usando uma PilhaUsando uma Pilha
�Esta apresentação 
mostra o uso de 
retrocesso 
(backtracking) para 
resolver o problema das 
N-Rainhas usando uma 
pilha
2
O Problema das Oito RainhasO Problema das Oito Rainhas
�Suponha que você tenha 8 rainhas de um 
jogo de xadrez...
�...e um tabuleiro de xadrez
3
O Problema das Oito RainhasO Problema das Oito Rainhas
�As rainhas podem ser dispostas no 
tabuleiro de modo que duas rainhas não se 
ataquem?
4
O Problema das Oito RainhasO Problema das Oito Rainhas
�Duas rainhas não são permitidas na 
mesma linha...
5
O Problema das Oito RainhasO Problema das Oito Rainhas
�Duas rainhas não são permitidas na 
mesma linha, ou na mesma coluna...
6
O Problema das Oito RainhasO Problema das Oito Rainhas
�Duas rainhas não são permitidas na 
mesma linha, ou na mesma coluna, ou na 
mesma diagonal
7
O Problema das N RainhasO Problema das N Rainhas
�O número de rainhas 
e o tamanho do 
tabuleiro podem variar
N colunas
N l i
n h a
s
N Rainhas
8
O Problema das N RainhasO Problema das N Rainhas
Escreveremos um 
programa que tenta 
encontrar uma maneira 
de colocar N Rainhas 
num tabuleiro N x N
9
Como o Programa FuncionaComo o Programa Funciona
O programa usa 
uma pilha para 
guardar onde 
cada rainha é
colocada
10
Como o Programa FuncionaComo o Programa Funciona
Cada vez que o 
programa decide 
colocar uma 
rainha no 
tabuleiro, a 
posição da nova 
rainha é
guardada em um 
registro que é
colocado na pilha
ROW 1, COL 1
11
Como o Programa FuncionaComo o Programa Funciona
Também temos 
um inteiro para 
guardar quantas 
linhas foram 
preenchidas até
o momento 
(Filled) ROW 1, COL 1
1 Filled
12
Como o Programa FuncionaComo o Programa Funciona
Cada vez que o 
programa decide 
colocar uma 
rainha no 
tabuleiro, a 
posição da nova 
rainha é guardada 
em um registro 
que é colocado na 
pilha...
ROW 1, COL 1
1 Filled
ROW 2, COL 1
13
Como o Programa FuncionaComo o Programa Funciona
...se há conflito 
com outra rainha, 
mudamos a nova 
rainha para a 
próxima coluna à
direita
ROW 1, COL 1
1 Filled
ROW 2, COL 2
14
Como o Programa FuncionaComo o Programa Funciona
Se outro conflito 
acontece, a 
rainha é
novamente 
mudada para a 
próxima coluna
ROW 1, COL 1
1 Filled
ROW 2, COL 3
15
Como o Programa FuncionaComo o Programa Funciona
ROW 1, COL 1
2 Filled
ROW 2, COL 3
Quando não há
mais conflitos, 
paramos e 
adicionamos 1 
ao valor de 
Filled
16
Como o Programa FuncionaComo o Programa Funciona
ROW 1, COL 1
2 Filled
ROW 2, COL 3
ROW 3, COL 1
Vamos olhar na 
terceira linha. A 
primeira posição 
que tentamos 
tem um conflito...
17
Como o Programa FuncionaComo o Programa Funciona
...então mudamos para 
a coluna 2. Mas outro 
conflito surge...
ROW 1, COL 1
2 Filled
ROW 2, COL 3
ROW 3, COL 2
18
Como o Programa FuncionaComo o Programa Funciona
ROW 1, COL 1
2 Filled
ROW 2, COL 3
ROW 3, COL 3
...e mudamos 
para a terceira 
coluna. Ainda há
conflito...
19
Como o Programa FuncionaComo o Programa Funciona
ROW 1, COL 1
2 Filled
ROW 2, COL 3
ROW 3, COL 4
...e mudamos 
para a coluna 4. 
Ainda há conflito 
nesta coluna, 
então tentamos 
mover a rainha 
novamente...
20
Como o Programa FuncionaComo o Programa Funciona
ROW 1, COL 1
2 Filled
ROW 2, COL 3
ROW 3, COL 4
...mas não há
mais lugar no 
tabuleiro
21
Como o Programa FuncionaComo o Programa Funciona
Quando não temos 
mais espaço em uma 
linha:
�Tiramos o topo da 
pilha
�Decrementamos 
Filled em uma 
unidade
�E continuamos 
trabalhando na 
linha anterior
ROW 1, COL 1
1 Filled
ROW 2, COL 3
22
Como o Programa FuncionaComo o Programa Funciona
ROW 1, COL 1
1 Filled
ROW 2, COL 4
Agora 
continuamos 
trabalhando na 
linha 2, mudando 
a rainha para a 
direita
23
Como o Programa FuncionaComo o Programa Funciona
ROW 1, COL 1
2 Filled
ROW 2, COL 4
Esta posição não 
tem conflitos, 
então podemos 
incrementar 
Filled de 1, e 
mover para a 
rainha da linha 3
24
Como o Programa FuncionaComo o Programa Funciona
ROW 1, COL 1
2 Filled
ROW 2, COL 4
ROW 3, COL 1
Na linha 3, 
começamos 
novamente pela 
primeira coluna
25
PseudoPseudo--ccóódigo para as Ndigo para as N--RainhasRainhas
�Crie uma pilha na qual cada decisão tomada será
armazenada
�Posicione a primeira rainha, inserindo sua 
posição na pilha e preenchendo Filled com zero
�Repita estes passos
� Se não há conflitos com as rainhas...
� Senão se há conflitos e há espaço no tabuleiro para 
colocar a rainha na próxima coluna
� Senão se há conflito e não há espaço para mover a 
rainha para a direita...
26
PseudoPseudo--ccóódigo para as Ndigo para as N--RainhasRainhas
�Repita estes passos
� Se não há conflitos com as rainhas...
Incremente Filled de 1. Se Filled é igual a N,
então o algoritmo acabou. Senão mude 
para a próxima linha e coloque a rainha na 
primeira coluna.
27
PseudoPseudo--ccóódigo para as digo para as NN--RainhasRainhas
�Repita estes passos
� Se não há conflitos com as rainhas...
� Senão se há conflito e há espaço no tabuleiro 
para mover a rainha...
Mova a rainha para a próxima coluna,
ajustando o registro no topo da pilha
para indicar a nova posição
28
PseudoPseudo--ccóódigo para as digo para as NN--RainhasRainhas
�Repita estes passos
� Se não há conflitos com as rainhas...
� Senão se há conflito e há espaço no tabuleiro 
para mover a rainha...
� Senão se há conflito e não há espaço no 
tabuleiro para mover a rainha...
Volte! (Backtrack!)
Continue tirando da pilha e reduzindo Filled
de 1 até chegar a uma linha onde a rainha possa
ser mudada para a próxima coluna. Mude-a.
29
�Pilhas têm muitas aplicações
�A aplicação que mostramos é chamada 
backtracking (retrocesso)
�A chave para backtracking: cada escolha é
guardada em um pilha
�Quando você não tem mais opções para a 
decisão corrente, você tira o topo da pilha, e 
continua tentando diferentes escolhas para a 
decisão anterior
ResumoResumo
30
THE ENDTTHE HE EENDND
Presentation copyright 1995, The Benjamin/Cummings Publishing Company,
For use with Data Structures and Other Objects
by Michael Main and Walter Savitch.
Some artwork in the presentation is used with permission from Presentation Task Force
(copyright New Vision Technologies Inc) and Corel Gallery Clipart Catalog (copyright
Corel Corporation, 3G Graphics Inc, Archive Arts, Cartesia Software, Image Club
Graphics Inc, One Mile Up Inc, TechPool Studios, Totem Graphics Inc).
Students and instructors who use Data Structures and Other Objects are welcome
to use this presentation however they see fit, so long as this copyright notice remains
intact.
Translation to portuguese by Prof. Maria Carolina Monard, USP.
Modifications for C++ language by Prof. José Augusto Baranauskas, USP, 2005.