如何用Java正确实现填字游戏求解器？排查无限递归问题

问题背景 #

任务要求：补全一个5x5方阵中的11个缺失字母，使得每行、每列都包含"BRAVE"的所有字母（无重复）。

运行下方代码时出现无限递归，程序始终无法终止，调试两天仍未定位问题：

public class Crossword {

    static Character[] letters = new Character[]{'B', 'R', 'A', 'V', 'E'};

    static boolean isFilled(char[][] matrix) {
        Set<Character> lettersSet = new HashSet<>(Arrays.asList(letters));

        // 同时检查行和列
        for (int i = 0; i < matrix.length; i++) {
            Set<Character> rowLetters = new HashSet<>();
            Set<Character> colLetters = new HashSet<>();

            for (int j = 0; j < matrix.length; j++) {
                rowLetters.add(matrix[i][j]);
                colLetters.add(matrix[j][i]);
            }

            if (!rowLetters.containsAll(lettersSet) || !colLetters.containsAll(lettersSet)) {
                return false;
            }
        }

        return true;
    }

    static boolean containsLetter(char[] row, char symbol) {
        for (char c : row) {
            if (c == symbol) {
                return true;
            }
        }

        return false;
    }

    static void fillMatrixBruteForce(char[][] matrix) {

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length; j++) {

                if (matrix[i][j] == ' ') {

                    for (int k = 0; k < letters.length; k++) {
                        if (!containsLetter(matrix[i], letters[k])) {

                            matrix[i][j] = letters[k];
                            if (isFilled(matrix)) {
                                return;
                            } else {
                                fillMatrixBruteForce(matrix);
                            }

                        }
                    }
                    matrix[i][j] = ' ';
                }
            }
        }

    }

    static void print(char[][] matrix) {
        Arrays.stream(matrix).forEach(
                System.out::println
        );
    }

    public static void main(String[] args) {
        char[][] matrix = {
                {'B', 'R', 'A', 'V', 'E'},
                {' ', 'E', 'B', 'R', ' '},
                {' ', ' ', 'V', ' ', 'B'},
                {' ', 'B', 'R', ' ', ' '},
                {' ', ' ', 'E', 'B', ' '}
        };
        print(matrix);

        fillMatrixBruteForce(matrix);
        print(matrix);
    }
}

问题根源 #

1. 递归无终止判断：递归调用fillMatrixBruteForce后，没有检查当前矩阵是否已经符合要求。即使下层递归找到解，当前层还会继续尝试其他字母，触发回溯，导致反复填充和清空，进入无限循环。
2. 缺少列约束检查：填入字母前只检查了当前行是否已有该字母，但没检查列。这会导致填入违反列唯一性的字母，后续需要大量无效回溯，甚至永远找不到正确路径。
3. 验证时机过晚：isFilled只有在矩阵完全填充后才返回true，中途的无效填充无法提前终止递归，导致递归深度无限增加。

修复方案 #

修改fillMatrixBruteForce方法，增加列检查、递归终止判断，优化回溯逻辑：

public class Crossword {

    static Character[] letters = new Character[]{'B', 'R', 'A', 'V', 'E'};

    static boolean isFilled(char[][] matrix) {
        Set<Character> lettersSet = new HashSet<>(Arrays.asList(letters));

        for (int i = 0; i < matrix.length; i++) {
            Set<Character> rowLetters = new HashSet<>();
            Set<Character> colLetters = new HashSet<>();

            for (int j = 0; j < matrix.length; j++) {
                rowLetters.add(matrix[i][j]);
                colLetters.add(matrix[j][i]);
            }

            if (!rowLetters.containsAll(lettersSet) || !colLetters.containsAll(lettersSet)) {
                return false;
            }
        }

        return true;
    }

    // 检查行是否包含指定字母
    static boolean containsInRow(char[][] matrix, int row, char symbol) {
        for (char c : matrix[row]) {
            if (c == symbol) {
                return true;
            }
        }
        return false;
    }

    // 检查列是否包含指定字母
    static boolean containsInCol(char[][] matrix, int col, char symbol) {
        for (int i = 0; i < matrix.length; i++) {
            if (matrix[i][col] == symbol) {
                return true;
            }
        }
        return false;
    }

    // 修改为返回boolean，标记是否找到解
    static boolean fillMatrixBruteForce(char[][] matrix) {

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length; j++) {

                if (matrix[i][j] == ' ') {

                    for (char letter : letters) {
                        // 同时检查行和列无重复
                        if (!containsInRow(matrix, i, letter) && !containsInCol(matrix, j, letter)) {

                            matrix[i][j] = letter;
                            // 如果已填满符合要求，返回true表示找到解
                            if (isFilled(matrix)) {
                                return true;
                            }
                            // 递归调用，若下层找到解，直接返回true
                            if (fillMatrixBruteForce(matrix)) {
                                return true;
                            }
                            // 回溯
                            matrix[i][j] = ' ';
                        }
                    }
                    // 所有字母都尝试过，返回false表示当前路径无解
                    return false;
                }
            }
        }
        // 矩阵已填满，返回是否符合要求
        return isFilled(matrix);
    }

    static void print(char[][] matrix) {
        for (char[] row : matrix) {
            System.out.println(new String(row));
        }
    }

    public static void main(String[] args) {
        char[][] matrix = {
                {'B', 'R', 'A', 'V', 'E'},
                {' ', 'E', 'B', 'R', ' '},
                {' ', ' ', 'V', ' ', 'B'},
                {' ', 'B', 'R', ' ', ' '},
                {' ', ' ', 'E', 'B', ' '}
        };
        System.out.println("初始矩阵：");
        print(matrix);

        fillMatrixBruteForce(matrix);
        System.out.println("\n填充后矩阵：");
        print(matrix);
    }
}

修改说明 #

• 将fillMatrixBruteForce改为返回boolean，用于标记是否找到解，一旦找到直接逐层返回，终止递归。
• 新增containsInCol方法，填入字母前检查列的唯一性，减少无效递归。
• 递归调用后立即判断是否找到解，若找到则直接返回，不再尝试其他字母，避免不必要的回溯。
• 优化打印逻辑，确保输出的矩阵格式清晰。

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