Upload
marcos-castro
View
3.743
Download
1
Embed Size (px)
Citation preview
Problema Ops, as rainhas se atacam pela diagonal! Vamos tentar colocar a segunda rainha em outro lugar...
R
R
Problema Ops, as rainhas se atacam pela coluna! Vamos tentar colocar a segunda rainha em outro lugar...
R
R
Problema Ops, as rainhas se atacam pela linha! Em um tabuleiro NxN, devemos colocar N rainhas de modo que elas não se ataquem por linha, coluna ou diagonal!
R R
Problema Construindo uma solução válida... As partes em vermelho não se pode colocar rainhas.
R
R
R
R
Problema Construindo uma solução válida... As partes em vermelho não se pode colocar rainhas.
R
R
R
R
R
Problema Construindo uma solução válida... As partes em vermelho não se pode colocar rainhas.
R
R
R
R
R
R
Problema Construindo uma solução válida... As partes em vermelho não se pode colocar rainhas.
R
R
R
R
R
R
R
Problema Construindo uma solução válida... As partes em vermelho não se pode colocar rainhas.
R
R
R
R
R
R
R
R
Solução Vamos resolver esse problema por backtracking... A ideia é colocar a primeira rainha em uma posição da primeira coluna, a segunda rainha em uma posição da segunda coluna, a terceira em uma posição da terceira coluna e assim por diante...
Cada rainha irá se movimentar na sua coluna para tentarmos achar a solução! Ao colocar uma rainha, é preciso verificar se elas se atacam. Se elas se atacarem, realiza-se um backtracking (volta para algum estado anterior) para tentar novamente de outra forma.
Solução Coloca-se a segunda rainha numa posição da segunda coluna: Ops, as rainhas se atacam, tenta colocar a segunda rainha em outra posição...
R R
Solução Ops, as rainhas se atacam, tenta colocar a segunda rainha em outra posição... Backtracking!
R
R
Solução Ops, as rainhas se atacam, tenta colocar a segunda rainha em outra posição... Backtracking!
R R
Solução Ops, as rainhas se atacam, tenta colocar a segunda rainha em outra posição... Backtracking!
R
R
Solução Legal, conseguimos colocar a segunda rainha de forma que as rainhas não se ataquem. Vamos tentar colocar a terceira rainha...
R
R
Solução Colocamos a terceira rainha na terceira coluna. Ops, as rainhas se atacam! Tenta colocar a terceira rainha em outra posição da terceira coluna.
R R
R
Solução Ops, as rainhas se atacam! Tenta colocar a terceira rainha em outra posição da terceira coluna.
R
R
R
Solução Ops, as rainhas se atacam! Tenta colocar a terceira rainha em outra posição da terceira coluna.
R
R R
Algoritmo Já conseguimos visualizar algumas coisas que temos que fazer. Precisamos ter uma função para verificar se, ao colocar uma rainha numa determinada posição, nenhuma rainha se atacará, ou seja, verifica a linha, coluna e diagonais a partir da posição de onde iremos colocar a rainha.
Algoritmo Precisamos de uma função para gerar as soluções. “tab” é o tabuleiro, “N” é a dimensão e “col” é a coluna onde que vamos tentar inserir a nova rainha.
Implementação Código em C++:
◦ https://gist.github.com/marcoscastro/501e816d6bb42a104eba
Contato [email protected]
www.geeksbr.com www.youtube.com/c/marcoscastrosouza
https://github.com/marcoscastro https://gist.github.com/marcoscastro
https://about.me/mcastrosouza