【刷题小结】华为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题又不想改代码的人倒可以加上试试。