5 reines sur un échiquier 8x8

Question

J'essaie de trouver le nombre de façons possibles de placer 5 reines sur un échiquier sans qu'elles puissent s'attaquer l'une à l'autre. J'ai réussi à trouver le premier set. Le problème est de savoir comment je serais capable de trouver la prochaine série de positions pour 5 reines. La procédure dans mon programme est comme ceci:

• Générez un vecteur de positions non admises sur la base des reines actuelles sur la carte
• boucle à travers toutes les positions sur la carte
• Vérifiez si la position actuelle est un des positions non admises sur la carte
• Dans le cas contraire, le retour de la position, l'ajouter au vecteur des reines sur le plateau et recommencer le processus

Continuer jusqu'à ce qu'il n'y a pas plus p osition disponible à-dire toutes les positions restantes sont refusé

#include <iostream> 
#include <vector> 

using namespace std; 
const int BSIZE = 8; 
char chessBoard[BSIZE][BSIZE]; 

struct qPos 
{ 
    qPos() : h(0), v(0), found(true) {} 
    int h; //horizontal pos 
    int v; //vertical pos 
    bool found; //if position is available 
}; 

qPos findNextQPos(vector<qPos> Qs); 
void fillBoard(vector<qPos> Qs); 
void print(); 
vector<qPos> generateDisallowed(vector<qPos> Qs); 
bool isDisallowed(qPos nextPos, vector<qPos> disallowedPos); 

int main(int argc, char **argv){ 
    vector<qPos> QsOnBoard; //Position of all the queens on board 
    qPos nextQ; //next possible position 
    while (nextQ.found) 
    { 
     nextQ = findNextQPos(QsOnBoard); 
     if (nextQ.found) 
     { 
      QsOnBoard.push_back(nextQ); //If the nextQ is available i.e. not disallowed, add it to the queens vector 
     } 
    } 
    fillBoard(QsOnBoard); //Fill the board with queens positions 
    print(); // print the board 
    return 0; 
} 

qPos findNextQPos(vector<qPos> Qs) { 
    // Generate disallowed positions based on all the queens on board 
    vector <qPos> disallowedPos = generateDisallowed(Qs); 
    qPos nextQ; 
    for (size_t i = 0; i < BSIZE; i++) 
    { 
     for (size_t j = 0; j < BSIZE; j++) 
     { 
      nextQ.h = i; 
      nextQ.v = j; 
      if (!isDisallowed(nextQ, disallowedPos)) { //Check if next possible position is a disallowed position 
       //cout << "Next available:\n" << nextQ.h << ", " << nextQ.v << endl; 
       return nextQ; // if it is avaible return the position, break the loop 
      } 
     } 
    } 
    nextQ.found = false; // No available position is found to return, found is set to false, return the position 
    return nextQ; 
} 

reste du code source où j'ai les autres fonctions, telles que de générer et rejeté et isDisallowed etc est sur this pastebin. Je pensais que ce ne serait pas vraiment lié à la question et le code ne devrait pas être trop long.

Le résultat du premier jeu ressemble à ceci: Alors, comment dois-je continuer pour être en mesure de trouver tous les jeux de solution? C'est là que je suis coincé.

Answer 1

D'abord, combiner ces deux boucles en un seul:

for (size_t i = 0; i < BSIZE; i++) 
{ 
    for (size_t j = 0; j < BSIZE; j++) 
    { 

Au lieu de cela:

for (size_t n = 0; n < (BSIZE * BSIZE); ++n) 
{ 
    size_t i = n % BSIZE; 
    size_t j = n/BSIZE; 

Maintenant, votre fonction peut facilement prendre à partir n. Pour trouver la "prochaine" solution, retirez simplement la dernière reine (en notant sa position) et appelez le FindNextQPos, en lui disant de commencer à la position un passé de cette reine. Si cette reine est déjà à la dernière position, revenez en arrière et retirez une autre reine.

Si vous ne trouvez pas de solution, faites la même chose que si vous trouviez une solution. Retirez la dernière reine et appelez le FindNextQPos, en commençant encore une fois après la position de la reine que vous avez enlevée.

Lorsque vous n'avez plus de reines à enlever, vous avez terminé.

Vous pouvez le faire avec une seule fonction "continue". Vous pouvez appeler cette fonction si vous avez trouvé une solution ou si vous n'avez trouvé aucune solution. Sa logique est:

1. Trouvez la dernière reine. S'il n'y a pas de dernière reine, arrête. Nous avons fini.

2. Notez sa position. Retirez-le.

3. Appelez FindNextQPos en commençant à la position après la position que nous avons notée. Si nous avons placé une reine, continuez à essayer de placer plus de reines à partir de la position zéro jusqu'à ce que nous trouvions une solution ou que nous ne puissions pas placer une reine.

4. Si nous avons trouvé une solution, envoyez-la.

5. Passez à l'étape 1.