哪些网站可以做顺风车,家政公司网站建设方案,大连市开发区网站建设公司,广州企业黄页大全目录题目核心思路的不断细化1、核心框架2、考虑到每个位置的工作3、考虑到到达最后一列、该位置的数已经预置的情况4、判断是否符合规则的函数5、确定递归终止条件确定函数返回值AC代码题目
编写一个程序#xff0c;通过填充空格来解决数独问题。 一个数独的解法需遵循如下规… 目录题目核心思路的不断细化1、核心框架2、考虑到每个位置的工作3、考虑到到达最后一列、该位置的数已经预置的情况4、判断是否符合规则的函数5、确定递归终止条件确定函数返回值AC代码 题目
编写一个程序通过填充空格来解决数独问题。 一个数独的解法需遵循如下规则 1、数字 1-9 在每一行只能出现一次。 2、数字 1-9 在每一列只能出现一次。 3、数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 空白格用 ‘.’ 表示。 一个数独。 答案被标成红色。 提示 给定的数独序列只包含数字 1-9 和字符 ‘.’ 。 你可以假设给定的数独只有唯一解。 给定数独永远是 9x9 形式的。 核心思路的不断细化
算法的核心思路就是对每一个空着的格子穷举 1 到 9如果遇到不合法的数字在同一行或同一列或同一个 3×3 的区域中存在相同的数字则跳过如果找到一个合法的数字则继续穷举下一个空格子。 写出核心框架
1、核心框架
void solveSudoku(vectorvectorchar board) {backtrack(board, 0, 0);
}void backtrack(vectorvectorchar board, int hang, int lie) {// 就是对棋盘的每个位置进行穷举for (int i hang; i 9; i) {for (int j lie; j 9; j) {// 做选择backtrack(board, i, j);// 撤销选择}}
}2、考虑到每个位置的工作
对于每个位置有1~9的选择这样就变成了3重嵌套循环。
void backtrack(vectorvectorchar board, int hang, int lie) {// 就是对每个位置进行穷举for (int i hang; i 9; i) {for (int j lie; j 9; j) {for (char ch 1; ch 9; ch) {// 做选择board[i][j] ch;// 继续穷举下一列backtrack(board, i, j 1);// 撤销选择board[i][j] .;}}}
}3、考虑到到达最后一列、该位置的数已经预置的情况
1、当lie到达超过最后一个索引时转为增加hang开始穷举下一行。 2、如果当前位置元素不为“.”那么跳过即可。 3、穷举的时候如果遇到符合规则的数字填入否则跳过。
void backtrack(vectorvectorchar board, int hang, int lie) {if(lie9){backtrack(board, hang1, 0);}// 就是对每个位置进行穷举for (int i hang; i 9; i) {for (int j lie; j 9; j) {// 如果该位置是预设的数字不用我们操心if (board[i][j] ! .) {backtrack(board, i, j 1);return;} //如果不是预置的数字for (char ch 1; ch 9; ch) {// 如果遇到符合规则的数字填入if (isValid(board, i, j, ch)){// 做选择board[i][j] ch;// 继续穷举下一列backtrack(board, i, j 1);// 撤销选择board[i][j] .;}}}}
}4、判断是否符合规则的函数
规则如下 1、数字 1-9 在每一行只能出现一次。 2、数字 1-9 在每一列只能出现一次。 3、数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 翻译成函数 注意这里对第3个规则的描述
// 判断 board[i][j] 是否可以填入 n
bool isValid(vectorvectorchar board, int hang, int lie, char n) {for (int i 0; i 9; i) {// 判断行是否存在重复if (board[hang][i] n) return false;// 判断列是否存在重复if (board[i][lie] n) return false;// 判断 3 x 3 方框是否存在重复if (board[(hang/3)*3 i/3][(lie/3)*3 i%3] n)return false;}return true;
}下面是这个式子的含义并且将i0~8模拟了一下
5、确定递归终止条件确定函数返回值
如果递归完最后一行那么我们就可以返回我们的结果了。 如果找到一个解我们的任务就结束了本题并没有要求找到所有解。 如果一个位置遍历完所有数字都不符合这说明此路不通应该及时返回false。 如果每个位置都遍历过了结果都没有返回true说明这个数独棋盘没有解返回false。 所以使用bool类型的值作为返回值
if(hang 9) return true;完整的回溯函数代码应该如下
bool backtrack(vectorvectorchar board, int hang, int lie) {//遍历完这一行最后一列转而遍历下一行if(lie9){return backtrack(board, hang1, 0);}//找到一个解返回if(hang 9) return true;// 就是对每个位置进行穷举for (int i hang; i 9; i) {for (int j lie; j 9; j) {// 如果该位置是预设的数字不用我们操心if (board[i][j] ! .) {return backtrack(board, i, j 1);} //如果不是预置的数字for (char ch 1; ch 9; ch) {// 如果遇到符合规则的数字填入if (isValid(board, i, j, ch)){// 做选择board[i][j] ch;// 继续穷举下一列如果找到了一个解立即结束if(backtrack(board, i, j 1) true) return true;// 撤销选择board[i][j] .;}}// 穷举完 1~9依然没有找到可行解此路不通return false;}}return false;
}AC代码
class Solution {
public:// 判断 board[i][j] 是否可以填入 nbool isValid(vectorvectorchar board, int hang, int lie, char n) {for (int i 0; i 9; i) {// 判断行是否存在重复if (board[hang][i] n) return false;// 判断列是否存在重复if (board[i][lie] n) return false;// 判断 3 x 3 方框是否存在重复if (board[(hang/3)*3 i/3][(lie/3)*3 i%3] n)return false;}return true;}bool backtrack(vectorvectorchar board, int hang, int lie) {//遍历完这一行最后一列转而遍历下一行if(lie9){return backtrack(board, hang1, 0);}//找到一个解返回if(hang 9) return true;// 就是对每个位置进行穷举for (int i hang; i 9; i) {for (int j lie; j 9; j) {// 如果该位置是预设的数字不用我们操心if (board[i][j] ! .) {return backtrack(board, i, j 1);} //如果不是预置的数字for (char ch 1; ch 9; ch) {// 如果遇到符合规则的数字填入if (isValid(board, i, j, ch)){// 做选择board[i][j] ch;// 继续穷举下一列如果找到了一个解立即结束if(backtrack(board, i, j 1) true) return true;// 撤销选择board[i][j] .;}}// 穷举完 1~9依然没有找到可行解此路不通return false;}}return false;}void solveSudoku(vectorvectorchar board) {backtrack(board, 0, 0);return;}
};
