Java回溯法数独求解器问题：无法正确返回结果数组

问题根源分析 #

你的代码能正确打印解，但返回全0数组，核心问题出在递归逻辑的返回值处理和局部变量作用域：

1. 每次调用solver方法都会新建一个int[][] solution = new int[9][9]，这个数组是当前递归层级的局部变量，上层递归无法获取到下层找到的解。
2. 递归调用solver(row, col+1)时没有接收返回值，也没有在找到解后终止回溯——当递归到最后填满数独时，你给当前层级的solution赋值了，但后续回溯会把board的元素改回0，而最初调用solver返回的是它自己创建的空数组（全0）。

修复后的代码实现 #

我们需要修改递归逻辑：当找到有效解时，立即返回复制后的数独数组，并且在递归调用中如果得到非null的解，直接向上传递，不再执行回溯操作。

import java.util.Arrays;

public class SudokuSolver {
    private boolean[][] markRow;
    private boolean[][] markCol;
    private boolean[][][] markMatrix;
    private int[][] board;

    public SudokuSolver(int[][] board) {
        // 深拷贝输入的board，避免修改原数组
        this.board = new int[9][9];
        for (int i = 0; i < 9; i++) {
            System.arraycopy(board[i], 0, this.board[i], 0, 9);
        }
        
        markRow = new boolean[9][9];
        markCol = new boolean[9][9];
        markMatrix = new boolean[3][3][9];

        for (int row = 0; row < this.board.length; row++) {
            for (int col = 0; col < this.board[row].length; col++) {
                int currentNumber = this.board[row][col];
                if (currentNumber != 0) {
                    markRow[row][currentNumber - 1] = true;
                    markCol[col][currentNumber - 1] = true;
                    markMatrix[row / 3][col / 3][currentNumber - 1] = true;
                }
            }
        }
    }

    public int[][] solver(int row, int col) {
        if (row == 9) {
            // 数独填满，返回深拷贝的解
            int[][] solution = new int[9][9];
            for (int i = 0; i < 9; i++) {
                System.arraycopy(board[i], 0, solution[i], 0, 9);
            }
            return solution;
        }

        int nextRow = row;
        int nextCol = col + 1;
        if (nextCol == 9) {
            nextRow = row + 1;
            nextCol = 0;
        }

        if (board[row][col] != 0) {
            // 当前位置已有数字，直接递归下一个位置
            return solver(nextRow, nextCol);
        } else {
            for (int num = 1; num <= 9; num++) {
                int idx = num - 1;
                if (!markRow[row][idx] && !markCol[col][idx] && !markMatrix[row/3][col/3][idx]) {
                    // 标记当前数字已使用
                    markRow[row][idx] = true;
                    markCol[col][idx] = true;
                    markMatrix[row/3][col/3][idx] = true;
                    board[row][col] = num;

                    // 递归下一个位置，如果找到解直接返回
                    int[][] result = solver(nextRow, nextCol);
                    if (result != null) {
                        return result;
                    }

                    // 回溯，取消标记
                    markRow[row][idx] = false;
                    markCol[col][idx] = false;
                    markMatrix[row/3][col/3][idx] = false;
                    board[row][col] = 0;
                }
            }
            // 所有数字都尝试过，无解
            return null;
        }
    }

    public static void main(String[] args) {
        int[][] initial = new int[][]
                {
                        {0, 0, 0, 4, 0, 0, 0, 9, 0},
                        {6, 0, 7, 0, 0, 0, 8, 0, 4},
                        {0, 1, 0, 7, 0, 9, 0, 0, 3},
                        {9, 0, 1, 0, 7, 0, 0, 3, 0},
                        {0, 0, 2, 0, 0, 0, 9, 0, 0},
                        {0, 5, 0, 0, 4, 0, 1, 0, 7},
                        {3, 0, 0, 5, 0, 2, 0, 7, 0},
                        {4, 0, 6, 0, 0, 0, 3, 0, 1},
                        {0, 7, 0, 0, 0, 4, 0, 0, 0}
                };
        SudokuSolver solve = new SudokuSolver(initial);
        int[][] test = solve.solver(0, 0);
        System.out.println("=================");
        if (test != null) {
            for (int[] row : test) {
                System.out.println(Arrays.toString(row));
            }
        } else {
            System.out.println("无解");
        }
    }
}

关键修改点 #

1. 深拷贝输入数组：在构造方法中对传入的board进行深拷贝，避免修改原数组（原代码直接引用会导致初始数组被回溯修改）。
2. 递归返回逻辑优化：
   • 当row == 9时，说明数独已填满，返回当前board的深拷贝作为解。
   • 递归调用时接收返回值，如果得到非null的解，直接向上返回，不再执行回溯操作，确保解不会被后续回溯修改。
3. 简化坐标切换逻辑：提前计算下一个要处理的行和列，让代码更清晰。
4. 类名规范：将sudokuSolver改为SudokuSolver，符合Java命名规范。

测试验证 #

运行修改后的代码，test数组会正确接收数独的解，不再是全0数组，可以直接用于和玩家输入的数组对比。

内容的提问来源于stack exchange，提问作者Tran Phat Trien