TProcura
Biblioteca em C++ para testes paramétricos de algoritmos, e coleção de algoritmos de procura e otimização
Loading...
Searching...
No Matches
✏️ 4 Damas, profundidade primeiro

O problema das N Damas consiste em colocar damas de xadrez num tabuleiro com a mesma largura do número de damas, sem que nenhum par de damas se ataquem (horizontal, vertical, diagonal). Para resolver à mão vamos resolver o problema das 4 damas.

O estado inicial pode ser o tabuleiro sem qualquer dama colocada, sendo os sucessores os tabuleiros em que se coloca mais uma dama na primeira linha vazia, numa das casas não atacada pelas damas já existentes no tabuleiro.

Geração Estado Nível Pai Expansão
1
   
 
 
 
 
   
 
 
   
 
 
 
 
0
0 1
2
 X
 
 
 
 
 
   
 
 
   
 
 
 
 
1
 1  
3
   X
 
 
 
 
   
 
 
   
 
 
 
 
1
 1  
4
   
 X
 
 
 
   
 
 
   
 
 
 
 
1 
 1  6
5
   
 
 X
 
 
   
 
 
   
 
 
 
 
1 
 1 2
6
   
 
 X
 X
 
   
 
 
   
 
 
 
 
 2
5  4
7
   
 
 X
 
 X
   
 
 
   
 
 
 
 
 2
5 3
8
   
 
 X
 X
 
   
 
 
 X
 
 
 
 
 
 3
6 5
9
   
 X
 
X 
 
   
 
 
   
 
 
 
 
 2
4 7
10 
   
 X
 
X 
 
   
 
 
   X
 
 
 
 
3
9  8
11
   
 X
 
X 
 
   
 
 
   X
 
X 
 
 
4
10 9 Solução!

Ficheiro de Excel, passo a passo:

Houve 11 gerações e 9 expansões. Neste problema há no entanto simetrias que foram ignoradas (horizontal, vertical, diagonal), o que pode levar a que sejam analisados estados em duplicado, tal como nos exemplos anteriores. Num problema desta dimensão não há problema, mas subindo a dimensão, a consideração das simetrias pode levar a poupanças muito consideráveis.

⚡ Ação: Refaça a procura em profundidade considerando as simetrias, mas para o problema das 5 damas. 
Geração Estado Nível Pai Expansão
1
         
         
         
         
         
0 0 1
2
X        
         
         
         
         
1 1  
3
  X       
         
         
         
         
1 1  
4
    X    
         
         
         
         
1 1 2
5
    X    
 X        
         
         
         
2 4 3
6
    X    
 X        
      X  
         
         
3 5 4
7
    X    
 X        
      X  
  X      
         
4 6 5
8
    X    
 X        
      X  
  X      
         X
5 7 6 Solução!

◀ Passo anterior Próximo passo ▶