解数独算法详解编程语言

class Solution { 
public: 
void solveSudoku(vector<vector<char>>& board) { 
//每一行里1-9使用的数字 
vector<vector<bool>> vec_row_b(9,vector<bool>(10,false)); 
//每一列 
vector<vector<bool>> vec_col_b(9,vector<bool>(10,false));
//这里可以优化下，二维数组就够了，int b = (i / 3 ) * 3 + j / 3; box[b][n] 
vector<vector<vector<bool>>> vec_box_b(3,vector<vector<bool>>(3,vector<bool>(10,false))); 
for(int i_row=0;i_row<board.size();i_row++) 
{ 
for(int j_col=0;j_col<board[0].size();j_col++) 
{ 
if(board[i_row][j_col]-'0'>=1&&board[i_row][j_col]-'0'<=9) 
{ 
int num=board[i_row][j_col]-'0'; 
vec_row_b[i_row][num]=true; 
vec_col_b[j_col][num]=true; 
vec_box_b[i_row/3][j_col/3][num]=true; 
} 
} 
} 
RecuSolveSudu(board,vec_row_b,vec_col_b,vec_box_b,0,0); 
} 
bool RecuSolveSudu(vector<vector<char>>&board,vector<vector<bool>>vec_row,vector<vector<bool>> vec_col,vector<vector<vector<bool>>>vecc_box,int row,int col) 
{ 
//一行的校验结束 
if(board[0].size()==col) 
{ 
col=0; 
row++; 
//所有的校验结束 
if(row==board.size()) 
{ 
return true; 
} 
} 
//空白的循环才有意义 
if(board[row][col]=='.') 
{ 
//遍历这一行一列未使用的数 
for(int i=1;i<=9;i++) 
{ 
bool can_used=!(vec_row[row][i]||vec_col[col][i]||vecc_box[row/3][col/3][i]); 
if(can_used) 
{ 
board[row][col]='0'+i; 
vec_row[row][i]=true; 
vec_col[col][i]=true; 
vecc_box[row/3][col/3][i]=true; 
if(RecuSolveSudu(board,vec_row,vec_col,vecc_box,row,col+1)) 
{ 
//返回true了 就说明找到答案了 ，立刻返回 
return true; 
} 
//否则回溯回来 继续尝试 
board[row][col]='.'; 
vec_row[row][i]=false; 
vec_col[col][i]=false; 
vecc_box[row/3][col/3][i]=false; 
} 
} 
} 
else 
{ 
return RecuSolveSudu(board,vec_row,vec_col,vecc_box,row,col+1); 
} 
return false; 
} 
};