题解 | #回溯解决数独#

import java.util.* ;
public class Main{
    public static void main(String...args) {
        Scanner sc = new Scanner(System.in) ;
        int[][] arr = new int[9][9] ;
        while(sc.hasNextLine()) {
            for(int i = 0 ; i < 9 ; i ++) {
                for(int j = 0 ; j < 9 ; j ++) {
                    arr[i][j] = sc.nextInt() ;
                }
                sc.nextLine() ;
            }
        }
        dfs(arr,0,0) ;
        for(int i = 0 ; i < 9 ; i ++) {
            for(int j = 0 ; j < 9 ; j ++) {
                System.out.print(arr[i][j] + " ") ; 
            }
            System.out.println() ;
        }
    }
    //确定当前（i,j）的值，并以其为起点去试探其他的点，是否可行
    public static boolean dfs(int[][] arr , int i , int j) {
        //说明试探玩了，都可行
        if(i == 9) {
            return true ;
        }
        if(arr[i][j] == 0) {
            for(int k = 1 ; k <= 9 ; k ++) {
                arr[i][j] = k ;
                if(check(arr,i,j) && dfs(arr , j == 8 ? i + 1 : i , j == 8 ? 0 : j+1)){
                    return true ;
                } 
            }
            arr[i][j] = 0 ;
            return false ;
        } else {
            return dfs(arr , j == 8 ? i + 1 : i , j == 8 ? 0 : j+1) ;
        }
    }
    public static boolean check(int arr[][] , int i , int j) {
        //检查同行
        for(int q = 0 ; q < 9 ; q ++) {
            if(q != j && arr[i][q] == arr[i][j]) {
                return false ;
            }
        }
        //检查同列
        for(int q = 0 ; q < 9 ; q ++) {
            if(q != i && arr[q][j] == arr[i][j]) {
                return false ;
            }
        }
        //检查同九宫格
        int up = (i/3)*3 ;
        int le = (j/3)*3 ;
        for(int a = up ; a < up+3 ; a ++) {
            for(int b = le ; b < le+3 ; b ++) {
                if((a != i || b != j )&& arr[a][b] == arr[i][j]) {
                    return false ;
                }
            }
        }
        return true ;
    }
}