关于 N-Queen 求解的疑问？

Question

我解决了N皇后问题，条件是每列只能有一个皇后。因此，我将皇后放置在第一列的方格中，然后移动到下一列，并将皇后放置在船上未被皇后攻击的方格中。 我能够用这种方法找到所有解决方案，但在 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);
          }
      }  
  } 

Answer 1

好吧，只有在有了解决方案后，您才能检查唯一的解决方案。要检查的位置是您递增 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

这样推送/弹出的数据要少得多，并且会大大提高速度。