题解 | #Sudoku# java优化思路

1.利用位运算快速确定可选数字。

因为int_32超过9bit，可以记录9个数字的存在性。

分别以line[i]、column[j]、grid[i / 3][j / 3]记录(i, j)位置所在的行、列、小格已有的数字。

2.在进行递归前先把直接能确定的位置填上。

对zeroList中的每一个空格判断是否有唯一可选数字，如果有就填上。

如果所有的空格都有多种可选数字，进入下一步递归回溯。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    static int[][] arrs = new int[9][9];

    static int[] line = new int[9];
    static int[] column = new int[9];
    static int[][] grid = new int[3][3];

    static int[] n2bits = new int[10];
    static int[] bits2n = new int[512];

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

    static void set(int i, int j, int n, int bit) {
        arrs[i][j] = n;
        line[i] |= bit;
        column[j] |= bit;
        grid[i / 3][j / 3] |= bit;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for (int i = 1; i <= 9; i++) {
            int bit = 1 << (i - 1);
            n2bits[i] = bit;
            bits2n[bit] = i;
        }

        for (int i = 0; i < 9; i++) {
            String str = br.readLine();
            String[] numStr = str.split(" ");
            for (int j = 0; j < 9; j++) {
                int n = Integer.parseInt(numStr[j]);
                if (n == 0) {
                    zeroList.add(new int[] {i, j});
                    continue;
                }
                int bit = n2bits[n];
                set(i, j, n, bit);
            }
        }

        boolean setFlag = true;
        while (setFlag) { //这一段先把确定的值填上，减少递归次数，也可以没有
            setFlag = false;
            for (int k = zeroList.size() - 1; k >= 0; k--) {
                int[] zero = zeroList.get(k);
                int i = zero[0];
                int j = zero[1];
                int bit = 511 & (~(line[i] | column[j] | grid[i / 3][j / 3]));
                int n = bits2n[bit];
                if (n == 0) {//不能直接确定
                    continue;
                }
                setFlag = true;
                zeroList.remove(k);
                set(i, j, n, bit);
            }
        }

        if (!zeroList.isEmpty()) {
            trySet(zeroList.size() - 1);
        }

        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < 9; i++) {
            ans.append(arrs[i][0]);
            for (int j = 1; j < 9; j++)
                ans.append(" ").append(arrs[i][j]);
            ans.append("\n");
        }
        System.out.print(ans.toString());
    }

    static boolean trySet(int k) {
        if (k == -1) {
            return true;
        }
        int[] zero = zeroList.get(k);
        int i = zero[0];
        int j = zero[1];
        int line_o = line[i];
        int column_o = column[j];
        int grid_o = grid[i / 3][j / 3];
        int bit = 511 & (~(line_o | column_o | grid_o));

        for (int n = 1; n <= 9; n++) {
            if ((bit & n2bits[n]) == 0) {
                continue;
            }
            line[i] |= n2bits[n];
            column[j] |= n2bits[n];
            grid[i / 3][j / 3] |= n2bits[n];
            if (trySet(k - 1)) {
                arrs[i][j] = n;
                return true;
            }
            line[i] = line_o;
            column[j] = column_o;
            grid[i / 3][j / 3] = grid_o;
        }
        return false;
    }
}