C++刷LeetCode（37. 解数独）【回溯】
题目描述：编写一个程序，通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 '.' 表示。
一个数独。
答案被标成红色。
Note:
给定的数独序列只包含数字 1-9 和字符 '.' 。
你可以假设给定的数独只有唯一解。
给定数独永远是 9x9 形式的。
class Solution {
private:
int row = {0};
int col = {0};
int matrix = {0};
public:
bool dfs(vector<vector<char> >&board, int index1, int index2){
if(index1 > 8) return true;
if(board == '.'){
for(char number = '1' ; number <= '9'; number++){
int number1 = number - '1';
if(row == 1 || col == 1 || matrix == 1)continue;
row = 1;
col = 1;
matrix = 1;
board = number;
if(dfs(board, index1 + (index2 + 1)/9, (index2 + 1)%9)) return true;
//回溯
board = '.';
matrix = 0;
col = 0;
row = 0;
}
}
else return dfs(board,index1 + (index2 + 1)/9, (index2 + 1)%9);
return false;
}
void solveSudoku(vector<vector<char>>& board) {
//初始化变量
for(int i = 0 ; i < 9; i++){
for(int j = 0; j < 9; j ++){
if(board != '.'){
int number = board - '1';
row = 1;
col = 1;
matrix = 1;
}
}
}
dfs(board, 0, 0);
return;
}
};
参考链接：https://leetcode-cn.com/problems/sudoku-solver/solution/fan-zheng-wo-jue-de-wo-zhe-ge-cai-ji-de-dai-ma-hen/
注意事项：注意函数dfs的写法。 没写出来{:10_250:}
页:
[1]