java - (8 Queens) 判断一个皇后是否适合二维矩阵

Question

我正在尝试编写一个程序，使用二维 boolean 数组解决 8 Queens 问题。我将使用回溯来找到解决方案。我知道这不是解决此问题的最佳方法，为了简单起见，我可能应该使用一维数组，但我想以这种方式解决它。

现在我被困在应该检查女王是否适合给定坐标的功能上。我的行、列和右下对角线检查有效，但我无法进行左下对角线检查。我正在努力寻找 i 和 j(x 和 y)的正确索引以开始，以及每次迭代要递增/递减的计数器。现在我的函数看起来像这样:

public static boolean fits(int x, int y) {

    for(int i = 0; i < N; i++) {
        if(board[x][i]) {
            return false; // Does not fit on the row
        }
    }

    for(int i = 0; i < N; i++) {
        if(board[i][y]) {
            return false; // Does not fit on the column
        }
    }

    for(int i = Math.max(x-y, 0), j = Math.max(y-x, 0); i < N && j < N; i++, j++) {
        if(board[i][j]) {
            return false; // Down right diagonal issue
        }
    }

    for(int i = Math.min(x+y, N-1), j = Math.max(N-1-x, 0); i >= 0 && j < N; i--, j++) {
        if(board[i][j]) {
            return false; // Supposed to check the down-left diagonal, but does not work.
        }
    }

    return true;
}

如您所见，此处的最后一个循环存在问题。如果有人能给我一个工作循环来检查左下对角线，我会非常非常高兴。提前致谢!

---

编辑:这是工作代码:

public class MyQueens {

    static boolean[][] board;
    static final int N = 8;

    public static void main(String[] args) {
        int p = 0;

        board = new boolean[N][N];

        board[1][1] = true;

        System.out.println(fits(0, 2));
        System.out.println(fits(2, 2));
    }

    public static boolean fits(int x, int y) {

        for(int i = 0; i < N; i++) {
            if(board[x][i]) {
                return false; // Row
            }
        }

        for(int i = 0; i < N; i++) {
            if(board[i][y]) {
                return false; // Column
            }
        }

        for(int i = 0, j = 0; i < N && j < 0; i++, j++) {
            if(board[i][j]) {
                return false; // for right diagonal
            }
        }

        int mirrorx = (N-1)-x;
        for(int i = Math.max(mirrorx-y, 0), j = Math.max(y-mirrorx, 0); i < N && j < N; i++, j++) {
            if(board[(N-1)-i][j]) {
                return false;
        }
    }

        return true;
    }

}

Answer 1

I'm attempting to write a program which solves the 8 Queens Problem using a 2 dimensional array of booleans.

这不是最佳表示，因为您必须使用四个循环来检查是否可以放置皇后。有一种更快的方法可以做到这一点。

为了您的程序的目的，为了放置女王，有四件事必须不受威胁:

• 一行，
• 专栏，
• 上升对角线，和
• 下降对角线

这四种东西中的每一种都可以用一个单独的 boolean 数组来建模。有 8 行、8 列、15 条上升对角线和 15 条下降对角线(包括角落处单细胞“对角线”的两种退化情况)。

声明四个数组row[8]、col[8]、asc[15] 和desc[15]，并使用这四种方法来处理它:

public static boolean fits(int r, int c) {
    return !row[r] && !col[c] && !asc[r+c] && !desc[c-r+7];
}
public static void add(int r, int c) {
    set(r, c, true);
}
public static void remove(int r, int c) {
    set(r, c, false);
}
private static void set(int r, int c, boolean q) {
    row[r] = col[c] = asc[r+c] = desc[c-r+7] = q;
}