题解 | #Sudoku#

import java.util.*;

public class Main {
    static int[][] arr;//记录当前盘面
    static boolean[][] booleans;//记录哪些数据要修改的

    public static void main(String[] args) {
        //初始化数据
        arr = new int[9][9];
        booleans = new boolean[9][9];
        //读取数据
        Scanner in = new Scanner(System.in);
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                int input = in.nextInt();
                arr[i][j] = input;
                if (input == 0) {
                    booleans[i][j] = true;
                }
            }
        }
        //深度搜索
        dfs(0, 0);
    }

    private static void dfs(int i, int j) {
        //边界条件
        if (i == 9 && j == 0) {
            //输出最后结果
            for (int p = 0; p < 9; p++) {
                for (int q = 0; q < 9; q++) {
                    System.out.print(arr[p][q] + " ");
                }
                System.out.println("");
            }
            System.exit(0);
        }
        //进一步搜索
        if (arr[i][j] == 0) {
            //查找可能的数据
            ArrayList<Integer> list = getList(i, j);
            if (list.size() == 0) {//如果找不到数字,回溯
                return;
            } else {
                for (int i1 = 0; i1 < list.size(); i1++) {
                    arr[i][j] = list.get(i1);
                    //进一步搜索
                    int nextRow;
                    int nextCol;
                    if (j + 1 == 9) {
                        nextRow = i + 1;
                        nextCol = 0;
                    } else {
                        nextRow = i;
                        nextCol = j + 1;
                    }
                    dfs(nextRow, nextCol);
                }
                //遍历完毕之后回溯
                arr[i][j] = 0;
            }
        } else {
            //进一步搜索
            int nextRow;
            int nextCol;
            if (j + 1 == 9) {
                nextRow = i + 1;
                nextCol = 0;
            } else {
                nextRow = i;
                nextCol = j + 1;
            }
            dfs(nextRow, nextCol);
        }
    }

    private static ArrayList<Integer> getList(int i, int j) {
        Integer[] integers = new Integer[] {1, 2, 3, 4, 5, 6, 7, 8, 9};
        List<Integer> list = Arrays.asList(integers);
        ArrayList<Integer> integers1 = new ArrayList<>(list);
        //行和列的数据
        for (int i1 = 0; i1 < 9; i1++) {
            integers1.remove((Integer) arr[i1][j]);
            integers1.remove((Integer) arr[i][i1]);
        }
        //九宫格内的数字
        int row = 0;
        int col = 0;
        if (i >= 0 && i <= 2) {
            row = 0;
        } else if (i >= 3 && i <= 5) {
            row = 3;
        } else if (i >= 6 && i <= 8) {
            row = 6;
        }
        if (j >= 0 && j <= 2) {
            col = 0;
        } else if (j >= 3 && j <= 5) {
            col = 3;
        } else if (j >= 6 && j <= 8) {
            col = 6;
        }
        for (int i1 = row; i1 < row + 3; i1++) {
            for (int i2 = col; i2 < col + 3; i2++) {
                integers1.remove((Integer) arr[i1][i2]);
            }
        }
        return integers1;
    }
}

解题思路:

1, 采用深度搜索算法, 对每个方格尝试填入数字;

2, 不断深入,如果发现有格子没有数字可填, 则说明上一步的猜测有误, 则进行回溯;

3, 直到所有格子都填进数字, 说明已经找到了结果, 就进行输出, 然后终止程序