数独C++ |
您所在的位置:网站首页 › 数独做题时间 › 数独C++ |
点击查看更多通信与专业知识 华为2016研发工程师编程题 数独是一个我们都非常熟悉的经典游戏,运用计算机我们可以很快地解开数独难题,现在有一些简单的数独题目,请编写一个程序求解。 如有多解,输出一个解 输入描述: 输入9行,每行为空格隔开的9个数字,为0的地方就是需要填充的。输出描述: 输出九行,每行九个空格隔开的数字,为解出的答案。 思路网上关于求解数独的题目也有很多方法,比如舞蹈链、摒弃法等等,这些网上都有教程。但是因为时间比较紧,我直接采用了暴力求解的方法,这个方法有以下关键点: 1. 采用了递归的思想,构造了一个函数solveQues。 2. 对于输入的9*9的矩阵,直接找到第一个不为0的数(没有则返回true),然后求得这个位置的所有可能性(和所在的行、所在的列、所在的宫里的数字都不冲突),如果可能性为空,则返回false,否则进行枚举,并调用solveQues函数进行递归运算, 如果递归失败,则继续枚举,否则返回true。如果对所有的枚举值都失败,则返回false。 原文链接:https://www.jianshu.com/p/1875bfeaff12 #include using namespace std; bool solveQues(int question[9][9]) { set numpos; for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { if (question[i][j] == 0) { for (int k = 0; k < 9; k++) { numpos.insert(question[i][k]); numpos.insert(question[k][j]); } for (int m = 0; m < 3; m++) { for (int n = 0; n < 3; n++) { numpos.insert(question[i/3*3+m][j/3*3+n]); } } if (numpos.size() == 10) { return false; } for (int k = 1; k < 10; k++) { if (numpos.find(k) == numpos.end()) { question[i][j] = k; if (solveQues(question)) { return true; } } } question[i][j] = 0; return false; } } } return true; } int main() { int a; while (cin >> a) { int question[9][9]; question[0][0] = a; for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { if (i == 0 && j == 0) { continue; } cin >> question[i][j]; } } if (solveQues(question) ){ for (int i = 0; i < 9; i++) { cout |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |