c++ - 查询N- Queen解法？

我解决了N-Queen问题，条件是每列只能有一个Queen。因此，我将皇后放在第一列的正方形中，然后移至下一列，并将皇后放置在不受皇后攻击的正方形中。
我可以使用这种方法找到所有解决方案，但是在n = 13之后开始花费很长时间。我还发现，大多数问题的解决方案可以通过很少几个不同解决方案的旋转和反射找到。例如8个皇后问题共有92个解决方案，其中只有12个是不同的。 (http://en.wikipedia.org/wiki/Eight_queens_puzzle)

所以我的问题是如何检查电路板的这些状态，然后仅将这些状态压入堆栈以提供独特的解决方案？

这就是我现在正在做的。

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);
          }
      }
  }

最佳答案

好吧，只有找到解决方案后，您才能检查唯一的解决方案。检查的地方是您增加count变量的位置。此时，将当前电路板与一组唯一的电路板进行比较，如果不在其中，则向其添加新的解决方案。

至于您的速度，在推送和弹出state值时，您的解决方案会遇到瓶颈。木板越大，速度越慢。

一种更快的方法是只有一块木板，并且让每个方块保持控制方块的皇后数量。因此，您将拥有:

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

这样可以大大减少被推入/弹出的数据，并且将大大提高速度。

关于c++ - 查询N- Queen解法？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/3940747/