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.判断函数实现的功能是判断每一行，每一列，每一个子矩阵是否有重复的数字。 3.采用递归的思想来求解。
class Solution { public: void solveSudoku(vector<vector<char>>& board) { int rows=0; int cols=0; bool found=false; _dosolve(board,rows,cols,found); } bool isValidSudoku(vector<vector<char>>& board) { set<char> temp; int count=0; for(int i=0;i<board.size();i++){ //判断每一行 for(int j=0;j<board.size();j++) if(board[i][j]!='.'){ count++; temp.insert(board[i][j]); } if(temp.size()!=count) return false; count=0; temp.clear(); } for(int i=0;i<board.size();i++){ //判断每一列 for(int j=0;j<board.size();j++) if(board[j][i]!='.'){ count++; temp.insert(board[j][i]); } if(temp.size()!=count) return false; count=0; temp.clear(); } for(int i=0;i<board.size();i++){ //判断每一个3*3的矩阵 for(int j=0;j<board.size();j++) if(board[i/3*3+j/3][i%3*3+j%3]!='.'){ count++; temp.insert(board[i/3*3+j/3][i%3*3+j%3]); } if(temp.size()!=count) return false; count=0; temp.clear(); } return true; } private: void _dosolve(vector<vector<char>>& board,int rows,int cols,bool& found){ if(cols==9) _dosolve(board,rows+1,0,found); else if(rows==9){ found=true; return ; } else{ if(board[rows][cols]=='.'){ for(int i=1;i<=9;i++){ board[rows][cols]=i+'0'; if(isValidSudoku(board)==true){ _dosolve(board,rows,cols+1,found); if(found==true) return; } board[rows][cols]='.'; } } else _dosolve(board,rows,cols+1,found); } } };