LC37. Sudoku Solver
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.
数独谜题… 当初刚买新手机，没什么游戏天天玩数独还真是闲散时光XD
Backtracking的题目，对于每一个空白，分别填入1-9，如果合理，就继续填入其他空白，否则停止。利用回溯找到所有可能性。
public class Solution {
public void solveSudoku(char[][] board) {
if(board == null || board.length == 0) return;
solve(board);
}
private boolean solve(char[][] board){
int n = board.length;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(board[i][j] == '.'){
for(char nn = '1'; nn <= '9'; nn++){
if(valid(board, nn, i, j)){
board[i][j] = nn;
if(solve(board)) return true;
board[i][j] = '.';
}
}
return false;
}
} // for j
} // for i
return true;
} // solve
private boolean valid(char[][] board, char num, int row, int col){
int n = board.length;
for(int i = 0; i < n; i++){
if(board[row][i] == num) return false;
if(board[i][col] == num) return false;
}
for(int i = (row/3)*3; i < (row/3)*3+3; i++){
for(int j = (col/3)*3; j < (col/3)*3+3; j++){
if(board[i][j] == num) return false;
}
}
return true;
} // valid
}
O(9^m)….m = num of blank