Запрос о решении N-Queen?

Я решил задачу 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);
          }
      }  
  }

c++ depth-first-search n-queens
person Ankit    schedule 15.10.2010    source источник

Ответы (1)


arrow_upward
4
arrow_downward

Что ж, вы можете проверить уникальность решения только тогда, когда у вас есть решение. Место для проверки находится в точке, где вы увеличиваете переменную 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

При этом гораздо меньше данных передается/извлекается, и это значительно увеличивает скорость.

person Skizz    schedule 15.10.2010