2

私は、列ごとに1つのクイーンしか存在できないという条件で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);
          }
      }  
  }
4

1 に答える 1

4

さて、あなたが解決策を持って初めて、あなたはユニークな解決策をチェックすることができます。チェックする場所は、count変数をインクリメントするポイントです。この時点で、現在のボードを一意のボードのセットと比較し、セットに含まれていない場合は、新しいソリューションを追加します。

速度に関しては、値をプッシュおよびポップするときにソリューションにボトルネックがありstateます。ボードが大きいほど、これは遅くなります。

はるかに速い方法は、ボードを1つだけ持ち、各正方形に、その正方形を制御しているクイーンの数をカウントさせることです。だからあなたはこれを持っているでしょう：

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 に答える