Проблема 8 королев

Question

Как мне решить проблему 8/4 ферзей? Если я использую DFS / BFS, я думаю, что DF будут лучше Может ли кто-нибудь дать какой-нибудь псевдокод / ​​гайдлайн?

Answer 1

Использование стека и обратного отслеживания, самый простой способ - через рекурсию.

См. Эти другие сообщения SO:

Тупая проблема 8 ферзей в C ++

Answer 2

DFS - действительно решение, которое должно быть реализовано как возврат.

См. здесь для описания решения.

Если вы не понимаете описание по ссылке, пожалуйста, спросите..

Answer 3

Если королевы имеют координаты (i, j) и (k, l), то они могут атаковать друг друга, если

1. i = k (та же строка)
2. j = l (тот же столбец)

3. | я-к | = | J-л | (По диагонали), | | обозначает абсолютное значение

   bool place(k,i)
   {
   //returns true if the queen can be placed at k-th row and i-th column
   //x[] is a global array with first (k-1) values set already.
   //x[p]=q means a queen is at location (p,q)
   
   for(j=1 to k-1)
   {
   if(x[j]==i)||(ABS(x[j]-i)==ABS(j-k))  //checking if another queen in same column or     diagonally
   return false;
   }
   return true;
   }
   

   Чтобы распечатать все возможные места размещения с помощью возврата:

   void NQueens (k, n) {

   for(i=1 to n)
   {
   if(place(k,i)) //checking if queen can be placed at (k,i)
   {
   x[k]=i;
   if(k==n) then write (x[1:n]);  
   else Nqueens(k+1,n);
    }
    }
   }
   

* По рекомендации школы Саураб

Answer 4

Мое решение имеет 2 предопределенные логики, в строке есть только одна королева, а в столбце только одна королева.Существует одномерный массив, длина которого равна 8. Все значения массива устанавливают один из 0-7, но все значения используются ровно один раз (перестановка значений, которые 0-7)6 в первой строке arr [1] = 3 означает королеву в столбце 4 во второй строке, просто управляйте значениями перекрестного нарушения при проверке массива, нет необходимости проверять строку или нарушение строки.Все функции перестановки и нарушения, все что вам нужно, (C ++ STL имеет функции перестановки, которые просто должны пересекать функции нарушения)