个人主页:元清加油_【C++】,【C语言】,【数据结构与算法】-CSDN博客
个人专栏
力扣递归算法题
【C++】? ??
??????http://t.csdnimg.cn/6AbpV
数据结构与算法
??????http://t.csdnimg.cn/hKh2l
前言:这个专栏主要讲述递归递归、搜索与回溯剪枝算法,所以下面题目主要也是这些算法做的 ?
我讲述题目会把讲解部分分为3个部分:
1、题目解析
2、算法原理思路讲解
3、代码实现
题目链接:解数独
题目
编写一个程序,通过填充空格来解决数独问题。
数独的解法需?遵循如下规则:
1-9
?在每一行只能出现一次。1-9
?在每一列只能出现一次。1-9
?在每一个以粗实线分隔的?3x3
?宫内只能出现一次。(请参考示例图)数独部分空格内已填入了数字,空白格用?'.'
?表示。
示例 1:
输入:board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]] 输出:[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]] 解释:输入的数独如上图所示,唯一有效的解决方案如下所示:
提示:
board.length == 9
board[i].length == 9
board[i][j]
?是一位数字或者?'.'
bool checkRow[9][10];
bool checkCol[9][10];
bool gird[3][3][10];
(2)设计递归函数
bool dfs(vector<vector<char>>& board);
class Solution {
public:
bool checkRow[9][10];
bool checkCol[9][10];
bool gird[3][3][10];
bool dfs(vector<vector<char>>& board)
{
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
if (board[i][j] == '.')
{
for (int m = 1; m <= 9; m++)
{
if (!checkRow[i][m] && !checkCol[j][m] && !gird[i / 3][j / 3][m])
{
board[i][j] = m + '0';
checkRow[i][m] = checkCol[j][m] = gird[i / 3][j / 3][m] = true;
if (dfs(board) == true)
return true;
board[i][j] = '.';
checkRow[i][m] = checkCol[j][m] = gird[i / 3][j / 3][m] = false;
}
}
return false; // 到这说明上一步已经错了
}
}
}
return true;
}
void solveSudoku(vector<vector<char>>& board)
{
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
if (board[i][j] != '.')
{
int number = board[i][j] - '0';
checkRow[i][number] = checkCol[j][number] = gird[i / 3][j / 3][number] = true;
}
}
}
dfs(board);
}
};