题解 | #Sudoku#

空间换时间，时间复杂度不会算，它取决于没有填数字的空格数，但应该是最小的了。

分别用3个map记录第x行、第y列、第x行第y列所在小九宫格是否存在val值。

输入数据时，专门用一个队列来存储没有填数字的空格，后续使用回溯算法的主要对象就是这个队列，这样可以大大减少时间复杂度。

import java.util.Scanner;
import java.util.LinkedList;
import java.util.Map;
import java.util.HashMap;

public class Main {
    private static boolean[][] rowMap = new boolean[9][9];
    private static boolean[][] colMap = new boolean[9][9];
    private static boolean[][] squareMap = new boolean[9][9];
    private static Map<String, Integer> squareIdxMap = new HashMap<>();

    public static void main(String[] args) {
        initSquareIdxMap();
        Scanner in = new Scanner(System.in);
        int[][] nums = new int[9][9];
        LinkedList<Pos> zeroQueue = new LinkedList<>();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                nums[i][j] = in.nextInt();
                if (nums[i][j] == 0) {
                    zeroQueue.offer(new Pos(i, j));
                } else {
                    rowMap[i][nums[i][j] - 1] = true;
                    colMap[j][nums[i][j] - 1] = true;
                    squareMap[getSquareI(i, j)][nums[i][j] - 1] = true;
                }
            }
        }

        traceBack(nums, zeroQueue);
    }

    private static void initSquareIdxMap() {
        int idx = 0;
        squareIdxMap.put("1,1", idx++);
        squareIdxMap.put("1,4", idx++);
        squareIdxMap.put("1,7", idx++);
        squareIdxMap.put("4,1", idx++);
        squareIdxMap.put("4,4", idx++);
        squareIdxMap.put("4,7", idx++);
        squareIdxMap.put("7,1", idx++);
        squareIdxMap.put("7,4", idx++);
        squareIdxMap.put("7,7", idx++);
    }

    private static Integer getSquareI(int x, int y) {
        String key = (3 * (x / 3) + 1) + "," + (3 * (y / 3) + 1);
        return squareIdxMap.get(key);
    }

    private static void printNums(int[][] nums) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(nums[i][j] + " ");
            }
            System.out.println();
        }
    }

    private static boolean traceBack(int[][] nums, LinkedList<Pos> zeroQueue) {
        if (zeroQueue.isEmpty()) {
            printNums(nums);
            return true;
        }
        boolean result = false;
        Pos curPos = zeroQueue.poll();
        for (int k = 1; k <= 9; k++) {
            if (isRowInValid(curPos.x, k) || isColInValid(curPos.y, k) || isSquareInValid(curPos.x, curPos.y, k)) {
                continue;
            }
            nums[curPos.x][curPos.y] = k;
            rowMap[curPos.x][k - 1] = true;
            colMap[curPos.y][k - 1] = true;
            squareMap[getSquareI(curPos.x, curPos.y)][k - 1] = true;
            result = traceBack(nums, zeroQueue);
            squareMap[getSquareI(curPos.x, curPos.y)][k - 1] = false;
            colMap[curPos.y][k - 1] = false;
            rowMap[curPos.x][k - 1] = false;
            if (result) {
                return true;
            }
        }
        zeroQueue.addFirst(curPos);
        return result;
    }

    private static boolean isRowInValid(int x, int val) {
        return rowMap[x][val - 1];
    }

    private static boolean isColInValid(int y, int val) {
        return colMap[y][val - 1];
    }

    private static boolean isSquareInValid(int x, int y, int val) {
        return squareMap[getSquareI(x, y)][val - 1];
    }
}

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