java用回溯法解决9*9数独问题

数独问题是一种经典的求解问题，回溯法是其中一种常用的算法。下面是用Java实现数独问题的回溯法：

public class SudokuSolver {
    private int[][] board;
    private static final int EMPTY = 0;
    private static final int SIZE = 9;

    public SudokuSolver(int[][] board) {
        this.board = new int[SIZE][SIZE];
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                this.board[i][j] = board[i][j];
            }
        }
    }

    public boolean solve() {
        int row = -1;
        int col = -1;
        boolean isEmpty = true;

        // 找到第一个空格
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                if (board[i][j] == EMPTY) {
                    row = i;
                    col = j;
                    isEmpty = false;
                    break;
                }
            }
            if (!isEmpty) {
                break;
            }
        }

        // 如果没有空格了，则数独已经解决
        if (isEmpty) {
            return true;
        }

        // 尝试填充数字
        for (int num = 1; num <= SIZE; num++) {
            if (isValid(row, col, num)) {
                board[row][col] = num;
                if (solve()) {
                    return true;
                }
                board[row][col] = EMPTY;
            }
        }

        return false;
    }

    // 检查当前数字是否有效
    private boolean isValid(int row, int col, int num) {
        for (int i = 0; i < SIZE; i++) {
            if (board[row][i] == num) {
                return false;
            }
            if (board[i][col] == num) {
                return false;
            }
            int rowOffset = 3 * (row / 3);
            int colOffset = 3 * (col / 3);
            if (board[rowOffset + (i / 3)][colOffset + (i % 3)] == num) {
                return false;
            }
        }
        return true;
    }

    public void print() {
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int[][] board = new int[][] {
                {8, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 3, 6, 0, 0, 0, 0, 0},
                {0, 7, 0, 0, 9, 0, 2, 0, 0},
                {0, 5, 0, 0, 0, 7, 0, 0, 0},
                {0, 0, 0, 0, 4, 5, 7, 0, 0},
                {0, 0, 0, 1, 0, 0, 0, 3, 0},
                {0, 0, 1, 0, 0, 0, 0, 6, 8},
                {0, 0, 8, 5, 0, 0, 0, 1, 0},
                {0, 9, 0, 0, 0, 0, 4, 0, 0}
        };

        SudokuSolver solver = new SudokuSolver(board);
        solver.solve();
        solver.print();
    }
}

在上面的代码中，我们定义了一个`SudokuSolver`类，其中包含了一个9x9的数独矩阵`board`。`solve()`方法通过回溯法来解决数独问题，`isValid()`方法用来检查当前数字是否有效，`print()`方法用来输出结果。

在`main()`方法中，我们定义了一个数独矩阵，并将其传递给`SudokuSolver`类来解决。最后输出结果。