关于N-Queen求解的疑问？

我解决了N皇后问题，条件是每列只能有一个皇后。所以我把女王放在第一列的正方形中，然后移动到下一列，并将女王放置在未受女王船员攻击的广场上。我能够使用这种方法找到所有的解决方案，但是在n = 13之后开始需要很长时间。此外，我发现问题的大多数解决方案都可以通过旋转和反射几个不同的解决方案来找到。例如，女王问题共有92个解决方案，其中只有12个解决方案是不同的。（http://en.wikipedia.org/wiki/Eight_queens_puzzle）关于N-Queen求解的疑问？

所以我的问题是我如何检查板的这些状态，只把这些状态推到栈上给出了一个独特的解决方案？

这就是我现在正在做的。

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

来源

2010-10-15 Ankit

那么，一旦你有解决方案，你只能检查一个独特的解决方案。要检查的地方是增加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-15 10:16:23 Skizz

关于N-Queen求解的疑问？

回答

相关问题