这道题。。真是有点难。
首先，这题的套路我懂，是N皇后那种全排列DFS问题。有几个难以理解的点，第一，为什么这题的dfs 返回值是boolean而不是void。
这篇blog上解释说：
只有正确达到最终81位置（即成功填充）的填充结果才可以返回，若不然，将会得到错误的填充。因此辅助函数solve需要设为bool而不是void。
Code ganker评论区4楼的朋友解释说：
我觉得helper的boolean返回值是有必要的 否则在21行处无法判定是否需要return 如果已经找到valid solution 应该直接return以跳过24行的backtrack。
他们说的都挺有道理的。我的理解是，这个函数是用来判断是否需要「恢复现场」的，也就是如果判断出来这个是true，就进入下一层，不用把board[i][j]置为'.'了。
第二个问题就是dfs里的各种返回值，比如dfs最后应该返回true还是false？这题有很多种写法，小莹子和九章的写法是用两个9的for循环遍历棋盘，他们都没有递归的终止条件，而是在for循环里加了一些我看不懂的return true/false语句。这让我觉得不太正规。我暂时的理解是，如果前面已经有了return true的终止条件了，那最后就return false。 Word Search那题就是如此。
代码的话，我贴一下code ganker的代码吧，之前模仿他的写过，AC了，今天用另外一个写法写，一直WRONG ANSWER，实在不想调试了，这种很长的题目，又是递归，真的很难调试。
下面这段代码来自code ganker：
public void solveSudoku(char[][] board) {
if(board == null || board.length != 9 || board[0].length !=9)
return;
helper(board,0,0);
}
private boolean helper(char[][] board, int i, int j)
{
if(j>=9)
return helper(board,i+1,0);
if(i==9)
{
return true;
}
if(board[i][j]=='.')
{
for(int k=1;k<=9;k++)
{
board[i][j] = (char)(k+'0');
if(isValid(board,i,j))
{
if(helper(board,i,j+1))
return true;
}
board[i][j] = '.';
}
}
else
{
return helper(board,i,j+1);
}
return false;
}
private boolean isValid(char[][] board, int i, int j)
{
for(int k=0;k<9;k++)
{
if(k!=j && board[i][k]==board[i][j])
return false;
}
for(int k=0;k<9;k++)
{
if(k!=i && board[k][j]==board[i][j])
return false;
}
for(int row = i/3*3; row<i/3*3+3; row++)
{
for(int col=j/3*3; col<j/3*3+3; col++)
{
if((row!=i || col!=j) && board[row][col]==board[i][j])
return false;
}
}
return true;
}
再贴一下今晚写的代码吧，模仿http://www.cnblogs.com/ganganloveu/p/3828401.html 写的，但一直没办法AC，以后有时间可以调试一下。
public class Solution {
public void solveSudoku(char[][] board) {
helper(board, 0);
}
private boolean helper(char[][] board, int position) {
if (position == 81) return true;
int row = position / 9;
int col = position % 9;
if (board[row][col] == '.') {
for (char i = '1'; i <= '9'; i++) {
board[row][col] = i;
//如果这个数字不会让棋盘坏掉，就用dfs插下一个数字
if (isValid(board, row,col)) {
//如果这样下去可以构造成一个pos == 80的完整board的话，就不用恢复现场了
if (helper(board, position + 1)) {
return true;
} else {
board[row][col] = '.';
}
}
}
} else {
// if (helper(board, position + 1)) return true;
return helper(board, position + 1);
}
//return false是因为 return true的终止条件已经写在最前面了
return false;
}
private boolean isValid(char[][] board, int i, int j)
{
for(int k=0;k<9;k++)
{
if(k!=j && board[i][k]==board[i][j])
return false;
}
for(int k=0;k<9;k++)
{
if(k!=i && board[k][j]==board[i][j])
return false;
}
//只需要检查当前的units就行了
for(int row = i/3*3; row<i/3*3+3; row++)
{
for(int col=j/3*3; col<j/3*3+3; col++)
{
// i == row && j == col的否命题是(i != row || j != col)，同时注意||优先级小于&&
if((row!=i || col!=j) && board[row][col]==board[i][j])
return false;
}
}
return true;
}
}
