java - N-Queens 不打印所有解决方案

Question

我是递归和回溯的新手。我正在尝试完成 N-Queen 问题以打印所有解决方案而不是仅打印 1 个，并理解这些概念。

我认为我已经部分正确地实现了算法，因为我得到了一些解决方案，但并非全部打印出来。我的代码是用 Java 编写的。

• 对于 N = 4 的值，我得到 2 个解决方案 - 这是正确的
• 对于 N = 5 的值，我得到 5 个解决方案 - 实际上有 10 个
• 对于 N= 8 的值，我没有打印任何内容

我无法弄清楚我犯了什么错误。我的想法是意识到第一个皇后必须放在第一行，第二个皇后必须放在第二行，等等。我必须弄清楚哪一列是合适的，显然要考虑对角线来放置皇后。

任何帮助我指明正确方向的帮助都是值得赞赏的。我的代码如下，我尝试添加注释以帮助理解。

public class nQueens {

    static class Queen {
        public Queen( int row, int column) {
            this.row = row;
            this.column = column;
        }
        int row = -1;
        int column = -1;
    }

    static ArrayList<Queen> queens = new ArrayList<Queen>();

    public static void main(String argv[]) {
        int n = 5;
        int[][] chessBoard = new int[n][n];
        int placed = 0;
        solve(n, chessBoard, placed);
    }

    public static void solve(int n, int[][] chessBoard, int placed) {
        // this means that all the queens have been placed
        if (placed == n) {
            System.out.println("**** Solution *****");
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    System.out.print(chessBoard[i][j] + " ");
                }
                System.out.println();
            }
        } else {
            // we know that each queen can be placed on each row
            int i = placed;
            // iterate through the columns
            for (int j = 0; j < n; j++) {
                if (chessBoard[i][j] != 1) {
                    if (isSafe(i, j)) {
                        chessBoard[i][j] = 1;
                        Queen queen = new Queen( i, j);
                        queens.add(queen);
                        placed = placed + 1;
                        // solve for the remaining number of queens
                        solve(n, chessBoard, placed);
                        // un-mark the spot
                        chessBoard[i][j] = 0;
                        // remove the placed queen
                        queens.remove(queens.size() - 1);
                        placed = placed - 1;
                    }
                }
            }
        }
    }

    public static boolean isSafe(int row, int column) {
        // this means that there are no queens on the board
        if (queens.isEmpty()) {
            return true;
        } else {
            for (int i = 0; i < queens.size(); i++) {
                // same column
                if (queens.get(i).column == column) {
                    return false;
                }
                // check diagonal
                int slope = Math.abs((queens.get(i).row - row) / (queens.get(i).column - column));
                if (slope == 1) {
                    return false;
                }
            }
        }
        return true;
    }
}

Answer 1

问题是:

int slope = Math.abs((queens.get(i).row - row) / (queens.get(i).column - column));
if (slope == 1) {
    return false;
}

您正在将slope 转换为整数。这意味着 1.5 或 1.3 的斜率变为 1 并导致您返回 false，即使皇后不是实际上并不在那条对角线上。

而是在除法之前转换为浮点型(请注意，java 的除法是整数除法，因此您需要先将除数或被除数转换为浮点型以获得浮点输出)以允许浮点斜率:

float tmp = (queens.get(i).row - row);
float slope = Math.abs(tmp/ (queens.get(i).column - column));
if (slope == 1) {
    return false;
}