题解 | #Sudoku#回溯算法

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextInt()){
            int[][] nums = new int[9][9];
            int toFillCount = 0;
            for (int i=0;i<9;i++){
                for(int j=0;j<9;j++){
                    nums[i][j] = in.nextInt();
                    if(nums[i][j] == 0){
                        toFillCount++;
                    }
                }
            }
            //包含已知数字的9X9盘面数组[空缺位以数字0表示]
            fill(nums,0,0,toFillCount);

            //很坑 这个题目输出多种解法算答错了 只能输出一个答案
            int[][] ares = res.get(0);
            for(int i=0;i<9;i++){
                for (int j=0;j<9;j++){
                    System.out.print(ares[i][j]);
                    System.out.print(" ");
                }
                System.out.println();
            }
        }
    }


    /**
     *
     * @param nums
     * @param row 当前要填的行号
     * @param line 当前要填的列号
     */
    private static void fill(int[][] nums,int row,int line,int toFillCount){
        //结束条件：没有需要填的空格
        if(toFillCount == 0){
            int[][] ares = new int[9][9];
            for(int i=0;i<9;i++){
                ares[i] = Arrays.copyOf(nums[i],9);
            }
            res.add(ares);
            return;
        }

        //找到要填的格
        boolean found = false;
        while(line < 9){
            while (row < 9){
                if(nums[line][row] == 0){
                    found = true;
                    break;
                }
                row++;
            }
            if(found){
                break;
            }
            line++;
            row = 0;
        }

        //遍历选择
        for(int i : getAvailableNum(nums,row,line)){
            //做出选择
            nums[line][row] = i;
            toFillCount--;

            fill(nums,row,line,toFillCount);

            //撤销选择
            nums[line][row] = 0;
            toFillCount++;
        }
    }

    static List<int[][]> res = new ArrayList<>();

    /**
     * 找出这个位置可以填的数字
     * @param nums
     * @param row
     * @param line
     * @return
     */
    private static List<Integer> getAvailableNum(int[][] nums , int row, int line){
        int[] used = new int[10];//used[0]空着不用

        for(int i=0;i<9;i++){
            //同一行已经出现过的数字
            int numInRow = nums[i][row];
            used[numInRow] = numInRow;

            //同一列出现过的
            int numInLine = nums[line][i];
            used[numInLine] = numInLine;

            //3*3小格里出现过的
            int xBegin = line - line%3;
            int rowBegin = row - row%3;
            for(int j=0;j<3;j++){
                for(int k=0;k<3;k++){
                    int numInBoard = nums[xBegin+j][rowBegin+k];
                    used[numInBoard] = numInBoard;
                }
            }
        }

        List<Integer> res = new LinkedList<>();
        for(int i=1;i<10;i++){
            if(used[i] == 0){
                res.add(i);
            }
        }
        return res;
    }
}