八皇后问题递归Java程序无输出，请求故障排查

原代码无法输出结果的核心问题在于解的存储逻辑完全错误，以下是具体问题分析和修复方案：

问题分析 #

1. 错误的存储位置计算：
   原代码使用Arrays.binarySearch(solutions, sb.toString())来确定解的存储位置，但初始的solutions数组全为null，binarySearch仅能在已排序的非空数组中查找元素，这种方式根本无法定位到正确的存储索引，导致所有解都没有被正确存入数组。

2. 缺少有效的解计数机制：
   没有跟踪已找到的解的数量，无法将每个新找到的解依次存入数组的对应位置。

修复后的代码 #

import java.util.Arrays;

public class EightQueens {
    public static void main(String[] args) {
        String[] solutions = new String[92]; // 已知8皇后问题有92个解
        int[] count = new int[1]; // 用数组传递计数器，避免全局变量
        solveQueens(0, new int[8], solutions, count);
        Arrays.sort(solutions);
        for (String solution : solutions) {
            System.out.println(solution);
            System.out.println();
        }
    }

    private static void solveQueens(int row, int[] columns, String[] solutions, int[] count) {
        if (row == 8) { // 找到一个完整解
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 8; i++) {
                for (int j = 0; j < 8; j++) {
                    sb.append(columns[i] == j ? "q " : ". ");
                }
                sb.append("\n");
            }
            // 将解存入数组，计数器自增
            solutions[count[0]] = sb.toString();
            count[0]++;
            return;
        }

        for (int col = 0; col < 8; col++) {
            columns[row] = col;
            if (isValid(row, columns)) {
                solveQueens(row + 1, columns, solutions, count);
            }
        }
    }

    private static boolean isValid(int row, int[] columns) {
        for (int i = 0; i < row; i++) {
            int diff = Math.abs(columns[i] - columns[row]);
            // 检查同列或同对角线
            if (diff == 0 || diff == row - i) {
                return false;
            }
        }
        return true;
    }
}

关键修复点 #

• 新增int[] count作为解的计数器：利用Java数组的引用传递特性，在递归过程中可以修改计数器的值，确保每个解都被依次存入数组的正确位置。
• 移除错误的Arrays.binarySearch逻辑：直接通过计数器索引存储解，这是解决无输出问题的核心。
• 保留了原有的有效逻辑：isValid方法的冲突检查是正确的，递归回溯的逻辑也没问题，仅需修复存储部分即可正常运行。

内容的提问来源于stack exchange，提问作者Sean Anderson