8 Queens Problem C ++
Qual é o problema do 8 Queens em C++?
O problema do N-Queens 'ou 8 Queens' refere-se à situação em que você deseja colocar o número de rainhas em um quadro de xadrez de uma maneira que nenhuma rainha possa ser atacada por outro vertical, horizontal ou diagonal, eu.e., Todas as rainhas devem ser posicionadas com tanta inteligência que nenhum deles possa ser atacado pelo outro de qualquer forma.
Como resolver o problema do 8 Queens em C ++ no Ubuntu 20.04?
Neste segmento, compartilharemos com você o procedimento de resolver o problema do 8 Queens em C++. Para alcançar esse objetivo, projetamos um código C ++ mostrado na imagem abaixo. No entanto, antes de prosseguir com a explicação deste código, gostaríamos de compartilhar com você que dividimos esse código em pequenos trechos para o seu entendimento fácil. Dividimos aproximadamente esse programa C ++ em uma função para imprimir todos os diferentes estados do quadro de xadrez que satisfazem a solução do problema do 8 Queens, uma função para verificar se uma posição específica é segura para colocar a rainha ou não, uma função para resolvendo o problema do 8 Queens usando o algoritmo de backtracking e, finalmente, a função principal do driver. Estaremos discutindo todos esses trechos um por um.
No primeiro trecho do nosso código, depois de incluir a biblioteca e o espaço para nome, definimos um tabuleiro de xadrez de tamanho 10 x 10 na forma de uma matriz 2D. Isso significa que nosso programa será capaz de tomar 10 rainhas 'no máximo para resolver o problema n-feens' em c++. No entanto, neste artigo, estamos preocupados principalmente com o problema do 8 Queens. Depois de definir o tabuleiro de xadrez, temos nossa função "Printboard" que leva um número inteiro "n" como entrada que se refere ao número de rainhas, eu.e., 8 Neste caso em particular. Dentro dessa função, temos um loop "para" aninhado para simplesmente imprimir o quadro de xadrez no terminal toda vez que essa função é chamada. Em seguida, temos algumas declarações de "cout" para imprimir espaços adequados entre os diferentes estados do tabuleiro de xadrez resolvido.
No segundo trecho do nosso código C ++, temos a função "ISSSAFE" que existe para verificar se será seguro colocar uma rainha em uma posição específica ou não. Por "seguro", queremos dizer que nenhuma outra rainha pode atacar uma rainha em particular verticalmente, horizontalmente ou diagonal. Em seguida, temos três loops independentes "para" nesta função que estão lá para verificar todas as três condições separadamente. Se alguma dessas condições se tornar verdadeira, então a função "Issafe" retornará "falsa" porque nesses casos, sempre haverá uma chance de ataque, por causa da qual não seremos capazes de colocar uma rainha na posição em particular. No entanto, se todas essas condições se tornarem falsas, eu.e., Não há chance de ataque nessa posição verticalmente, horizontalmente ou diagonal, somente então a função "issafe" retornará "verdadeiro" eu.e., Será seguro colocar uma rainha na posição específica.
No terceiro trecho do nosso código C ++, temos a função de "solução" que elaborará a solução do problema do N-Queens usando o algoritmo de backtracking. Dentro desta função, a primeira declaração "se" é usada para verificar se o número da rainha é igual ao número total de rainhas ou não. Se esta declaração avaliar como verdadeira, a função "Printboard" será chamada instantaneamente. Caso contrário, uma variável booleana "resultado" será definida cujo estado inicial é mantido "falso". Em seguida, temos outro loop "para" dentro do qual chamamos iterativamente a função "issafe" para cada uma das rainhas para descobrir se a posição fornecida é segura para colocá -la ou não. Dentro dessa condição, usamos a recursão para executar a trilha de volta para colocar as rainhas nas posições mais seguras para que elas não possam ser atacadas por nenhuma outra rainha. Aqui, "1" representará que uma rainha é colocada em uma posição específica, enquanto "0" representará todas as posições vazias do quadro de xadrez. Finalmente, retornamos a variável "resultado" para notificar se a solução para o número dado de rainhas é possível ou não.
No último trecho do nosso código C ++, temos a função principal do driver. A razão por trás do uso das duas primeiras declarações dentro da nossa função "main ()" é a otimização do desempenho porque, para um número maior de rainhas, seu programa pode executar irracionalmente mais lento. No entanto, você pode pular isso, se desejar,. Em seguida, definimos um número inteiro "n" que corresponde ao número de rainhas. Depois disso, exibimos uma mensagem no terminal para levar o usuário a inserir o número de rainhas para as quais ele/ela deseja resolver o problema da n-Queens. Então, simplesmente adquirimos isso como entrada do usuário. Depois disso, temos um loop aninhado "para" no qual chamamos a função "tabuleiro de xadrez". Em seguida, chamamos a função de "solução" e armazenamos sua saída na variável "resultado". Se o valor da variável "resultado" será "falso", isso significará que não existe solução para o número dado de rainhas. Por fim, temos a declaração "Return 0" para encerrar nosso código.
Para compilar este código, usamos o seguinte comando:
$ g ++ 8queens.CPP -O 8QUEENSPara executar este código, usamos o comando anexado abaixo:
$ ./8queensFomos convidados a inserir o número de rainhas, como mostrado na imagem a seguir:
Entramos "8" para o nosso caso específico, como mostrado na imagem abaixo:
Assim que você fornecer o número de rainhas, todas as soluções possíveis para o problema do 8 Queens aparecerão no terminal, como mostrado na imagem a seguir:
Para testar este código para o outro caso, eu.e., A solução não existe, fornecemos “3” como o número de rainhas. Isso é mostrado na imagem abaixo:
Entendemos que, para um quadro de xadrez de 3 x 3, não existe solução; É por isso que recebemos a seguinte saída:
Conclusão
Este artigo foi sobre o problema do 8 Queens em C ++ no Ubuntu 20.04. Explicamos a você brevemente sobre esse problema e todas as condições que devem ser satisfeitas para resolver este problema. Depois disso, compartilhamos com você um programa C ++ completo que resolverá esse problema para você para 8 rainhas ou no máximo 10 rainhas. Além disso, também testamos este código para um caso em que a solução para esse problema é impossível. Felizmente, depois de ler este guia, você terá uma boa compreensão do famoso 8 do Queens do Queens em C++.