c# - 8皇后算法示例？

Question

任何人都知道 8-queens 的好的/简洁的算法示例？我进行了网络搜索，但没有找到任何好的示例。

Answer 1

这是朴素递归算法的简单 Java 实现；它应该是有启发性的。

public class NQueens {
    final static int N = 4;
    static int[] position = new int[N];

    public static void main(String[] args) {
        solve(0);
    }

    static boolean isSafe(int k, int p) {
//      for (int i = 1; i <= k; i++) {
//          int other = position[k - i];
//          if (other == p || other == p - i || other == p + i) {
//              return false;
//          }
//      }
        return true;
    }
    static void solve(int k) {
        if (k == N) {
            System.out.println(java.util.Arrays.toString(position));
        } else {
            for (char p = 0; p < N; p++) {
                if (isSafe(k, p)) {
                    position[k] = p;
                    solve(k+1);
                }
            }
        }
    }
}

请注意 isSafe 现在包含注释行；这是故意的。注释掉这些行后，程序就变成了一个递归的 N 元组生成器，其中每个值都在 0(含)和 N(不含)之间.也就是说，程序按原样生成以下输出:

[0, 0, 0, 0]
[0, 0, 0, 1]
[0, 0, 0, 2]
[0, 0, 0, 3]
[0, 0, 1, 0]
[0, 0, 1, 1]
[0, 0, 1, 2]
[0, 0, 1, 3]
:
:
[3, 3, 3, 0]
[3, 3, 3, 1]
[3, 3, 3, 2]
[3, 3, 3, 3]

这个 N 元组生成是 NQueens 问题的具体子问题。当您不知道 N 是什么时，stackoverflow 上已经有很多关于如何编写 N 嵌套循环的问题。我觉得在这个问题上暂时停下来并首先了解它的解决方案是有指导意义的，将 isSafe 注释掉以简单地 return true;，首先感受一下递归确实如此。

一旦您对这个递归元组生成器的工作感到满意，只需取消注释这些行，您就会得到一个简单、朴素但有效的 NQueens 求解器。取消注释 N=5 和 isSafe 行后，程序现在生成以下输出:

[0, 2, 4, 1, 3]
[0, 3, 1, 4, 2]
[1, 3, 0, 2, 4]
[1, 4, 2, 0, 3]
[2, 0, 3, 1, 4]
[2, 4, 1, 3, 0]
[3, 0, 2, 4, 1]
[3, 1, 4, 2, 0]
[4, 1, 3, 0, 2]
[4, 2, 0, 3, 1]

每一行都是 5-queens 问题的解决方案。数组的第 i 元素表示放置在第 i 列的第 i 个皇后的行位置(所有索引都是0 为基础)。所以，第一个解决方案在黑板上看起来像这样:

[0,2,4,1,3]

 Q · · · ·
 · · · Q ·
 · Q · · ·
 · · · · Q
 · · Q · ·

我将把它留作练习，以了解为什么 isSafe 有效，如何打印电路板布局，以及如何实现更快但更复杂的递归算法。

快乐学习。