Oito rainhas: técnicas de força bruta. Neste problema,você desenvolverá várias técnicas de força bruta para solucionar o problema das Oito Rainhas, introduzido no Exercício 6.26.
a) Resolva o problema das Oito Rainhas usando a técnica de força bruta aleatória desenvolvida no Exercício 6.25.
b) Use uma técnica exaustiva (ou seja, tente todas as combinações possíveis de oito rainhas no tabuleiro).
c) Na sua opinião, por que a técnica de força bruta exaustiva pode não ser apropriada para resolver o problema das Oito Rainhas?
d) Compare as técnicas de força bruta aleatória e de força bruta exaustiva em geral.
Passo 1
Beleza pessoal, espero que todos estejam bem e dispostos a estudar um pouco hoje. Hoje temos uma questão de C para fazermos e com vários passos, então é super importante que você abra o seu compilador para não se perder. Vamos nessa!!!!
- Modificaremos o código da tarefa anterior para realizar uma busca de força bruta por uma solução. Podemos excluir a função heurística, pois não usaremos a abordagem heurística.
- Ao tentar todos os movimentos possíveis, o algoritmo alcançará a mesma solução com apenas uma ordem diferente de movimentos. Como queremos apenas soluções únicas, teremos que armazenar as soluções à medida que forem encontradas, então quando uma nova solução for encontrada, verifique-a com as soluções encontradas anteriormente. Isso é feito armazenando os valores da placa quando uma solução é encontrada. Esses valores serão armazenados em
- A abordagem de força bruta exaustiva não é adequada para este problema porque existem muitos arranjos possíveis e muito poucas soluções.
- A força bruta aleatória é bastante rápida, pois encontra apenas uma solução. A abordagem exaustiva da força bruta é lenta, mas ainda encontra apenas uma solução rapidamente. Se quiséssemos encontrar apenas algumas soluções, ambas funcionariam. No entanto, se quiséssemos encontrar todas as soluções, ambas precisariam ser modificadas.
Vamos modificar a função placeQueen e renomeá-la para placeQueenRandomly. A versão modificada simplesmente tenta colocar uma rainha em um quadrado aleatório.
A função placeQueenRandomly:
Passo 2
Também teremos que modificar a função EightQueens. Agora, ele manterá uma contagem das rainhas colocadas. Ele também verificará se há casas disponíveis no tabuleiro para que uma rainha seja colocada. Ele também retornará o número de rainhas colocadas.
A função das oito Rainhas:
Também teremos que modificar main para executar a função EightQueens até que uma solução seja encontrada, ou seja, 88 rainhas foram colocadas. Também introduziremos uma nova função clearBoard que simplesmente limpa o quadro antes de tentar uma nova solução.
A função principal modificada:
The clearBoard function:
Passo 3
int soluções[100][8][8] = { -1 };
O primeiro número é o número de soluções que podem ser armazenadas. O segundo e o terceiro são usados para armazenar os valores reais da placa.
Por exemplo, solutions[0] é uma solução possível. solutions[0][0] é a primeira linha dessa solução. solutions[0][0][0] é o elemento na primeira linha da primeira coluna dessa solução.
Para armazenar uma solução, introduzimos uma nova função, apropriadamente denominada storeSolution:
Esta função armazena o estado da placa, quando uma solução é alcançada, no array de soluções.
Para colocar uma rainha, usaremos a função placeQueen. Agora, para verificar todos os quadrados possíveis para cada quadrado, precisaríamos escrever 6464 para loops. Em vez disso, usaremos recursão.
A função placeQueen:
Agora, para cada quadrado possível, verificaremos todos os outros quadrados possíveis usando recursão. Agora, também precisamos verificar se uma rainha pode ser colocada na linha e coluna fornecidas. Além disso, cada chamada para placeQueen precisa ter seu próprio tabuleiro, pois cada tabuleiro é único porque estamos tentando todos os movimentos possíveis.
A função printIfNew, usada na função placeQueen, verifica se a solução é nova comparando-a com todas as soluções anteriores. Então, se for novo, imprime e armazena.
A função:
A função oitoQueens modificada e funções auxiliares:
Passo 4
Resposta
Ver o desenvolvimento!!!