Interrogez-vous sur N-Queen?

Question

J'ai résolu le problème N-Queen avec la condition qu'il ne peut y avoir qu'un seul reine par colonne. Donc, je place une reine dans un carré dans la première colonne, puis déplacez-vous sur la colonne suivante et placez une reine dans un carré non attaqué par la reine à bord. Je suis capable de trouver toutes les solutions avec cette approche mais cela commence à prendre du temps après n = 13. J'ai également trouvé que la plupart des solutions du problème peuvent être trouvées par des rotations et des réflexions de très peu de solutions distinctes. Par exemple, le problème de 8 reines a 92 solutions totales dont seulement 12 sont distinctes. (http://en.wikipedia.org/wiki/Eight_queens_puzzle)

Donc, ma question est comment puis-je vérifier pour ces états de la carte et seulement pousser ces états sur la pile qui donnent une solution distincte?

C'est ce que je suis en train de faire.

typedef struct state{ 
    int board[N][N]; 
    int col; 
}state; 

state cur; 
state next; 

stack<state> myS; 
myS.push(emptyBoard); 

while(!myS.empty()){   
     cur=myS.top(); myS.pop(); 
     if(cur.col==n){ 
      count++; 
      continue; 
     } 
     for(i=0;i<n;i++){ 
      next=cur; 
      if(cur.board[i][cur.col]==available){ 
       next.board[i][cur.col]=occupied; 
       markConflicts(i,cur.col);   //mark squares attacked by queen as conflicted 
       next.col=cur.col+1; 
       myS.push(next); 
      } 
     } 
    } 

Answer 1

Eh bien, vous ne pouvez vérifier une solution unique qu'une fois que vous avez une solution. L'endroit à vérifier est au moment où vous incrémentez la variable count. À ce stade, comparez la carte actuelle à un ensemble de cartes uniques et si elle n'est pas dans l'ensemble, ajoutez-y la nouvelle solution.

En ce qui concerne votre vitesse, votre solution a un goulot d'étranglement lorsque vous appuyez sur la valeur state et que vous la saisissez. Plus le plateau est grand, plus il devient lent.

Un moyen beaucoup plus rapide est de n'avoir qu'une seule planche et de faire en sorte que chaque carré tienne compte du nombre de reines contrôlant le carré. Donc, vous auriez ceci:

function scan (column) 
    if column == number of columns (zero based index) 
    check solution 
    else 
    if there's a free space 
     add queen 
     increment controlled squares in columns to right of current column 
     scan (column+1) 
     decrement controlled squares in columns to right of current column 
     remove queen 

Ceci a beaucoup moins de données étant poussé/coupé et augmentera considérablement la vitesse.