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

Question

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

Answer 1

Ну, вы можете проверить только уникальное решение, как только у вас есть решение. Место для проверки - это то, что вы увеличиваете count Переменная. На данный момент сравните нынешнюю доску на набор уникальных досок, и если это не в установленном состоянии, а затем добавьте его новое решение.

Что касается вашей скорости, ваше решение имеет узкое место при нажатии и выскакивания state стоимость. Чем большая доска, тем медленнее становится.

Гораздо более быстрый способ состоит в том, чтобы иметь только одну доску и у каждого квадрата сохраняют количество og количество королев, управляющих квадратом. Так что у вас будет это:

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

Это имеет гораздо меньшие данные, которые выдвинуты / выдвинуты / выскочили и значительно увеличит скорость.