8 ms Java bit map solution

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
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);
}
}
}
``````

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