解决N皇后问题的算法

Question

我已经解决了更通用的N皇后问题，但现在我正在寻找解决N皇后占领问题的算法。

“给定一个n×n的棋盘，找到控制数，即攻击或占领每个方格所需的最少皇后（或其他棋子）数量。对于8×8棋盘，皇后的控制数为5。“- 维基百科

我已经广泛搜索过这个问题，但除了学术论文之外，无法找到任何可以理解的东西。

我的第一个想法是只需要放置一位皇后，然后将下一位皇后放置在可以攻击大多数其他方格的地方，以此类推。然而，虽然这可能会生成一个解决方案，但我无法找到保证这个解决方案是最小解决方案的方法。

任何帮助都将不胜感激，谢谢。

- Michael Robinson

---

你想要解决“只有皇后”的问题，还是“包含皇后和其他棋子”的问题？我猜后者只有皇后和骑士，但仍然比仅有皇后的情况更难解决。 - Matthew Strawbridge

请将作业问题标记为“作业”，以便回答者清楚。特别是对于更琐碎的问题，知道是从教师还是同事的角度回答有所帮助。(https://wiki.engr.illinois.edu/display/cs242sp12/Assignment+1.1) - Aria Buckles

仅寻求皇后问题的解决方案。 - Michael Robinson

Answer 1

使用您的算法，可以生成所有可能的组合并从中取最小值。 提示: 对此使用递归，并且不要处理类似的条件（或缓存它），如对称放置、相同的顺序等。

- mishadoff

Answer 2

出于这是一个作业问题的精神，我不会提供解决方案，而是提供一系列问题，以引导解决方案。以下是回答“你能用n个皇后占领棋盘吗？”的方法。然后，您可以通过测试n=1、n=2等来找到占领数。

1）通过在位置1*放置一个皇后，您是否可以通过在（2,3,...）中选择（n-1）个位置，在（n-1）个位置上放置（n-1）个皇后，从而支配所有未被皇后1占领的剩余位置？

2）如果不能，您是否可以在位置2上放置一个皇后，然后通过在（3,4,...）中选择（n-1）个位置，在（n-1）个位置上放置（n-1）个皇后，从而支配所有未被皇后1占领的剩余位置？

3）以此类推...即将第一个皇后放在位置3，然后放在位置4等等。

请注意，此解决方案是递归的-在每次递归时，“要添加皇后的剩余位置”和“尚未被任何皇后到达的位置”作为参数传递。当“尚未被任何皇后到达的位置”为空时，您已经找到了一个解决方案。

将棋盘上的所有位置按照某种方式排序，例如从左到右，从上到下。这样，8x8棋盘上的64个位置可以通过索引（1..64）来引用。

- gcbenison

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;
   }

- Jijo Varghese

Answer 4

以下方法并不高效，但它可以解决问题。

将问题重新表述为整数规划问题。棋盘上的每个方格都是0或1。对于任何一个方格，它本身和所有攻击该方格的方格的总和应该恰好为1。您需要最小化总和。

- wye.bee