8 ms Java bit map solution


  • 0
    L
    1. Use 3 bit map arrays to track which numbers have been used in rows, cols and 3x3 regions.
    2. start solving the problem from position 0. If it is NOT EMPTY (indicated by '.') then check the next position.
    3. if it IS EMPTY, then try to fill current position with char '1'.
      if it returns true, then done.
      else rollback current char and bit maps, then check the next char '2' till '9'.
    public class Solution {
        private static final int SIZE = 9;
        private static final int TOTAL = SIZE * SIZE;
        private int[] rowBitMap;
        private int[] colBitMap;
        private int[][] regionBitMap;
    
        public void solveSudoku(char[][] board) {
            if (board == null || board.length != SIZE || board[0].length != SIZE) {
                return;
            }
            initBitMaps(board);
            solve(board, 0);
        }
    
        private void initBitMaps(char[][] board) {
            rowBitMap = new int[SIZE];
            colBitMap = new int[SIZE];
            regionBitMap = new int[SIZE / 3][SIZE / 3];
    
            for (int i = 0; i < SIZE; i++) {
                for (int j = 0; j < SIZE; j++) {
                    if (board[i][j] != '.') {
                        int bit = 1 << (board[i][j] - '1');
                        setBitMap(i, j, bit);
                    }
                }
            }
        }
    
        private void setBitMap(int i, int j, int bit) {
            rowBitMap[i] |= bit;
            colBitMap[j] |= bit;
            regionBitMap[i / 3][j / 3] |= bit;
        }
    
        private void undoBitMap(int i, int j, int bit) {
            //Rollback bit maps
            int mask = ~bit;
            rowBitMap[i] &= mask;
            colBitMap[j] &= mask;
            regionBitMap[i / 3][j / 3] &= mask;
        }
    
        public boolean solve(char[][] board, int pos) {
            if ( pos == TOTAL) { 
                return true;    //return true when reach to the end of the board
            }
            int i = pos / SIZE; //convert pos to the x index
            int j = pos % SIZE; //convert pos to the y index
    
            if (board[i][j] == '.') {
                //get all used bits from row, column and 3*3 region
                int usedBits = rowBitMap[i] | colBitMap[j] | regionBitMap[i / 3][j / 3];
                int bit = 1;
                for (char c = '1'; c <= '9'; c++) {//trial. Try 1 through 9
                    //unused bits should be 0,
                    if ((usedBits & bit) == 0) {
                        board[i][j] = c; //Put c for this cell
                        setBitMap(i, j, bit);
    
                        if (solve(board, pos + 1)) {
                            return true; //If it's the solution return true
                        } else {
                            board[i][j] = '.'; //Otherwise go back
                            undoBitMap(i, j, bit);
                        }
                    }
                    //keep increase bit with c
                    bit <<= 1;
                }
                return false;
            } else {
                return solve(board, pos + 1);
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.