8 reines Problème C ++

C ++ peut être utilisé pour résoudre des problèmes très complexes mais intéressants. Un tel problème crucial en C ++ est le problème des N-Queens, où «n» représente le nombre total de reines sur l'échec. Maintenant, vous vous demandez peut-être ce qu'est réellement ce problème et comment vous pouvez le résoudre avec C++. Vous pourrez découvrir les réponses à ces questions après avoir parcouru cet article.

Quel est le problème des 8 reines en C++?

Le problème des N-Queens ou 8 Queens fait référence à la situation dans laquelle vous souhaitez placer le nombre donné de reines sur un échec d'une manière qu'aucune reine ne peut être attaquée par un autre verticalement, horizontalement ou en diagonale, je.e., Toutes les reines doivent être positionnées si intelligemment qu'aucun d'eux ne peut être attaqué par l'autre de quelque manière que ce soit.

Comment résoudre le problème des 8 reines en C ++ dans Ubuntu 20.04?

Dans ce segment, nous partagerons avec vous la procédure de résolution du problème des 8 reines en C++. Pour atteindre cet objectif, nous avons conçu un code C ++ illustré dans l'image ci-dessous. Cependant, avant d'expliquer ce code, nous aimerions partager avec vous que nous avons divisé ce code en petits extraits pour votre compréhension facile. Nous avons à peu près divisé ce programme C ++ en une fonction pour imprimer tous les différents états de l'échec Résoudre le problème des 8 Queens en utilisant l'algorithme de retour en arrière, et enfin, la fonction principale du pilote. Nous discuterons de tous ces extraits un par un.

Dans le premier extrait de notre code, après avoir inclus la bibliothèque et l'espace de noms, nous avons défini un échec de taille 10 x 10 sous la forme d'un tableau 2D. Cela signifie que notre programme sera capable de prendre 10 reines au maximum pour résoudre le problème des N-Queens en C++. Cependant, dans cet article, nous sommes principalement préoccupés par le problème des 8 reines. Après avoir défini l'échecteur, nous avons notre fonction «Printboard» qui prend un «N» entier comme entrée qui fait référence au nombre de reines, je.e., 8 Dans ce cas particulier. Dans cette fonction, nous avons une boucle «pour» imbriquée pour simplement imprimer l'échecteur sur le terminal chaque fois que cette fonction est appelée. Ensuite, nous avons des déclarations «cout» pour l'impression d'espaces adéquats entre les différents états de l'échiquier résolu.

Dans le deuxième extrait de notre code C ++, nous avons la fonction «ISSAFE» qui est là pour vérifier s'il sera sûr de placer une reine à une position particulière ou non. Par «sûr», nous voulons dire qu'aucune autre reine ne peut attaquer une reine en particulier verticalement, horizontalement ou en diagonale. Ensuite, nous avons trois boucles «pour» indépendantes dans cette fonction qui sont là pour vérifier séparément les trois conditions. Si l'une de ces conditions devient vraie, alors la fonction «issafe» retournera «fausse» car dans ces cas, il y aura toujours une chance d'attaque, car nous ne pourrons pas placer une reine à la position particulière. Cependant, si toutes ces conditions deviennent fausses, je.e., Il n'y a aucune chance d'attaquer à cette position verticalement, horizontalement ou en diagonale, seulement alors la fonction «issafe» renverra «vrai» i.e., Il sera sûr de placer une reine à la position particulière.

Dans le troisième extrait de notre code C ++, nous avons la fonction «solution» qui conçoit la solution du problème des N-Queens en utilisant l'algorithme de retournement. Dans cette fonction, la première instruction «IF» est utilisée pour vérifier si le numéro de reine est égal au nombre total de reines ou non. Si cette instruction évalue pour être vraie, alors la fonction «Printboard» sera instantanément appelée. Sinon, un «résultat» variable booléen sera défini dont l'état initial est gardé «faux». Ensuite, nous avons une autre boucle «pour» dans laquelle nous appelons itérativement la fonction «ISSAFE» pour chacune des reines pour savoir si la position donnée est sans danger pour la placer ou non. Dans cette condition, nous avons utilisé la récursivité pour effectuer le retour en arrière pour placer les reines aux positions les plus sûres afin qu'ils ne puissent être attaqués par aucune autre reine. Ici, «1» représentera qu'une reine est placée à une position particulière, tandis que «0» représentera toutes les positions vides de l'échec. Enfin, nous avons retourné la variable «Résultat» pour indiquer si la solution au nombre de reines données est possible ou non.

Dans le dernier extrait de notre code C ++, nous avons la fonction principale du pilote. La raison derrière l'utilisation des deux premières déclarations dans notre fonction «Main ()» est l'optimisation des performances car, pour un plus grand nombre de reines, votre programme pourrait exécuter des. Cependant, vous pouvez les sauter si vous le souhaitez. Ensuite, nous avons défini un «n» entier qui correspond au nombre de reines. Après cela, nous avons affiché un message sur le terminal pour inciter l'utilisateur à saisir le nombre de reines pour lesquelles il veut résoudre le problème des N-Queens. Ensuite, nous avons simplement acquis cela comme entrée de l'utilisateur. Après cela, nous avons une boucle «pour» imbriquée dans laquelle nous avons appelé la fonction «échec». Ensuite, nous avons appelé la fonction «Solution» et stocké sa sortie dans la variable «Résultat». Si la valeur de la variable «Résultat» sera «fausse», cela signifiera qu'aucune solution n'existe pour le nombre donné de reines. Enfin, nous avons l'instruction «Return 0» pour terminer notre code.

Pour compiler ce code, nous avons utilisé la commande suivante:

$ g ++ 8Queens.CPP -O 8QUEENS

Pour exécuter ce code, nous avons utilisé la commande annexée ci-dessous:

$ ./ 8Queens

On nous a d'abord demandé d'entrer le nombre de reines comme indiqué dans l'image suivante:

Nous avons entré «8» pour notre cas particulier, comme indiqué dans l'image ci-dessous:

Dès que vous fournissez le nombre de reines, toutes les solutions possibles au problème des 8 reines apparaîtront sur le terminal comme indiqué dans l'image suivante:

Pour tester ce code pour l'autre cas, je.e., La solution n'existe pas, nous avons fourni «3» comme nombre de reines. Ceci est montré dans l'image ci-dessous:

Nous comprenons que pour un échec de 3 x 3, aucune solution n'existe; C'est pourquoi nous avons reçu la sortie suivante:

Conclusion

Cet article concernait le problème des 8 reines en C ++ dans Ubuntu 20.04. Nous vous avons expliqué brièvement ce problème et toutes les conditions qui doivent être remplies pour résoudre ce problème. Après cela, nous avons partagé avec vous un programme C ++ à part entière qui résoudra ce problème pour vous pour 8 reines ou chez Max 10 Queens. De plus, nous avons également testé ce code pour un cas où la solution à ce problème est impossible. J'espère qu'après avoir lu ce guide, vous aurez une bonne compréhension du problème du célèbre 8 reines en C++.