数独C++

点击查看更多通信与专业知识

华为2016研发工程师编程题

数独是一个我们都非常熟悉的经典游戏，运用计算机我们可以很快地解开数独难题，现在有一些简单的数独题目，请编写一个程序求解。

如有多解，输出一个解

输入描述:

输入9行，每行为空格隔开的9个数字，为0的地方就是需要填充的。

输出描述:

输出九行，每行九个空格隔开的数字，为解出的答案。

思路

  网上关于求解数独的题目也有很多方法，比如舞蹈链、摒弃法等等，这些网上都有教程。但是因为时间比较紧，我直接采用了暴力求解的方法，这个方法有以下关键点：
   1. 采用了递归的思想，构造了一个函数solveQues。
   2. 对于输入的9*9的矩阵，直接找到第一个不为0的数（没有则返回true），然后求得这个位置的所有可能性（和所在的行、所在的列、所在的宫里的数字都不冲突），如果可能性为空，则返回false，否则进行枚举，并调用solveQues函数进行递归运算， 如果递归失败，则继续枚举，否则返回true。如果对所有的枚举值都失败，则返回false。

原文链接：https://www.jianshu.com/p/1875bfeaff12

#include<bits/stdc++.h>
    using namespace std;
    
    bool solveQues(int question[9][9])
    {
        set<int> 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 << question[i][0];
                    for (int j =1; j < 9; j++) {
                        cout << " "<< question[i][j];
                    }
                    cout << endl;
                }
            }
        }
        return 0;
    }