B. 【例题2】数独游戏

在这里插入图片描述

题解

经过不断地debug，终于用自己的方法做出这题了。

我的方法跟书上的不同，自认为更简单些。

用三个二维数组分别记录每一行、列、宫中是否出现1~9，即判重，来进行剪枝。

dfs每个输入时就储存下来的空着的格子，枚举1~9并根据判重数组判断能否填入该数字。

填完所有空格后，输出并直接退出，最后别忘了初始化那三个判重数组，因为有多组数据。

若点

（ x, y ）

的数为

t

，三个判重的数组可以这样写：

fx[x][t]=1;//行fy[y][t]=1;//列fg[(x-1)/3*3+(y-1)/3+1][t]=1;//宫

对于宫判重，我们将宫编号：

套用我想出的小公式：

(x - 1) / 3 * 3 + (y - 1) / 3 + 1

（证明略）就可求出每个点属于的宫。

代码

#include
   
    #include
    
     #include
     
      using namespace std;int a[100][100],b[100][2],c[100],fx[10][10],fy[10][10],fg[10][10],n;string s;bool check(int x,int y,int t)//判断是否可填该数{
   	if(fx[x][t]||fy[y][t]||fg[(x-1)/3*3+(y-1)/3+1][t]) return false;	else //无重复，即可填，判重数组标记为一	{
   		fx[x][t]=1;		fy[y][t]=1;		fg[(x-1)/3*3+(y-1)/3+1][t]=1;		return true;	}}void back(int x,int y,int t)//回溯，还原信息{
   	fx[x][t]=0;	fy[y][t]=0;	fg[(x-1)/3*3+(y-1)/3+1][t]=0;}bool dfs(int dep){
   	if(dep>n)	{
   		n=0;		for(int i=1; i<=9; i++)		{
   			for(int j=1; j<=9; j++)			{
   				if(a[i][j]) cout<