c++ - 关于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

这有更少的数据被推送/弹出，并且会大大提高速度。