Java使用递归回溯完美解决八皇后问题

什么是八皇后问题

八皇后是一个以棋盘为底盘，放置八个皇后的问题，皇后拥有垂直、水平和对角线的移动能力，要求任意两个皇后都不能在同一行、同一列或同一对角线上。

解题思路

因为任意两个皇后不能在同一行、同一列或同一对角线上，因此我们可以通过递归回溯的思路，按行对皇后进行放置，逐步约束各个皇后的位置，以达到放置成功且不冲突的状态。

具体步骤如下：

初始化棋盘，用 0 表示空格，1 表示皇后。
从棋盘第一行开始，按照列的顺序依次尝试放置皇后。
当尝试放置皇后时，判断该位置是否与之前已经放置的皇后位置产生冲突。如果产生冲突，继续尝试下一列；如果不产生冲突，将皇后放在该位置，并标记此位置为 1。
继续按行进行递归，直到放置第 8 个皇后或者无法继续放置。如果无法继续放置，则回溯到上一个皇后位置进行重新尝试，直到找到不冲突的位置或者所有位置都尝试过了。

代码实现

我们可以使用一个一维数组 int[] queen 来表示各个皇后的位置。queen[i] 表示第 i 行的皇后所在的列数。在每个节点进行选择时，我们需要将当前皇后所有可能的放置位置进行遍历，并进行回溯。

示例代码：

class EightQueens {
    private int[] queen = new int[8];    // 记录每个皇后的位置，初始化都为 0
    private int count = 0;    // 记录解法的数量
    private void placeQueen(int row) {
        // 递归终止条件：如果 row == 8，说明 8 个皇后已经全部放置成功，此时将当前棋盘打印出来
        if (row == 8) {
            printQueen();
            count++;
            return;
        }
        // 尝试放置第 row 行皇后
        for (int col = 0; col < 8; col++) {
            if (check(row, col)) {  // 判断该位置是否冲突
                queen[row] = col;   // 如果不冲突，则将皇后放在该位置
                placeQueen(row + 1);    // 继续放置下一行的皇后
            }
        }
    }
    // 判断放置在 (row, col) 位置的皇后是否与之前的皇后冲突
    private boolean check(int row, int col) {
        for (int i = 0; i < row; i++) {
            // 如果同一列已经有皇后，或者斜方向上的两个点距离相等，则说明冲突
            if (queen[i] == col || Math.abs(row - i) == Math.abs(col - queen[i])) {
                return false;
            }
        }
        return true;
    }
    // 打印棋盘
    private void printQueen() {
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                if (queen[i] == j) {
                    System.out.print("1 ");
                } else {
                    System.out.print("0 ");
                }
            }
            System.out.println();
        }
        System.out.println();
    }
    public void solve() {
        placeQueen(0);
        System.out.println("共有 " + count + " 种解法");
    }
}

我们创建一个 EightQueens 的实例，并调用 solve() 方法，即可解决八皇后问题并输出所有解法的情况。下面是一个示例：

EightQueens eightQueens = new EightQueens();
eightQueens.solve();

输出：

0 0 0 0 1 0 0 0 
0 0 0 0 0 0 0 1 
0 0 0 1 0 0 0 0 
0 0 0 0 0 0 1 0 
1 0 0 0 0 0 0 0 
0 0 1 0 0 0 0 0 
0 0 0 0 0 1 0 0 
0 1 0 0 0 0 0 0 

0 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 1 
0 0 0 0 1 0 0 0 
0 0 1 0 0 0 0 0 
1 0 0 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 0 0 1 0 0 0 0 
0 1 0 0 0 0 0 0 

共有 92 种解法

可以发现，八皇后问题共有 92 种解法。

示例说明

示例一

我们假设在八皇后问题中，求取其中一种解法。此时，我们可以使用回溯算法，从第一行开始，逐个尝试每个皇后的位置。如果该位置不与之前的皇后产生冲突，则将该皇后放置在该位置，继续放置下一行的皇后。如果当前皇后无论在哪个位置都无法放置成功，则回溯到上一个皇后位置重新放置。

代码实现如下：

