华为2016研发工程师编程题-数独

题目描述

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

输入

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

输出

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

示例

输入

0 6 0 5 9 3 0 0 0
9 0 1 0 0 0 5 0 0
0 3 0 4 0 0 0 9 0
1 0 8 0 2 0 0 0 4
4 0 0 3 0 9 0 0 1
2 0 0 0 1 0 6 0 9
0 8 0 0 0 6 0 2 0
0 0 4 0 0 0 8 0 7
0 0 0 7 8 5 0 1 0

输出

7 6 2 5 9 3 1 4 8
9 4 1 2 7 8 5 3 6
8 3 5 4 6 1 7 9 2
1 9 8 6 2 7 3 5 4
4 7 6 3 5 9 2 8 1
2 5 3 8 1 4 6 7 9
3 8 7 1 4 6 9 2 5
5 1 4 9 3 2 8 6 7
6 2 9 7 8 5 4 1 3

解题

思路

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

代码

    #include <iostream>
    #include <cstring>
    #include <set>
    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;
    }

瑕疵

  这个代码只输出了一种结果，所以要用它去跑牛客网的题目的话，正确率只有83.33%，有一题有多解，然后我的答案和标准答案不一致，这个我我也很无奈，这个我就不计较了，但是下面有人贴出了一段代码：

    if(data[6][0]==2&&data[6][1]==1&&data[6][2]==3)
    {
        data[6][2]=5;data[6][3]=8;data[6][4]=4;data[6][5]=6;data[6][6]=9;data[6][7]=7;data[6][8]=3;
        data[7][0]=9;data[7][1]=6;data[7][2]=3;data[7][3]=7;data[7][4]=2;data[7][5]=1;data[7][6]=5;data[7][7]=4;data[7][8]=8;
        data[8][0]=8;data[8][1]=7;data[8][2]=4;data[8][3]=3;data[8][4]=5;data[8][5]=9;data[8][6]=1;data[8][7]=2;data[8][8]=6;
    }

  这个就看看了，只针对题库中的那一种情况，如果真的想A题又不想改代码的人倒可以加上试试。