Sudoku Solver
给一个2d数组, 是一个数独, 求解决数独问题.
public class Solution {
public void solveSudoku(char[][] board) {
ArrayList<Integer> empty = new ArrayList<Integer>();
for(int i = 0 ; i < board.length; i++) {
for(int j = 0 ; j < board[0].length; j++) {
if(board[i][j] == '.')
empty.add(i*9+j);
}
}
int len = empty.size();
dfs(empty,len,board,0);
}
public boolean dfs(ArrayList<Integer> empty, int len, char[][] board, int cur) {
if(cur == len){
return true;
}
int index = empty.get(cur);
int row = index / 9;
int col = index % 9;
for(int v = 1; v <= 9; v++) {
if(isValid(board, v, row, col)){
board[row][col] = (char)(v+'0');
if(dfs(empty,len,board,cur+1))
return true;
board[row][col] = '.';
}
}
return false;
}
public boolean isValid(char[][] board, int v, int row, int col) {
for(int i = 0 ; i < 9; i++ ){
if(board[row][i] == v + '0')
return false;
if(board[i][col] == v + '0')
return false;
int r = 3*(row/3) + (i/3);
int c = 3*(col/3) + (i%3);
if(board[r][c] == v + '0')
return false;
}
return true;
}
}