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.
思路：
dfs搜索所有可行解，每个空格从1-9开始逐一遍历，isValid()函数判断该空格是否能放这个数。如果能，则继续dfs递归，如果不能就继续下一个数。如果遍历完了1-9仍然没有可行解，就说明前面的空格填入的数字不对，只能返回改变前面的数字。如此遍历，直到最后一个空格仍然满足条件时，说明找到了可行解。用一个变量flag标记是否找到了可行解。如果没有找到可行解，就还原现在的数字，变成初始状态(.)，继续循环；如果找到了，就直接返回而不再循环，逐一退出递归。这个flag很重要，如果没有这个flag，虽然找到了可行解，但是在逐一退出递归的时候余下的循环仍然会继续进行，board[i][j]的值就会改变，这样全部递归推出的时候，结果很奇怪。
其实晚上还有一种方法，思路差不多，只是将dfs()函数变成又返回值的，而不再是void。这样如果找到可行解，返回true，否则返回false。
题解：
class Solution { public: bool flag = false; //判断是否找到可行解 bool isValid(vector<vector<char> > &board, int row, int col) { for(int j=0;j<9;j++) if(j!=col && board[row][col] == board[row][j]) return false; for(int i=0;i<9;i++) if(i!=row && board[row][col] == board[i][col]) return false; int x = row/3*3; int y = col/3*3; for(int i=0;i<3;i++) for(int j=0;j<3;j++) if(x+i!=row && y+j!=col && board[row][col] == board[x+i][y+j]) return false; return true; } void dfs(vector<vector<char> > &board) { int k; for(int i=0;i<9;i++) for(int j=0;j<9;j++) { if(board[i][j]=='.') { for(k=0;k<9;k++) { board[i][j] = k+'1'; if(isValid(board,i,j)) dfs(board); if(!flag) //如果没找到可行解，才会还原 board[i][j] = '.'; else //已经找打了可行解，直接返回，不在继续接下来的循环 return; } if(k==9) //维护如果填入1—9都不满足时，说明前面的结果有问题 return; } if(i==8 && j==8) //找到了可行解 flag = true; } } void solveSudoku(vector<vector<char> > &board) { dfs(board); } };
后话：
就像在思路中的那样，可以将dfs()函数变成返回值为bool类型的函数，感觉这种方法应该更牛逼一点。就贴出两篇这种方法的吧
http://www.cnblogs.com/ganganloveu/p/3828401.html 和 http://www.cnblogs.com/panda_lin/archive/2013/11/04/sudoku_solver.html