本文主要是介绍c++程序求解9X9数独，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
也算是机缘巧合，在做力扣第三十六题有效的数独的时候没理解好题目意思，以为是要求解数独，正好我也觉得挺有意思，分享一下
解题方法主要使用回溯法，大致意思就是对于任意一个可填数字的位置，遍历所有可以填入的数字，填入数字后递归调用去下一个可填数字位置，当所有位置都被填满就找到了一个解
以下是我学习回溯法时的记录
是一种组织的井井有条的，能避免不必要搜索的穷举式搜索法
是在问题的解空间树中按深度优先策略从根结点触发搜索整个解空间树
对于每一点都要判断这一结点是否包含问题的解，如不包含则对兄弟节点搜索，包含才进入该子树继续深度优先策略搜索
回溯法希望问题的解可以表示为一个n元组{x1，x2，x3......xn} 解空间树 就是解所有的可能组成一棵树
A 第一层是第一个物品 左边代表放入，右边代表不放入 0
1/ \0
B C 第二层是第二个物品 1
/ \ / \
D E F G 第三层是第三个物品 2
/ \ / \ / \ / \
H I J K L M N O 3
但是这么看起来很多不是吗，回溯法为了避免生成不可能产生最佳解的问题状态，有一个剪枝函数来处死那些解以减少计算量
常用两类剪枝函数：用 约束函数 在扩展结点(还在生成儿子)处剪去不满足约束的结点、用 上界函数 剪去得不到最优解的子树
对于子集树这两个方法分别应用于左右分支 对于排列树(每一个分支性质一样)同时应用于每一个分支 但在我看来不是那么严格
回溯法在搜索过程中动态产生解空间树，即边搜边拓展
任何时候仅记录根到当前节点的路径
void backtrack(int t){ n是总层数或者说总个数
if(t>n){ t>n说明已经走到最下层以下了，那说明这个解已经构造完成 就像上面已经是4了，超过了最下层
output(x);
}else{
for(int i=f(n,t); i<=g(n,t); i++){ f(n,t)是左分支编号，g(n,t)代表右分支编号，也就是从左分支遍历到右分支,把每一个分支拓展出来
x[t] = h(i);
if(constraint(t)&&bound(t)) backtrack(t+1); 这个结点是否满足要求
}
}
}
常见的两种解空间树：选择树和排列树、其实还有个n叉树，具体看图的m着色问题 他们都是n+1层
选择树每个结点下面有两个分支 排列树,第一层往下3个，第二层往下排两个，第三层往下排一个
A A
1/ \0 1/ 2| \3
B C B C D 看最左边，123三个元素，如果上面选择排了1，比如AB
1/ \0 1/ \0 2/\3 1/\3 1/\2 那么下面B往下排就只能排2或者3，比如BE这条线
D E F G E F G H I G 再往下走因为AB排了1，BE排了2，那么EK就只能排3
3| |2 3| |1 2| |1
K L M N O P
关于算法的解题方法我推荐看中国大学mooc的算法设计与分析
青岛大学的那个，貌似贴截图会违规，各位自己找下吧，教授讲的超棒
具体包括回溯法、分支限界法、分治法、动态规划法等讲解
#include <vector>
#include <iostream>
namespace 有效的数独 {class Solution {public:std::vector<std::vector<std::vector<char>>> save;bool find = false;bool isValidSudoku(std::vector<std::vector<char>>& board) {int i = 0, j = 0;while (board[i][j] != '.') {if (j < board.size() - 1) { j++; continue;}if (i < board.size() - 1) { i++; j = 0; continue;}}BackTrack(board, i, j);if (find) { return true; };return false;}void BackTrack(std::vector<std::vector<char>>& board, int i, int j) {for (int x = 1; x <= board.size(); x++) { // 找数放if (Place(board, i, j, x)) { // 还能找到一个可以放if (i == board.size() - 1 && j == board.size() - 1) {find = true;save.push_back(board);return;}int temp1 = i, temp2 = j;while (board[i][j] != '.') {if (j < board.size() - 1) { j++; continue; }if (i < board.size() - 1) { i++; j = 0; continue; }find = true;save.push_back(board);return;}BackTrack(board, i, j);board[i][j] = '.';//指针得回到上一个位置i = temp1;j = temp2;}}}bool Place(std::vector<std::vector<char>>& board, int i, int j, int x) {// 行列不重复for (int a = 0; a < board.size(); a++) {if (board[i][a] == x + '0' || board[a][j] == x + '0') {//发现重复return false;}}// 3x3内不重复int startrow = i / 3 * 3, startcol = j / 3 * 3;for (int m = 0; m <= 2; m++) {for (int n = 0; n <= 2; n++){if (board[startrow + m][startcol + n] == x + '0') {return false;}}}board[i][j] = x + '0';return true;}};}
int main() {std::vector<std::vector<char>> a ={ {'.', '3', '.', '.', '7', '.', '.', '.', '.'},{'6', '.', '.', '1', '.', '5', '.', '.', '.'},{'.', '9', '8', '.', '.', '.', '.', '6', '.'},{'8', '.', '.', '.', '6', '.', '.', '.', '3'},{'.', '.', '.', '8', '.', '3', '.', '.', '1'},{'7', '.', '.', '.', '2', '.', '.', '.', '.'},{'.', '6', '.', '.', '.', '.', '2', '8', '.'},{'.', '.', '.', '4', '.', '9', '.', '.', '5'},{'.', '.', '.', '.', '.', '.', '.', '7', '.'} };有效的数独::Solution s;if (s.isValidSudoku(a)) {std::cout<<"有"<< s.save.size()<<"个解" << std::endl;for (int t = 0; t <s.save.size() ; t++){std::cout << "第" << t+1 << "个解:" << std::endl;for (int i = 0; i < a.size(); i++) {for (int j = 0; j < a.size(); j++){std::cout << s.save[t][i][j] << " ";}std::cout << std::endl;}std::cout << std::endl;}}else{std::cout << "无解";}}输入待解数独后的输出
‘.’的位置代表这里是空的，还没有填入数字
这篇关于c++程序求解9X9数独的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
