八皇后问题 Java 递归实现 + 完整思路解析

问题描述在 8×8 的国际象棋棋盘上放置8 个皇后要求任意两个皇后不能同一行任意两个皇后不能同一列任意两个皇后不能在同一条斜线上主斜线、副斜线优化思路一行只放一个皇后所以我们按行递归每一行选择一列放皇后天然规避同行冲突。核心思路递归思想递归函数定义void backtrack(int row)代表处理第row行尝试在这一行的每一列放置皇后。终止条件row 8说明 8 行全部摆放完毕找到一组合法解。状态记录用数组queen[]保存摆放位置queen[row] col→ 第 row 行皇后放在第 col 列冲突校验规则遍历之前所有已放置的行i (i row) 设当前尝试位置(row, col)历史位置(i, queen[i])同列queen[i] col斜线行差绝对值 列差绝对值Math.abs(row - i) Math.abs(col - queen[i])满足任意一条则冲突不能放。递归回溯流程循环当前行所有列找到安全位置记录皇后位置递归处理下一行row1递归返回后回溯不需要手动清空数组下一次循环直接覆盖完整 Java 代码java运行public class EightQueens { // 皇后摆放位置queen[行号] 列号 private static int[] queen new int[8]; // 统计一共有多少种解法 private static int count 0; public static void main(String[] args) { // 从第0行开始递归摆放皇后 backtrack(0); System.out.println(八皇后总解法数量 count); } /** * 递归回溯核心方法 * param row 当前要摆放皇后的行号 */ public static void backtrack(int row) { // 递归终止条件8行全部摆放完成行0~7 if (row 8) { printResult(); count; return; } // 遍历当前行所有列(0~7)尝试摆放皇后 for (int col 0; col 8; col) { // 判断当前 (row,col) 是否安全 if (isSafe(row, col)) { queen[row] col; // 放置皇后 backtrack(row 1); // 递归处理下一行 // 回溯不需要手动清除下一次循环会直接覆盖queen[row] } } } /** * 判断第row行第col列是否可以放皇后 * param row 当前行 * param col 当前列 * return true 安全false冲突 */ public static boolean isSafe(int row, int col) { // 检查前面所有已经摆放皇后的行0 ~ row-1 for (int i 0; i row; i) { // 同列 或者 在同一斜线 → 冲突 if (queen[i] col || Math.abs(row - i) Math.abs(col - queen[i])) { return false; } } return true; } /** * 打印一种可行的棋盘方案 */ public static void printResult() { System.out.println(第 (count 1) 种方案); for (int i 0; i 8; i) { for (int j 0; j 8; j) { if (queen[i] j) { System.out.print(Q ); } else { System.out.print(· ); } } System.out.println(); } System.out.println(------------------------); } }运行结果说明程序最终输出92 种合法方案这是八皇后经典答案。递归与回溯重点总结为什么按行递归每行只放一个皇后省去判断同行大幅减少计算量。回溯体现在哪里当某一列摆放皇后之后递归深入当这条路径全部尝试完成回到 for 循环尝试下一列自动覆盖数组完成状态撤销。时间复杂度暴力最坏 \(O(8^8)\)通过合法性剪枝大量无效分支被提前截断效率大幅提升。