题解 | #Sudoku#

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) {
            int[][] sudo = new int[9][9];
            List<int[]> list = new ArrayList<>();
            List<Integer> values = new ArrayList<>();
            for (int i = 0 ; i < 9 ; ++i) {
                for (int j = 0 ; j < 9 ; ++j) {
                    sudo[i][j] = in.nextInt();
                    }
            }

            dfs(sudo);
            for(int i=0 ; i<9 ; ++i){
                for(int j=0 ; j<9 ; ++j){
                    System.out.print(sudo[i][j]+" ");
                }
                System.out.println();
            }

        }
    }

    public static boolean dfs(int[][] sudo) {
        for(int i=0 ; i<9 ; ++i){
            for(int j=0 ; j<9 ; ++j){
                if(sudo[i][j] != 0){
                    continue;
                }
                for(int k=1 ; k<=9 ; ++k){
                    if(isValid(sudo, k, i, j)){
                        sudo[i][j] = k;
                        if(dfs(sudo)){
                            return true;
                        }
                        sudo[i][j] = 0;
                    }
                }
                return false;
            }
        }
        return true;
        
    }

    public static boolean isValid(int[][] sudo, int val, int row, int col) {
        for(int i=0 ; i<9 ; ++i){
            if(sudo[row][i] == val){
                return false;
            }
        }

        for(int i=0 ; i<9 ; ++i){
            if(sudo[i][col] == val){
                return false;
            }
        }

        int startRow = (row/3)*3;
        int startCol = (col/3)*3;
        for(int i=startRow ; i<startRow+3 ; ++i){
            for(int j=startCol ; j<startCol+3 ; ++j){
                if(sudo[i][j] == val){
                    return false;
                }
            }
        }
        return true;
    }
}