题解 | #Sudoku#数独填充

import java.util.*;

class SudokuSolver {

    private static final int SIZE = 9; // 数独的大小
    private final int[][] board; // 存储数独状态的二维数组

    public SudokuSolver(int[][] initialBoard) {
        this.board = Arrays.copyOf(initialBoard, SIZE);
    }

    public boolean solveSudoku() {
        for (int row = 0; row < SIZE; row++) {
            for (int col = 0; col < SIZE; col++) {
                if (board[row][col] == 0) { // 找到空格
                    if (!solveCell(row, col)) {
                        return false; // 如果当前单元格无法填充，则返回false
                    }
                }
            }
        }
        return true; // 如果所有单元格都成功填充，则返回true
    }

    private boolean solveCell(int row, int col) {
        if (col == SIZE) { // 列已满，则换行
            col = 0;
            row++;
        }

        if (row == SIZE) { // 数独完成
            return true;
        }

        if (board[row][col] != 0) { // 当前单元格已有数字，检查下一个
            return solveCell(row, col + 1);
        }

        for (int num = 1; num <= SIZE; num++) {
            if (isValid(row, col, num)) {
                board[row][col] = num;

                // 继续尝试填充下一个空白单元格
                if (solveCell(row, col + 1)) {
                    return true;
                } else {
                    // 如果后续单元格填充失败，则撤销当前操作
                    board[row][col] = 0;
                }
            }
        }

        return false; // 当前单元格的所有可能数字都已尝试且无效，返回false
    }

    private boolean isValid(int row, int col, int num) {
        // 检查行、列和3x3宫格内是否存在重复数字
        for (int i = 0; i < SIZE; i++) {
            if (board[row][i] == num
                    || board[i][col] == num
                    || board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == num//九宫格值判定
                ) {
                return false;
            }
        }
        return true;
    }


    public void printBoard() {
        for (int[] row : board) {
            for(int i : row){
                System.out.print(i + " ");
            }
            System.out.println();
        }
    }

}

public class Main {
    private static final int N = 9;
    // 测试用例
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 输入的数组arr[n][m]的值0表示空格
        int[][] arr = new int[N][N];
        int index = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int gridValue = in.nextInt();
                arr[i][j] = gridValue;

            }
        }
        SudokuSolver solver = new SudokuSolver(arr);
        if (solver.solveSudoku()) {
            solver.printBoard();
        } else {
            System.out.println("No solution exists.");
        }

    }
}