题目
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.
解数独，空格用 '.' 表示
思路
1 这个题目，想到自己平时做数独的技巧，感觉无法应用上去啊。
2 看了两个大牛的博客，http://blog.csdn.net/fightforyourdream/article/details/16916985 ，原来是dfs+回溯，其实也就是暴力破解啦。
3 想想也对，一共就9*9 ，不会有数据扩散得太大。
4 一般来说，如果不是求所有组合，dfs都需要有返回值。
代码
public class Solution {
public void solveSudoku(char[][] board) {
dfs(board);
}
public boolean dfs(char[][] board){
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
if(board[i][j]=='.'){
for(int k=0;k<9;k++){
board[i][j]=(char)(k+'1');
if(isValid(board,i,j)&&dfs(board)){
return true;
}
board[i][j]='.';
}
return false;
}
}
}
return true;
}
public boolean isValid(char[][] board, int x,int y){
int temp = board[x][y];
for(int i=0;i<9;i++){
if(i!=x && board[i][y]==temp){
return false;
}
}
for(int j=0;j<9;j++){
if(j!=y && board[x][j]==temp){
return false;
}
}
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
int tempx = 3*(x/3)+i;
int tempy = 3*(y/3)+j;
if (tempx != x && tempy != y && board[tempx][tempy] == temp)
return false;
}
}
return true;
}
}