SudokuSolverOPT [source code]

public class SudokuSolverOPT {
static
/******************************************************************************/
class Solution {
    static final int ALL_ZEROS = 0;
    static final int ALL_ONES = 0x3fe;
    int[] row_bitmap, col_bitmap, cube_bitmap, entry, sequence;
    // Always points to the first empty cell's SQUARE index, which is stored in SEQUENCE
    int seq_start;
    // Utility arrays to store mapping from SQUARE to ROW/COLs/CUBES: e.g. 37 -> cube[1, 0], whose 1D index is 3;
    int[] square_to_row, square_to_col, square_to_cube;

    public void solveSudoku(char[][] board) {
        seq_start = 0;
        row_bitmap = new int[9];
        col_bitmap = new int[9];
        cube_bitmap = new int[9];
        entry =  new int[81];
        sequence =  new int[81];
        square_to_row =  new int[81];
        square_to_col =  new int[81];
        square_to_cube = new int[81];
        // Initialize all helping data structures
        // All digits are initially all available (marked by 1) in all rows/columns/cubes
        for (int i = 0; i < 9; i++)
            row_bitmap[i] = col_bitmap[i] = cube_bitmap[i] = ALL_ONES;
        // Sequence stores all SQUARE indices of all cells, with 0..start-1 being all filled cells, and the rest all empty
        // All cells initially all empty
        for (int i = 0; i < 81; i++)
            sequence[i] = i;
        for (int i = 0; i < 9; i++) for (int j = 0; j < 9; j++) {
            // Mapping from SQUARE to I/J is also beneficial: avoid calculating I/J from SQUARE later
            int square = i * 9 + j;
            square_to_row[square] = i;
            square_to_col[square] = j;
            square_to_cube[square] = (i / 3) * 3 + j / 3;
        }
        // Fill in the given cells. Update the bitmaps at the same time
        for (int i = 0; i < 9; i++) for (int j = 0; j < 9; j++) if (board[i][j] != '.') {
            int square = i * 9 + j, val = board[i][j] - '0', valbit = 1 << val;
            row_bitmap[i] &= ~valbit;
            col_bitmap[j] &= ~valbit;
            cube_bitmap[(i / 3) * 3 + j / 3] &= ~valbit;
            entry[square] = valbit;
            int seq_iter = seq_start;
            // Compact non-empty cells to the front, and use SEQ_START to mark the first empty cell's position
            while (seq_iter < 81 && sequence[seq_iter] != square)
                seq_iter++;
            swapSeq (seq_start++, seq_iter);
        }
        // main solver process
        boolean success = place (seq_start);
        assert success : "Unsolvable Puzzle!";
        // dump result back from ENTRY array to BOARD
        for (int s = 0; s < 81; s++) {
            int i = square_to_row[s], j = square_to_col[s];
            board[i][j] = (char) (Integer.numberOfTrailingZeros (entry[s]) + '0');
        }
    }

    boolean place (int seq_pos) {
        if (seq_pos >= 81)
            return true;
        int seq_next = nextPos (seq_pos);
        swapSeq (seq_pos, seq_next);
        int square = sequence[seq_pos], row_idx = square_to_row[square], col_idx = square_to_col[square], cube_idx = square_to_cube[square];
        int cell_bitmap = row_bitmap[row_idx] & col_bitmap[col_idx] & cube_bitmap[cube_idx];
        while (cell_bitmap > 0) {
            // Get each available bit/digit in order
            int next_digit_bit = cell_bitmap & -cell_bitmap;
            cell_bitmap &= ~next_digit_bit;
            entry[square] = next_digit_bit;
            // claim this DIGIT is used in row/column/cube
            row_bitmap[row_idx] &= ~next_digit_bit;
            col_bitmap[col_idx] &= ~next_digit_bit;
            cube_bitmap[cube_idx] &= ~next_digit_bit;

            if (place (seq_pos + 1))
                return true;

            // undo claims in the bitmaps
            row_bitmap[row_idx] |= next_digit_bit;
            col_bitmap[col_idx] |= next_digit_bit;
            cube_bitmap[cube_idx] |= next_digit_bit;
            entry[square] = ALL_ZEROS;
        }
        swapSeq (seq_pos, seq_next);
        return false;
    }

