BackTracking

Backtracking
Katia Guimarães

Backtracking
Técnica em procedimentos de busca que corresponde ao retorno de uma exploração.
Ex: (já visto) Busca-em-Profundidade
Quando chegamos a um nó v pela primeira vez, cada aresta incidente a v é explorada e então o controle volta (backtracks) ao nó a partir do qual v foi alcançado. [e-mail] 2

Problema das Oito Rainhas
Colocar oito rainhas num tabuleiro de xadrez, de forma que nenhuma delas fique atacada por outra.
Em outras palavras, escolher oito posições no tabuleiro de forma que não haja duas delas compartilhando a mesma linha, a mesma coluna ou a mesma diagonal. [e-mail] 3

Algoritmo para
O Problema das Oito Rainhas
1. Coloque uma rainha na posição mais à esquerda da primeira linha.
2. Enquanto não houver oito rainhas no tabuleiro faça:
Se na próxima linha existir uma coluna que não está sob ataque de uma rainha já no tabuleiro então coloque uma rainha nesta posição senão volte à linha anterior /* backtrack */ mova a rainha o mínimo necessário para a direita de forma que ela não fique sob ataque [e-mail] 4

Algoritmo para
O Problema das Oito Rainhas
Q

[e-mail]

5

Algoritmo para
O Problema das Oito Rainhas
Q
Q

[e-mail]

6

Algoritmo para
O Problema das Oito Rainhas
Q
Q
Q

[e-mail]

7

Algoritmo para
O Problema das Oito Rainhas
Q
Q
Q
Q

[e-mail]

8

Algoritmo para
O Problema das Oito Rainhas
Q
Q
Q
Q
Q

[e-mail]

9

Algoritmo para
O Problema das Oito Rainhas
Q
Q
Q
Q
Q

[e-mail]

10

Algoritmo para
O Problema das Oito Rainhas
Q
Q
Q
Q
Q

[e-mail]

11

Algoritmo para
O Problema das Oito Rainhas
Q
Q
Q
Q
Q

[e-mail]

12

Algoritmo para
O Problema das Oito Rainhas
Q
Q
Q
Q

[e-mail]

13

Algoritmo para
O Problema das Oito Rainhas
Q
Q
Q
Q
Q

[e-mail]

14

Algoritmo para
O Problema das Oito Rainhas
Q
Q
Q
Q
Q
Q

[e-mail]

15

Algoritmo para
O Problema das Oito Rainhas
Q
Q
Q
Q
Q
Q
Q