8-Queens算法示例？

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-neted循环的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皇后问题的解决方案.i数组的-th元素表示i放在i第-列上的第 - 个皇后的行位置(所有索引都是从0开始的).所以,第一个解决方案在板上看起来像这样:

[0,2,4,1,3]

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

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

快乐学习.