    // Find among empty cells the one with the smallest search space: least bits on its bitmap;
    int nextPos (int pos) {
        int min_idx = pos, min_digit_count = 100;
        for (int i = pos; i < 81; i++) {
            int square = sequence[i];
            // Number of bits in CELL_BITMAP is the number of digits that this cell can take
            int cell_bitmap = row_bitmap[square_to_row[square]] & col_bitmap[square_to_col[square]] & cube_bitmap[square_to_cube[square]];
            // Counts the bits, so you know how many digits this CELL can take: we want the minimum one
            int num_possible_digits = Integer.bitCount (cell_bitmap);
            if (num_possible_digits < min_digit_count) {
                min_idx = i;
                min_digit_count = num_possible_digits;
            }
        }
        return min_idx;
    }

    void swapSeq (int i, int j) {
        int tmp = sequence[i];
        sequence[i] = sequence[j];
        sequence[j] = tmp;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        SudokuSolverOPT.Solution tester = new SudokuSolverOPT.Solution();
        char[][][] inputs = {
            //1
            {{'.','.','9','7','4','8','.','.','.'},
            {'7','.','.','.','.','.','.','.','.'},
            {'.','2','.','1','.','9','.','.','.'},
            {'.','.','7','.','.','.','2','4','.'},
            {'.','6','4','.','1','.','5','9','.'},
            {'.','9','8','.','.','.','3','.','.'},
            {'.','.','.','8','.','3','.','2','.'},
            {'.','.','.','.','.','.','.','.','6'},
            {'.','.','.','2','7','5','9','.','.'}}, 
            {{'5','1','9','7','4','8','6','3','2'},
            {'7','8','3','6','5','2','4','1','9'},
            {'4','2','6','1','3','9','8','7','5'},
            {'3','5','7','9','8','6','2','4','1'},
            {'2','6','4','3','1','7','5','9','8'},
            {'1','9','8','5','2','4','3','6','7'},
            {'9','7','5','8','6','3','1','2','4'},
            {'8','3','2','4','9','1','7','5','6'},
            {'6','4','1','2','7','5','9','8','3'}}
        };
        for (int i = 0; i < inputs.length / 2; i++) {
            char[][] board = inputs[2 * i], ans = inputs[2 * i + 1];
            String input_str = Matrix.printMatrix (board), ans_str = Matrix.printMatrix (ans);
            System.out.println (Printer.separator ());
            tester.solveSudoku (board);
            String output_str = Matrix.printMatrix (board);
            System.out.printf ("%s -> \n%s, expected: \n%s\n", 
                input_str, Printer.wrapColor (output_str, output_str.equals (ans_str) ? "green" : "red"), ans_str
            );
        }

    }

    static String printMatrix (int[] entry) {
        StringBuilder sb = new StringBuilder ();
        for (int i = 0; i < 81; i++) {
            if (i > 0 && i % 9 == 0)
                sb.append ("\n");
            sb.append ((entry[i] > 0 ? Integer.numberOfTrailingZeros (entry[i]) : ".") + "\t");
        }
        return sb.toString ();
    }

