Алгоритм решения головоломки N Queens Domination

Question

Я решил более общую проблему N Queens, но сейчас я ищу алгоритм для решения проблемы N Queens Domination.

"Для данной доски n × n найдите номер доминирования, который представляет собой минимальное количество ферзей (или других фигур), необходимое для атаки или захвата каждого квадрата. Для доски 8 × 8 номер доминирования ферзя равен 5. " - Википедия

Я много искал и не могу найти ничего, кроме научных работ по этой проблеме, ничего, что можно было бы понять.

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

Любая помощь будет оценена, спасибо.

Answer 1

Используя свой алгоритм, вы можете сгенерировать все возможные комбинации и извлечь из него минимум.Подсказки: используйте рекурсию для этого и не обрабатывайте подобные условия (или кешируйте их), такие как симметричное размещение, тот же порядок и т. Д.

Answer 2

В духе того, что это вопрос домашней работы, я не буду предлагать решение, а скорее ряд вопросов, которые приведут к решению. Ниже приведен способ ответить «можете ли вы доминировать на доске с n ферзями?» Затем вы можете найти номер доминирования, протестировав n = 1, n = 2, ...

1) Поместив ферзя в положение 1 *, можно ли тогда доминировать над всеми оставшимися позициями, не достигнутыми королевой 1, разместив (n - 1) ферзей в (n - 1) позициях, выбранных из (2,3, ..). .)

2) Если нет, можете ли вы поместить королеву в позицию 2, а затем доминировать над всеми оставшимися позициями, не достигнутыми королевой 1, разместив (n - 1) ферзей в (n - 1) позициях, выбранных из (3,4, ...)

3) и так далее, т. Е. Поместите сначала ферзя в положение 3, затем в положение 4 и т. Д.

Обратите внимание, что это решение является рекурсивным - при каждой рекурсии в качестве аргументов передаются «оставшиеся позиции для добавления ферзя» и «позиции, которые еще не достижимы ни одной маткой». Когда «позиции, которые еще не доступны ни одной королеве» пустые, вы нашли решение.

* упорядочить все позиции доски каким-либо образом, например слева направо, сверху вниз. Таким образом, 64 позиции на доске 8x8 могут быть обозначены только индексом (1..64).

Answer 3

int count;

int safetyOfThisPosition(int col,int row,int *x)

{

       int iterator;
       for(iterator=0;iterator<col;iterator++)
       {
        if(row==x[iterator] || abs(col-iterator)==abs(row-x[iterator]))
           return 0;
       }
       return 1;
}

void Nqueen(int col){

       int row,iterator;
       static int x[N];  
       for(row=0;row<N;row++)  
       {
           if(safetyOfThisPosition(col,row,x))
           {
               x[col]=row;
               if(col==N-1)
               {
                   for(iterator=0;iterator<=col;iterator++)
               printf("%d  ",x[iterator]);
                   printf("\n");
               }
               else
                   Nqueen(col+1);
           }
       }

   }

int main(){

       Nqueen(0);
       return 0;
   }

Answer 4

Следующее не эффективно, но оно будет работать.

Переформулируйте задачу как задачу целочисленного программирования.Каждый квадрат на доске равен 0 или 1. Для любого квадрата сумма его самого и всех атакующих квадратов должна быть ровно 1. И вы хотите уменьшить общую сумму.