使用DFS求解数独（Sudoku）问题

1.题目描述

问题描述：数独（Sudoku）是一款大众喜爱的数字逻辑游戏。玩家需要根据9X9盘面上的已知数字，推算出所有剩余空格的数字，并且满足每一行、每一列、每一个粗线宫内的数字均含1-9，并且不重复。
输入：
包含已知数字的9X9盘面数组[空缺位以数字0表示]
输出：
完整的9X9盘面数组
示例：
输入：

0 9 2 4 8 1 7 6 3
4 1 3 7 6 2 9 8 5
8 6 7 3 5 9 4 1 2
6 2 4 1 9 5 3 7 8
7 5 9 8 4 3 1 2 6
1 3 8 6 2 7 5 9 4
2 7 1 5 3 8 6 4 9
3 8 6 9 1 4 2 5 7
0 4 5 2 7 6 8 3 1

输出：

5 9 2 4 8 1 7 6 3
4 1 3 7 6 2 9 8 5
8 6 7 3 5 9 4 1 2
6 2 4 1 9 5 3 7 8
7 5 9 8 4 3 1 2 6
1 3 8 6 2 7 5 9 4
2 7 1 5 3 8 6 4 9
3 8 6 9 1 4 2 5 7
9 4 5 2 7 6 8 3 1

2.思路精要

该题可以用DFS来求解，步骤如下：

• （1）对于每个值为0的格子，从1到9尝试，填入一个暂时满足条件的值。
• （2）填写下一个格子（从左到右，从上到下），如果下一个格子能填写数字就继续进行。否则回溯。

3.具体代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            // 初始化数独
            int[][] sd = new int[9][9];
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    sd[i][j] = scanner.nextInt();
                }
            }

            // 填充数独
            dfs(sd, 0, 0);

            // 打印数独
            for (int[] row : sd) {
                for (int i = 0; i < 9; i++) {
                    System.out.print(row[i]);
                    if (i != 8) {
                        System.out.print(" ");
                    }
                }
                System.out.println();
            }
        }
    }

    private static boolean dfs(int[][] sd, int i, int j) {
        // (9,0)坐标
        if (i == 9) {
            return true;
        }
        if (sd[i][j] == 0) {
            for (int k = 1; k <= 9; k++) {
                sd[i][j] = k;
                if (check(sd, i, j) && dfs(sd, j == 8 ? i + 1 : i, j == 8 ? 0 : j + 1)) {
                    return true;
                }
            }
            sd[i][j] = 0;// 回溯
            return false;
        } else {
            return dfs(sd, j == 8 ? i + 1 : i, j == 8 ? 0 : j + 1);
        }
    }

    private static boolean check(int[][] sd, int i, int j) {
        // 同行
        for (int k = 0; k < 9; k++) {
            if (k != j && sd[i][k] == sd[i][j]) {
                return false;
            }
        }

        // 同列
        for (int k = 0; k < 9; k++) {
            if (k != i && sd[k][j] == sd[i][j]) {
                return false;
            }
        }

        // 同九宫
        int up = i / 3 * 3;
        int left = j / 3 * 3;
        for (int k = up; k < up + 3; k++) {
            for (int l = left; l < left + 3; l++) {
                if ((k != i || l != j) && sd[k][l] == sd[i][j]) {
                    return false;
                }
            }
        }

        return true;
    }
}