java使用回溯法求解数独示例

在Java中使用回溯法求解数独问题是一个经典的算法问题。下面是一个简单的Java示例代码，展示了如何使用回溯法来解决数独。

public class SudokuSolver {
    private char[][] board;

    public void solveSudoku(char[][] board) {
        this.board = board;
        solve();
    }

    private boolean solve() {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    for (char num = '1'; num <= '9'; num++) {
                        if (isValid(i, j, num)) {
                            board[i][j] = num;
                            if (solve()) {
                                return true;
                            } else {
                                board[i][j] = '.'; // 回溯
                            }
                        }
                    }
                    return false; // 9个数都试完了，都不行
                }
            }
        }
        return true; // 数独已解决
    }

    private boolean isValid(int row, int col, char num) {
        // 检查行
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == num) {
                return false;
            }
        }
        // 检查列
        for (int i = 0; i < 9; i++) {
            if (board[i][col] == num) {
                return false;
            }
        }
        // 检查3x3方格
        int startRow = row - row % 3;
        int startCol = col - col % 3;
        for (int i = startRow; i < startRow + 3; i++) {
            for (int j = startCol; j < startCol + 3; j++) {
                if (board[i][j] == num) {
                    return false;
                }
            }
        }
        return true;
    }

    // 示例主函数
    public static void main(String[] args) {
        char[][] board = {
            {'5','3','.','.','7','.','.','.','.'},
            {'6','.','.','1','9','5','.','.','.'},
            {'.','9','8','.','.','.','.','6','.'},
            {'8','.','.','.','6','.','.','.','3'},
            {'4','.','.','8','.','3','.','.','1'},
            {'7','.','.','.','2','.','.','.','6'},
            {'.','6','.','.','.','.','2','8','.'},
            {'.','.','.','4','1','9','.','.','5'},
            {'.','.','.','.','8','.','.','7','9'}
        };

        SudokuSolver solver = new SudokuSolver();
        solver.solveSudoku(board);

        // 打印解决后的数独
        for (char[] row : board) {
            for (char cell : row) {
                System.out.print(cell + " ");
            }
            System.out.println();
        }
    }
}

在这个示例中，`SudokuSolver` 类包含了一个 `solveSudoku` 方法，该方法接受一个二维字符数组作为数独的输入，并对其进行求解。内部使用了 `solve` 方法来递归地尝试填充数独的空白位置，并通过 `isValid` 方法来检查每个尝试是否合法。如果找到了一个有效的解决方案，则数独被解决，否则回溯到上一个决策点并尝试其他可能性。