C语言||暴力算法解数独

比眉伴天荒 2023-02-21 14:03 13阅读 0赞

## 前言 ##

前几天在玩解数独游戏时，发现有点费时间。心血来潮想实现一个解数独的c语言程序，根据我在晚解数独游戏的思路，采用了暴力算法求解。在数组维数的选择上，我选择了用一维数组实现。

## 分析 ##

其实暴力算法求解的实际是，将求解数组的思路，整合成代码，通过代码告诉计算机，让计算机按我们的想法来工作。  
首先，9\*9数独的规则是，每行九个数各不相同，每列九个数各不相同，每个小九宫格的九个数各不相同。例如下图（图片源于网络，侵删）：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzOTIw_size_16_color_FFFFFF_t_70]  
暴力算法的实际就是，对81个小格里面待填元素逐一填值（1-9），符合则填入，九个数字都不符合则回退到上一个代填值元素，对该元素填新值，以此类推。时间复杂度是O(9^81)。下面是具体实现思路。

## 实现 ##

1，拷贝原始数独至辅助数组，通过逐渐填满辅助数组来实现数独求解。而原始数独数组的作用是实时获取到上一个待填元素的位置，以便不会将原始数据改变。

void exit(int n) { 
    	int i = n;
    	for (; i < 81; i++) { 
    		arr[i] = shudu[i]; 
    	}
    }

2，判断该值于该元素是否符合。  
对于每次尝试填入的值，判断其是否符合规则（行唯一，列唯一，小单元格唯一）。主要通过调用下面的函数实现判断。

int check(int n, int num) { //检查num能不能作为当前元素的值 
    	int hang = n / 9;//行 
    	int lie = n % 9;//列
    	//获得所在小九宫格 
    	int x = n / 9 / 3;
    	int y = n % 9 / 3;
    
    	int i , j;
    	for (i=0; i < 9; i++) { 
    		
    		if (arr[hang * 9 + i] == num && n != (hang * 9 + i)) { //检查行 
    			return 0;
    		}
    		if (arr[lie + i * 9] == num && n != (lie + i * 9)) { //检查列
    			return 0;
    		}
    
    	}
    	//检查小九宫格
    	for (i = x * 3; i < (x + 1) * 3; i++) { 
    		for (j = y * 3; j < (y + 1) * 3; j++) { 
    			if (num == arr[i * 9 + j] && n != (i * 9 + j)) { 
    				return 0;
    			}
    		}
    	}
    	return 1;
    }

3，如果该元素无论填1-9的任意值到不能满足要求，则回退。通过回退原始数组，从其原始的值得到具体回退的目标位置，获取改下标值，去查辅助数组从而获得刚刚成功的填入值，对其加1，重新判断，以此类推。下面是关键代码：

void solve() { 
    	int x = 0;
    	for (; x < 81; x++) { 
    		if (shudu[x] == 0) { 
    			int i;
    			int tellok=0;
    			if (arr[x] == 0) { 
    				i = 1;
    			}else { 
    				i = arr[x];
    			}
    			for (; i < 10; i++) { 
    				int res = check(x, i);
    				if (res) { 
    					tellok = 1;
    					arr[x] = i;
    					break;
    				}
    				
    			}
    			
    			if(tellok == 0 ){ 
    				x--;
    				while(shudu[x] != 0){ 
    					x--;
    				}
    				arr[x]++;
    				exit(x+1);
    				x--;
    			}
    			
    		}
    	}
    }

4，输出，直接输出辅助数组即可。

## 运行 ##

![在这里插入图片描述][20200701081117737.png]

## 完整源代码 ##

下面附上有完整注释的源代码，刚需下（在visual studio上写的，可以在visual studio上、虚拟机的Gcc编译器上跑）https://download.csdn.net/download/qq\_43543920/12565682

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzOTIw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200701073609927.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTQzOTIw,size_16,color_FFFFFF,t_70
[20200701081117737.png]: https://img-blog.csdnimg.cn/20200701081117737.png