BiruLyu
7/31/2017 - 11:46 PM

## 37. Sudoku Solver(#).java

``````public class Solution {
private int[][] col = new int[9][9];
private int[][] row = new int[9][9];
private int[][] grid = new int[9][9];
public void solveSudoku(char[][] board) {
for(int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++){
if (board[i][j] != '.') {
int num = board[i][j] - '1';
row[i][num] = col[j][num] = grid[i/3*3+j/3][num] = 1;
// i/3 would be int divide
// 9 grid
}
}
}
dfs(board, 0);
}

private boolean dfs(char[][] board, int pos) {
if (pos == 81) {
return true;
}
int x = pos/9, y = pos%9;
if (board[x][y] != '.') {
return dfs(board, pos + 1);
}
for (int i = 0; i < 9; i++) {
if (row[x][i]  == 0 && col[y][i] == 0 && grid[x/3*3+y/3][i] == 0){
row[x][i] = col[y][i] = grid[x/3*3+y/3][i] = 1;
if (dfs(board, pos+1)) {
board[x][y] = (char)(i + '1');
return true;
}
row[x][i] = 0;
col[y][i] = 0;
grid[x/3*3+y/3][i] = 0;
}
}
return false;
}

}``````
``````public class Solution {
private boolean solver(int idx, char[][] board, ArrayList<Integer> stack, int[] store) {
if (idx == stack.size()) return true;
int n = stack.get(idx);
int y = n / 9;
int x = n - y * 9;
int h = y;
int v = 9 + x;
int b = 18 + (y / 3 * 3 + x / 3);
int available = ~store[h] & ~store[v] & ~store[b] & 0b111111111;
while (available > 0) {
int bit = available & -available;
int num = Integer.numberOfTrailingZeros(bit);
store[h] ^= bit;
store[v] ^= bit;
store[b] ^= bit;
board[y][x] = (char)(num + '1');
if (solver(idx + 1, board, stack, store)) return true;
store[h] ^= bit;
store[v] ^= bit;
store[b] ^= bit;
// board[y][x] = '.';
available &= available - 1;
}
return false;
}
public void solveSudoku(char[][] board) {
ArrayList<Integer> stack =  new ArrayList<>();
// int[] stack = new int[81];
int len = 0;
int[] store = new int[27]; // 0-8 h, 9 - 17 v, 18 - 26 b
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.') stack.add(i * 9 + j);
else {
int h = i;
int v = 9 + j;
int b = 18 + (i / 3 * 3 + j / 3);
store[h] ^= 1 << board[i][j] - '1';
store[v] ^= 1 << board[i][j] - '1';
store[b] ^= 1 << board[i][j] - '1';
}
}
}
solver(0, board, stack, store);
}
}``````
``````public class Solution {
public void solveSudoku(char[][] board) {
if(board == null || board.length == 0)
return;
solve(board);
}

public boolean solve(char[][] board){
for(int i = 0; i < board.length; i++){
for(int j = 0; j < board[0].length; j++){
if(board[i][j] == '.'){
for(char c = '1'; c <= '9'; c++){//trial. Try 1 through 9
if(isValid(board, i, j, c)){
board[i][j] = c; //Put c for this cell

if(solve(board))
return true; //If it's the solution return true
else
board[i][j] = '.'; //Otherwise go back
}
}

return false;
}
}
}
return true;
}

private boolean isValid(char[][] board, int row, int col, char c){
for(int i = 0; i < 9; i++) {
if(board[i][col] != '.' && board[i][col] == c) return false; //check row
if(board[row][i] != '.' && board[row][i] == c) return false; //check column
if(board[3 * (row / 3) + i / 3][ 3 * (col / 3) + i % 3] != '.' &&
board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false; //check 3*3 block
}
return true;
}
}``````