Sudoku Killer——————DFS搜索的使用

深碍√TFBOYSˉ_ 2023-06-14 04:29 9阅读 0赞

最近找到了一个好玩的题，以后解数独就太简单了。  
**题目描述：**  
数独游戏的规则只这样的：在一个9 \* 9的方格中，需要把数字1~ 9填写到空格当中，并且使方格的每一行和每一列中都包含1~ 9这9个数字。同时还要保证，空格中用粗线划分成9个3 \* 3的方格也同时包含1~9这9个数字。输入的是9 \* 9的方格，不确定的地方给出问号。输出是一个9\*9的可行解。

**输入样例**  
7 1 2 ? 6 ? 3 5 8  
? 6 5 2 ? 7 1 ? 4  
? ? 8 5 1 3 6 7 2  
9 2 4 ? 5 6 ? 3 7  
5 ? 6 ? ? ? 2 4 1  
1 ? 3 7 2 ? 9 ? 5  
? ? 1 9 7 5 4 8 6  
6 ? 7 8 3 ? 5 1 9  
8 5 9 ? 4 ? ? 2 3

**输出样例**  
7 1 2 4 6 9 3 5 8  
3 6 5 2 8 7 1 9 4  
4 9 8 5 1 3 6 7 2  
9 2 4 1 5 6 8 3 7  
5 7 6 3 9 8 2 4 1  
1 8 3 7 2 4 9 6 5  
2 3 1 9 7 5 4 8 6  
6 4 7 8 3 2 5 1 9  
8 5 9 6 4 1 7 2 3

**题目解析**  
此题是熟悉的数独游戏，要求把数度矩阵中的问号填好。可以通过每一行已知的信息来枚举问号代表的数字，如果遇到无法继续枚举的情况就返回，此时使用DFS来解决问题是再好不过了。搜索的时候也很简单，只要有一个格子还没有填写上，就按照顺序尝试所有的数字，填写之后再去尝试下一个格子，直到找到答案为止。

**参考代码**

#include<cstdio>
    #include<iostream>
    using namespace std;
    
    int map[9][9];
    int num, ok;
    
    struct node
    { 
    	int x, y;
    }q[81];
    
    bool check(int k, int cur)
    { 
    	for(int i=0; i < 9; i++)
    	{ 
    		if(map[q[cur].x][i] == k || map[i][q[cur].y] == k)	return 0;
    	}
    	int x = q[cur].x / 3 * 3;
    	int y = q[cur].y / 3 * 3;
    	for(int i = 0; i < 3; i++)
    		for(int j = 0; j<3; j++)
    			if(map[x+i][y+j] == k)
    				return 0;
    				
    	return 1;		
    }
    
    void DFS(int cur)
    { 
    	if(cur == num)
    	{ 
    		for(int i = 0; i < 9; i++)
    		{ 
    				for(int j = 0; j < 8; j++)
    				printf("%d ", map[i][j]);
    			printf("%d\n", map[i][8]);
    		}
    		
    		ok = 1;
    	    return;	
    	}
    	else
    	{ 
    		for(int i = 1; i <= 9; i++)
    		{ 
    			if(check(i, cur) && !ok)
    			{ 
    				map[q[cur].x][q[cur].y] = i;  //填表
    				DFS(cur+1);  //递归 
    				map[q[cur].x][q[cur].y] = 0;//回溯 
    			}
    		}
    		return; 
    	}
    }
    
    int main(void)
    { 
    	char s;
    	int cas = 0;
    	while(cin>>s)
    	{ 
    		num = 0;
    		if(s=='?') 	map[0][0] = 0;
    		else	map[0][0] = s - '0';
    		
    		for(int i = 0; i < 9; i++)
    			for(int j = 0; j < 9; j++)
    			{ 
    				if(!(i==0 && j==0))		cin>>s;
    				if(s == '?')
    				{ 
    					map[i][j] = 0;
    					q[num].x = i;
    					q[num].y = j;
    					num++;
    				}
    				else
    					map[i][j] = s-'0';
    			}
    			ok = 0;
    			if(cas++)
    				printf("\n");
    	DFS(0);			
    	}
    	
    	
    	return 0;
     }