Вопрос о решении N-Queen? - PullRequest
Новая
       4

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

2 голосов
/ 15 октября 2010

Я решил проблему 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);
          }
      }  
  }

1 Ответ

4 голосов
/ 15 октября 2010

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

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

...