题解 | #Sudoku#

和迷宫题一样用深度优先算法

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        // while (in.hasNextInt()) { // 注意 while 处理多个 case
        //     int a = in.nextInt();
        //     int b = in.nextInt();
        //     System.out.println(a + b);
        // }
        int[][] table = new int[9][9];
        List<Node> list = new ArrayList<>();
        int[] index = new int[2];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                table[i][j] = in.nextInt();
                if (table[i][j] == 0) {
                    list.add(new Node(i, j));
                }
            }
        }
        dfs(table, list, 0);
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(table[i][j] + " ");
            }
            System.out.println();
        }
    }
    private static boolean dfs(int[][] table, List<Node> nodes, int index) {
        if (index >= nodes.size()) {
            return true;
        }
        Node node = nodes.get(index);
        int x = node.x;
        int y = node.y;
        index++;
        for (int i = 1; i <= 9; i++) {
            if (!contains(table, x, y, i)) {
                table[x][y] = i;
                if (dfs(table, nodes, index)) {
                    return true;
                }
            }
        }
        index--;
        table[x][y] = 0;
        return false;
    }

    private static boolean contains(int[][] table, int x, int y, int val) {
        int xStart = (x / 3) * 3;
        int yStart = (y / 3) * 3;
        for (int i = xStart; i < xStart + 3; i++) {
            for (int j = yStart; j < yStart + 3; j++) {
                if (table[i][j] == val) {
                    return true;
                }
            }
        }
        for (int i = 0; i < 9; i++) {
            if (table[x][i] == val) {
                return true;
            }
            if (table[i][y] == val) {
                return true;
            }
        }
        return false;
    }
}
class Node {
    int x;
    int y;

    Node (int x, int y) {
        this.x = x;
        this.y = y;
    }
}