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.
A sudoku puzzle...
1 每个backtracking的题目，最好都有独立判断isValid的程序，这样架构清楚。同时，valid判断函数在这里可以稍微研究一下。只要当前要判断的位置上的数值和本行没有重复，本列没有重复，九宫格没有重复就可以。一旦重复立即返回，减少判断次数。
2 backtracking的递归函数，怎么能没有返回值呢？！因为要判断递归的方案正确与否，所以这里的递归一定是有返回值的（除非是combination那种没有正确错误概念的backtracking）！
3 可以考虑“先放置，再判断”的方案。比如这里，首先判断当前位置是否为空，如果为空，那么放置一个元素，检查它是否正确。如果正确，就继续进行下面的递归（也就是第29行 isValid&&solveSudoku的作用）。当函数返回错误之后，将刚刚的数值变为空，再进行下一次尝试即可。
5 最后一点需要注意的是，当i,j循环完毕之后，表明已经解出了sudoku，需要返回！切记切记，最终情况！
简单地说思路就是循环处理子问题，对于每个格子，带入不同的9个数，然后判合法，如果成立就递归继续，结束后把数字设回空。大家可以看出代码结构和N-Queens是完全一样的。判合法其实在这里因为每次进入时已经保证之前的board不会冲突，所以不需要判断整个盘，只需要看当前加入的数字和之前是否冲突就可以，这样可以大大提高运行效率，毕竟判合法在程序中被多次调用。
class Solution { public void solveSudoku(char[][] board) { helper(board,0,0); } //判断row,col位置是否为'.'，是的话就设置值。 //因为要判断是否正确，所以需要返回值 public boolean helper(char[][] board,int row,int col){ if(col>=9){ //下一个位置超出列，就是进行下一行 return helper(board,row+1,0); } if(row==9){ return true; } //如果该位置是'.'，则要添加数字 if(board[row][col]=='.'){ //依次给该位置添加1-9 for(int k=1;k<=9;k++){ board[row][col]=(char)(k+'0'); if(isValid(board,row,col)){//如果有效，就进行下一个位置添加 if(helper(board,row,col+1))//如果后面的添加返回true,表明添加成功，返回true，否则就尝试下一个k return true; } board[row][col]='.'; } }else{ return helper(board,row,col+1); } return false; } /* 前面都已经判断了，只要判断该位置添加数字后是否符合要求，也就是看该行、列有没有和该元素相同的，而且该位置所在的九宫格中也不能有和它相同的 */ public boolean isValid(char[][] board,int row,int col){ //判断列是否有相同的，再同列不同行，元素却相同 for(int i=0;i<9;i++){ if(i!=row&&board[i][col]==board[row][col]) return false; } //判断行是否有相同的，同行不同列 for(int j=0;j<9;j++){ if(j!=col&&board[row][col]==board[row][j]) return false; } //判断该位置所在九宫格是否有相同的 /*要根据该位置找到所在九宫格的行和列的范围 每个九宫格的行的范围是0-2,3-5,6-8, */ 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((i!=row||j!=col)&&board[i][j]==board[row][col]) return false; } } return true; } }