8 皇后解决方案 Java 代码的解释。

Question

我找到了一个可以在 Eclipse 中编译和运行的 8-Queen 解决方案。我相信这个解决方案遵循回溯方法，主要工作是在 solution 和 unsafe 函数中完成的，但我很难理解其中的代码路径。有人可以帮我理解这段代码在做什么吗？

我的来源 - http://rosettacode.org/wiki/N-queens_problem#Java 我根据其他来源发布的 92 个解决方案验证了输出。看起来不错。所以我知道代码有效。

我试着格式化它并添加一些基本的注释来清理它 -

private static int[] b = new int[8];
private static int s = 0;

public static void main(String[] args) {
    // solution from - http://rosettacode.org/wiki/N-queens_problem#Java
    new QueenN();
}

public QueenN() {
    solution();
}

public void solution() {
    int y = 0;
    b[0] = -1;
    while (y >= 0) {
        do {
            b[y]++;
        } while ((b[y] < 8) && unsafe(y));

        if (b[y] < 8) {

            if (y < 7) {
                b[++y] = -1;
            } else {
                putboard();
            }

        } else {
            y--;
        }
    }
}

// check if queen placement clashes with other queens
public static boolean unsafe(int y) {
    int x = b[y];
    for (int i = 1; i <= y; i++) {
        int t = b[y - i];
        if (t == x || t == x - i || t == x + i) {
            return true;
        }
    }
    return false;
}

// printing solution
public static void putboard() {
    System.out.println("\n\nSolution " + (++s));
    for (int y = 0; y < 8; y++) {
        for (int x = 0; x < 8; x++) {
            if (b[y] == x)
                System.out.print("|Q");
            else
                System.out.print("|_");
        }
        System.out.println("|");
    }
}

结束。

Answer 1

让我们尝试逐步理解代码。首先，我们调用函数 solution()，这就是导致拼图答案执行的原因。

解函数：

public void solution() {
    int y = 0;
    b[0] = -1;
    while (y >= 0) {
        do {
            b[y]++; //if last cell was unsafe or we reached the end of the board, we go for the next row.
        } while ((b[y] < 8) && unsafe(y)); //Checks whether it's the last cell and if it's an unsafe cell (clashing)

        if (b[y] < 8) { //We found a safe cell. Hooray!

            if (y < 7) { //Did we place the last queen?
                b[++y] = -1; //Nope, let's allocate the next one.
            } else {
                putboard(); //Yup, let's print the result!
            }

        } else { //If not a single safe cell was found, we reallocate the last queen.
            y--;
        }
    }
}

首先，您将遍历行中的每个单元格（或列中的每个单元格，但是您喜欢它。这只是一个旋转问题）。在每个单元格上进行 unsafe(y) 检查，如果您放置女王的单元格与其他女王占用的单元格发生冲突（正如您已经在评论中发现的那样），这将 return 为真).

下一步，一旦我们找到一个安全的单元格来放置实际的女王 (y)，我们就会进行安全检查：如果我们没有为那个女王找到一个安全的单元格，我们必须重新分配最后一位女王。

如果单元格被发现并且是正确的，我们检查它是否是最后一个女王 (y < 7)。如果是这样，我们继续打印结果。否则，我们只需通过放置 b[++y] = -1.

来重新启动 while 循环

不安全函数：

public static boolean unsafe(int y) {
    int x = b[y]; //Let's call the actual cell "x"
    for (int i = 1; i <= y; i++) { //For each queen before placed BEFORE the actual one, we gotta check if it's in the same row, column or diagonal.
        int t = b[y - i];
        if (t == x || t == x - i || t == x + i) {
            return true; //Uh oh, clash!
        }
    }
    return false; //Yay, no clashes!
}

此函数检查我们正在使用的皇后是否与在此之前分配的任何皇后发生冲突。冲突可能沿对角线、垂直或水平方向发生：这就是为什么在 "return true" 语句之前有一个三重或检查。

推板功能：

public static void putboard() {
    System.out.println("\n\nSolution " + (++s));
    for (int y = 0; y < 8; y++) {
        for (int x = 0; x < 8; x++) {
            if (b[y] == x)
                System.out.print("|Q");
            else
                System.out.print("|_");
        }
        System.out.println("|");
    }
}

这个我就不解释那么深了，因为它只是一个相当简单的行打印功能，你可以在执行解决方案时自行了解它是如何工作的！

希望对您有所帮助。

干杯！

8 皇后解决方案 Java 代码的解释。

Explanation of 8-Queen solution Java code.

java

backtracking

n-queens