数独 【C语言】华为2016研发工程师编程_c语言数独游戏交互性

参考：努力努力再努力r

题目：

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

输入格式

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

输出格式

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

输入样例

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

输出样例

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

算法

问题分析

玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3*3）内的数字均含1-9，不重复

代码实现

#include<stdio.h>
#include<stdbool.h>
#define SIZE 9
int Board[SIZE][SIZE];
int main()
{
	int i,j;
	for(i=0;i<SIZE;i++){
	    for(j=0;j<SIZE;j++){
	        scanf("%d",&(Board[i][j]));
	    }
	}
	if(Backtrack(0,0)){
	    for(i=0;i<SIZE;i++){
	        for(j=0;j<SIZE;j++){
	            if(j!=0){
	                printf(" ");
	            }
	            printf("%d",Board[i][j]);
	        }
	        printf("\n");
	    }
	}
	return 0;
}
		
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

Backtrack(回溯）函数

• 找到空格位置，依次用1——9去尝试
• 尝试一个数值时，进入下一个空格位置。
• 当空格无法进行填充时，倒退上一步更改尝试数字（可能连续倒退）

bool Backtrack(int i,int j)
{
	if(i == SIZE ){//行数为9时，推出递归
	    return true;
	}
	int Next_i,Next_j;
	if(Board[i][j]==0){
	    int k;
	    for(k=1;k<10;k++){//1——9循环尝试
	        if(IsConform(i,j,k)){//判断k是否符合游戏规则
	            Board[i][j]=k;
	            if(j<8){//进入下一个位置
	                Next_i=i;
	                Next_j=j+1;
	            }else{
	                Next_i=i+1;
	                Next_j=0;
	            }
	            if(Backtrack(Next_i,Next_j)){
	                return true;
	            }else{//下一个位置尝试失败时，要从上一步更改尝试值
	                Board[i][j]=0;
	            }
	        }
	    }
	}else{
	    if(j<8){
	        Next_i=i;
	        Next_j=j+1;
	    }else{
	        Next_i=i+1;
	        Next_j=0;
	    }
	    if(Backtrack(Next_i,Next_j)){
	        return true;
	    }else{
	        return false;
	    }
	}
	return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

IsConform函数

说明：判断尝试值k是否符合游戏规则

bool IsConform(int i,int j,int k)
{
	int u,v;
	for(u=0;u<SIZE;u++){
	    if(Board[i][u]==k||Board[u][j]==k){
	        return false;
	    }
	}
	for(u=i/3*3;u<i/3*3+3;u++){
	    for(v=j/3*3;v<j/3*3+3;v++){
	        if(Board[u][v]==k){
	            return false;
	        }
	    }
	}
	return true;
}		
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16