class EightQueens {
    private int[] queen = new int[8];    // 记录每个皇后的位置，初始化都为 0
    public void solve() {
        placeQueen(0);
    }
    private void placeQueen(int row) {
        // 如果 8 个皇后都放置成功，打印棋盘并返回
        if (row == 8) {
            printQueen();
            return;
        }
        // 尝试把皇后放在当前行的每一列上，并递归尝试下一行的放置
        for (int col = 0; col < 8; col++) {
            if (check(row, col)) {  // 判断当前位置是否可以放置
                queen[row] = col;   // 如果可以，将皇后放置在该位置
                placeQueen(row + 1);    // 放置下一行的皇后
            }
        }
    }
    // 判断放置在 (row, col) 位置的皇后是否与之前的皇后冲突
    private boolean check(int row, int col) {
        for (int i = 0; i < row; i++) {
            // 如果同一列已经有皇后，或者斜方向上的两个点距离相等，则说明冲突
            if (queen[i] == col || Math.abs(row - i) == Math.abs(col - queen[i])) {
                return false;
            }
        }
        return true;
    }
    // 打印棋盘
    private void printQueen() {
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                if (queen[i] == j) {
                    System.out.print("1 ");
                } else {
                    System.out.print("0 ");
                }
            }
            System.out.println();
        }
        System.out.println();
    }
}

EightQueens eightQueens = new EightQueens();
eightQueens.solve();

输出：

0 0 0 0 1 0 0 0 
0 0 0 0 0 0 0 1 
0 0 0 1 0 0 0 0 
0 0 0 0 0 0 1 0 
1 0 0 0 0 0 0 0 
0 0 1 0 0 0 0 0 
0 0 0 0 0 1 0 0 
0 1 0 0 0 0 0 0

这一种解法中，所有皇后的位置分别为 (0, 4), (1, 7), (2, 3), (3, 6), (4, 0), (5, 2), (6, 5), (7, 1)。

示例二

我们假设在八皇后问题中，求取所有解法，代码实现如下：

class EightQueens {
    private int[] queen = new int[8];    // 记录每个皇后的位置，初始化都为 0
    private int count = 0;    // 记录解法的数量
    private void placeQueen(int row) {
        // 递归终止条件：如果 row == 8，说明 8 个皇后已经全部放置成功，此时将当前棋盘打印出来
        if (row == 8) {
            printQueen();
            count++;
            return;
        }
        // 尝试放置第 row 行皇后
        for (int col = 0; col < 8; col++) {
            if (check(row, col)) {  // 判断该位置是否冲突
                queen[row] = col;   // 如果不冲突，则将皇后放在该位置
                placeQueen(row + 1);    // 继续放置下一行的皇后
            }
        }
    }
    // 判断放置在 (row, col) 位置的皇后是否与之前的皇后冲突
    private boolean check(int row, int col) {
        for (int i = 0; i < row; i++) {
            // 如果同一列已经有皇后，或者斜方向上的两个点距离相等，则说明冲突
            if (queen[i] == col || Math.abs(row - i) == Math.abs(col - queen[i])) {
                return false;
            }
        }
        return true;
    }
    // 打印棋盘
    private void printQueen() {
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                if (queen[i] == j) {
                    System.out.print("1 ");
                } else {
                    System.out.print("0 ");
                }
            }
            System.out.println();
        }
        System.out.println();
    }
    public void solve() {
        placeQueen(0);
        System.out.println("共有 " + count + " 种解法");
    }
}

EightQueens eightQueens = new EightQueens();
eightQueens.solve();

输出：

0 0 0 0 1 0 0 0 
0 0 0 0 0 0 0 1 
0 0 0 1 0 0 0 0 
0 0 0 0 0 0 1 0 
1 0 0 0 0 0 0 0 
0 0 1 0 0 0 0 0 
0 0 0 0 0 1 0 0 
0 1 0 0 0 0 0 0 

0 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 1 
0 0 0 0 1 0 0 0 
0 0 1 0 0 0 0 0 
1 0 0 0 0 0 0 0 
0 0 0 0 0 0 1 0 
0 0 0 1 0 0 0 0 
0 1 0 0 0 0 0 0 

...
共有 92 种解法

可以发现，八皇后问题共有 92 种解法。

本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：Java使用递归回溯完美解决八皇后的问题 - Python技术站

Java使用递归回溯完美解决八皇后的问题

Java使用递归回溯完美解决八皇后问题

什么是八皇后问题

解题思路

代码实现

示例说明

示例一

示例二

相关文章