2

我解决了 N-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);
          }
      }  
  }
4

1 回答 1

4

好吧，只有找到解决方案后，您才能检查唯一的解决方案。检查的地方是你增加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

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

于 2010-10-15T10:16:23.020 回答