    static String printBitmap (int[] bitmap, int... indices) {
        StringBuilder sb = new StringBuilder ();
        for (int i = 0; i < bitmap.length; i++) {
            if (indices.length > 0 && !Arrays.deepToString (new int[][] {indices}).contains (Integer.toString (i)))
                continue;
            sb.append (String.format ("%d = %10s", i, Integer.toBinaryString (bitmap[i])));
            if (i < bitmap.length - 1)
                sb.append ("\n");
        }
        return sb.toString ();
    }
}

他这里本来实现的时候, 是有一个priority的想法的, 但是好像最后没有用PriorityQueue来实现, 是为什么? 我自己试验了一下, 好像这题没有办法用单纯的PriorityQueue来实现: 因为weight是一个entry的space的大小, 当你因为其他的操作, propagate改变了我的entry的weight的时候, 其实PriorityQueue是不会自动立刻重新调整排序的, 这个我是专门实验过了. 这个也是为什么之前看到的那个大神写的propagate算法没有用PriorityQueue, 而只是最后全部处理完了之后一个sort拉倒;

写这个的时候重新思考了一下之前那个大神的做法, 发现那个大神的其实不是一个PriorityQueue的做法: 他只是在最开始的时候sort了一下, 后面propagate之后的priority实际上是始终没有更新的; 也就是说这个priority只反映了最开始还没有开始solve的时候的constraint的情况; 这个可能稍微有点作用, 不过不是最理想的; 不过那里的一个做法或许值得借鉴: 只维护所有Empty的;

但是对比下来, 就可以看到, 这个总理算法基本是这题的最优解了: 虽然这里选择priority的方式有点麻烦, 是linear的, 但是因为总共的size并不大, 所以最后速度还可以; 加上最起码考虑的信息比之前那个只sort一次的要多, 所以最后实际的搜索速度估计是更快的;

一个typo调了大半天, 简直恼火; 但是调完之后的速度很惊人, 3(100). 这个就很牛逼了;

don't share initialization

今天又犯了一个低级的错误:

entry = sequence = square_to_row = square_to_col = square_to_cube = new int[81];

这个跟以前一个Arrays.fill用法的时候犯的错误是一样的, 一定记住, 尤其是init的时候, 不要用同一个object去init不同的指针;

我自己在下面发的讲解:

To understand this algorithm, you first have to understand the common usage of bitmasks. If we have a bitmap, which is initialized to 11..11, each bit representing something (as define d by you) being available, then there are some common operations regarding a bitmask of the format 0..010..0 (there can be multiple 1 bits):

• allocate: bitmap &= ~bitmask: which clear out in bitmap all bits corresponding to 1 bits in bitmask.
• deallocate: bitmap |= bitmask, which set back those bits mentioned above.

Hopefully you can gain some insights now for this algorithm. The powerful parts of this algorithm are:

• bit operation: row_bitmap[i] is a bitmap that marks the digit (0 to 9) availability of a row i, and col_bitmap, cube_bitmap similarly. For example: row_bitmap[1] = 1101101110 means that only digits 4, 7 are unavailable from row 1 now (not including 0).
  The nice thing about this is, when you have all these, you can calculate the search space for any entry! Suppose you are now at board[i][j] (which in the algorithm is represented by a 1-D index square), then the cell_bitmap as calculated in the code above (& together) represents the available digits for entry [i][j]. We can then use bitmap & -bitmap trick to extract out the last bit, indicating our intent to use it (thus making it unavailable/allocated) now, and then we clear out this bit from the cell_bitmap with the allocate operation discussed above.
  Note that this style of bit manipulation is actually well-known and frequently used in the study of 8Quees problem.
• Priority: There was another solution that more or less used such a concept of priority as well. The basic idea is, you want to search the entry with less options (smaller search space) first. This is based on some theory in constraint processing which I don't feel confident in explaining here. Intuitively, you want to search the most constrained variable (a variable ordering heuristic) first to make the search tree generally smaller.
  This prioritization is implemented here with linear search: all empty cells' 1D indices (square) are stored in the array sequence. We move from left to right, at each iteration find the most constrained cell by a linear scan, then swap it to the front, find a digit for it, then move on. I tried to implement this with Priority Queue, but it does not seem so feasible: PQ only adjusts its order during get/set operations, while during solving, we sometimes fill a cell, ending up changing the priorities (indicated by the number of available digits) of other cells: but the PQ is not aware of that, meaning it will maintain the wrong or at least not-really-useful order.
• Pre-calculation: the array square_to_row (and two other similar arrays) is simply a utility to store the mapping from the 1D index of a cell, square, to the corresponding row_idx (or col_idx, cube_idx). Since we are storing all values in the array entry, most of the time we are dealing with the 1D index square, which also makes backtracking argument passing easier. We would occasionally need to convert 1D index back to 2D, and storing these calculations' mappings is just some trick to trade space for time.

Problem Description

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

A sudoku puzzle...

...and its solution numbers marked in red.

Difficulty:Hard
Total Accepted:87.4K
Total Submissions:276.1K
Contributor:LeetCode
Companies
ubersnapchat
Related Topics
hash tablebacktracking
Similar Questions
Valid Sudoku