题解 | #Sudoku#

使用回溯法，使用一个静态变量保存结果
是用一个变量保存确定的数据的个数，当确定的数据个数等于81时就表示数独解好了
搜索的时候从数独数组的第(0,0)位置开始向下搜索，注意当遍历到边界时需要进行判断
当前元素时非0元素时，就表示他本身就是确定的，就直接向下遍历，当当前元素时0，那么就需要从1-9逐个的遍历确定可行值，并向下搜索

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int[][] arr = new int[9][9];
            for(int i = 0; i < 9; i++){
                for(int j = 0; j < 9; j++){
                    arr[i][j] = sc.nextInt();
                }
            }
            sudoku(arr);
            for(int i = 0; i < 9; i++){
                for(int j = 0; j < 9; j++){
                    System.out.printf("%d ",result[i][j]);
                }
                System.out.println();
            }
        }
    }
    static int finished = 0; //已经确定的格子数目
    static int[][] result = new int[9][9];
    public static void sudoku(int[][] arr){
        // 通过回溯法
        backtrace(arr, 0, 0);

    }
    // arr 的(x,y)位置
    public static void backtrace(int[][] arr, int x, int y){
        if(finished == 81){
            for(int i = 0; i < 9; i++){
                for(int j = 0; j < 9; j++){
                   result[i][j] = arr[i][j];
                }
            }
            return;
        }
        if(arr[x][y] == 0){
            // 当x,y位置数为0时，就遍历1-9,在判断前首先需要判断是否满足条件
            for(int i = 1; i <= 9; i++){
                //先判断i是否满足条件,即(x,y)所在的行列和3*3是否存在i
                if(isValid(arr, x, y, i)){//如果满足条件则向下继续搜索
                    arr[x][y] = i;
                    finished++;
                    if(y < 8){
                        backtrace(arr, x, y + 1);
                    }else{
                        backtrace(arr, x + 1, 0);
                    }
                    finished--;
                    arr[x][y] = 0;
                }
            }
        }else{
            finished++;
            if(y < 8){
                backtrace(arr, x, y + 1);
            }else{
                backtrace(arr, x + 1, 0);
            }
            finished--;
        }
    }

    public static boolean isValid(int[][] arr, int x, int y, int k){
        // 检查行
        for(int i = 0; i < 9; i++){
            if(arr[x][i] == k){
                return false;
            }
        }
        // 检查列
        for(int i = 0; i < 9; i++){
            if(arr[i][y] == k){
                return false;
            }
        }
        // 检查3*3单元格
        for(int i = x / 3 * 3; i < x / 3 * 3 + 3; i++){
            for(int j = y / 3 * 3; j <  y / 3 * 3 + 3; j++){
                if(arr[i][j] == k){
                    return false;
                }
            }
        }
        return true;

    }
}