História de Guerra - Cobertura do
Tabuleiro de Xadrez
Projeto e Análise de Algoritmos
Professora Dra. Diane Castonguay
André da Cunha Ribeiro – [email protected]
Geoflávia Guilarducci de Alvarenga – [email protected]
1
Tópicos








O jogo de Xadrez
Idéias Centrais
Problema da cobertura do tabuleiro de xadrez
O algoritmo do backtracking
Técnica de Podagem (Pruning)
Podagem aplicada à História de Guerra
Considerações Finais
Lição Aprendida
2
História de Guerra - Cobertura do
Tabuleiro de Xadrez - Parte I
Próximo
Rei
Voltar
4
Dama
Voltar
5
Cavalo
Voltar
6
Bispo
Voltar
7
Torre
Voltar
8
Idéias Centrais – História de Guerra


O jogo de xadrez inspirou vários problemas de
combinação
Em 1848, Kling propôs a seguinte questão:
 Se
todos os 64 quadrados do tabuleiro podem ser
fortemente ameaçados simultaneamente por um arranjo
das 8 peças principais no tabuleiro de xadrez

Configurações que simultaneamente ameaçam 63
quadrados foram conhecidas por muitos anos
9
10
11
12
13
Vejamos algumas considerações

Considere as 8 peças principais do xadrez
Quantos modos as peças podem ser
posicionadas no tabuleiro de xadrez?
 O número de posições aproximado é de
1015

14
Busca exaustiva

Este problema parece bem maduro para
solução de pesquisa exaustiva de
combinação;

O algoritmo do backtracking (regressão)
15
Backtrack(A)
Calcule S1, conjunto dos primeiros elementos
candidatos da solução A.
k=1
enquanto k > 0 faça
enquanto Sk <> 0 faça (*avanço*)
ak = próximo elemento de sk
sk = sk - ak
se A = (a1, a2, a3, …, an) é uma solução,
imprima isso.
k=k+1
fim enquanto
k = k - 1 (*backtrack*)
fim enquanto
16
Considerações

A história de guerra seria solucionável
usando a técnica Backtracking, dependendo
do tamanho do espaço de procura.
17
Podagem (Pruning)

BackTracking

Sua eficiência depende da sofisticação do
esquema de “poda” da árvore de soluções.
Como efetuar essa
podagem ?
18
Podagem (Pruning)

Técnica de eliminação de busca que atua
no momento que estabelecemos que tal
solução parcial não pode ser estendida na
solução que nós almejamos.
19
Podagem

Árvore pode ser “podada” através do uso de
heurísticas de acordo com a aplicação.

Há uma redução da complexidade de busca
de maneira significativa.
20
Podagem aplicada à História de Guerra

BackTracking => gera uma combinação
exaustiva de posições. Mas algumas
poderiam ter sido podadas.

Quais são as posições candidatas a serem
podadas?

São aquelas que não oferecem ameaça para uma
dada peça.
21
Podagem aplicada à História de Guerra

Exemplos:

1. Remoção de simetrias

Considerando as simetrias
ortogonais e diagonais, haverá
somente 10 posições diferentes
para a Rainha.
22
Podagem aplicada à História de Guerra

Exemplos: (cont.)

1. Remoção de simetrias (cont.)
 Uma
vez que a Rainha é colocada, há 2080
modos diferentes para posicionar um par de
Torres ou Cavalos.
 64
lugares para localizar o Rei.
 32
lugares para cada um dos Bispos.
23
Podagem aplicada à História de Guerra

Exemplos: (cont.)

2. Sp que já tivéssemos colocado 7 peças no
tabuleiro, e juntas elas cobririam todos menos
10 quadrados no tabuleiro; e a peça restante
fosse o Rei.
 Existe
alguma posição possível para colocar
o Rei de forma que todos os quadrados são
ameaçados?
24
Cobertura do Tabuleiro de Xadrez
BackTracking
+
Podagem
=
Eliminação acima de 95% do espaço
de pesquisa.
25
Cobertura do Tabuleiro de Xadrez

Considerações usadas na solução:
Os
tabuleiros de xadrez podem ter
qualquer número de peças, e mais de uma
peça num quadrado.
26
Cobertura do Tabuleiro de Xadrez

Dois tipos de ataques num quadrado:
ataque forte e ataque fraco.
27
Cobertura do Tabuleiro de Xadrez

Passos principais do algoritmo:
 Listar
todas as configurações dos tabuleiros nas
quais todo quadrado é fracamento atacado.
 Filtrar
a lista considerando bloqueios e
tabuleiros com n ou pouco menos quadrados
seguros.
28
Considerações Finais

Sobre o algoritmo:
Não
encontrou uma configuração que
cobrisse todos os 64 quadrados, porém,
mostrou que é possível cobrir um tabuleiro
com 7 peças se a Rainha e um Cavalo
possam ocupar o mesmo quadrado.
29
Considerações Finais

Configuração gerada pelo algoritmo:
30
Outros problemas [2]

Percurso do Cavalo no Tabuleiro de Xadrez

Problema das 8 Rainhas

Problema do Casamento Estável
31
Lição Aprendida
Uma ou mais estratégias de podagem
usadas de maneira inteligente podem
otimizar o trabalho de problemas de busca
ou de pesquisa combinatória de maneira
surpreendente.

32
Referências Bibliográficas
[01]
http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK/
NODE$.htm
[02] Wirth, Niklaus. Algoritmos e Estruturas de Dados. Editora
LTC, 1989.
33
Dúvidas ?
34
Fim
Obrigado !
André da Cunha Ribeiro
Geoflávia Guilarducci de Alvarenga
35