编写一个程序，通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3×3 宫内只能出现一次。
空白格用 ‘.’ 表示。
Note:
- 给定的数独序列只包含数字
1-9和字符'.'。 - 你可以假设给定的数独只有唯一解。
- 给定数独永远是
9x9形式的。
解:还是用回溯法，代码量看着有点多，其实挺简单
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;
}
};
原创文章，作者：奋斗，如若转载，请注明出处：https://blog.ytso.com/17557.html