【HDU 1426】Sudoku Killer 深搜DFS

题目地址

数独游戏，每一行、每一列包括每个小的九宫格中的数字都不能重复。

我的方法是用二维数组储存矩阵，“？”用0代替。

然后记录每一行，每一列和每个九宫格中出现过的数字，利用数组的桶结构储存起来。可以快速查询当前位置的行列阵是否包含某个数字。

由于每个空白位置可以填写的数字可能有多个，因此深搜部分利用回溯原理，对每种填写方式都进行查找，若不符合则回溯为0；

注意输出格式，多组样例，并且从第二组数据开始要先输出空白行。

其中九宫格的处理比较麻烦，贴张图表示九宫格的储存顺序：

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

int map[11][11],cnt;
int a[11][11],b[11][11],c[11][11];	// 阵 行 列 

struct ac
{
	int x,y;
}q[100];                            //记录空白位置

int aa(int n,int m)                 //返回当前位置所处九宫格位置
{
	if(n<=3)
	{
		if(m<=3)
			return 1;
		else if(m<=6)
			return 4;
		else return 7;
	}
	else if(n<=6)
	{
		if(m<=3)
			return 2;
		else if(m<=6)
			return 5;
		else return 8;
	}
	else
	{
		if(m<=3)
			return 3;
		else if(m<=6)
			return 6;
		else return 9;
	}
}

void dfs(int s)
{
	if(s==cnt)
	{
		for(int i=1;i<=9;i++)
		{
			for(int j=1;j<=9;j++)
			{
				if(j!=1)
					cout<<" ";
				cout<<map[i][j];
			}
			cout<<endl;
		}
		return ;
	}
	else
	{
		int n=q[s].x,m=q[s].y,t=aa(n,m);
		for(int i=1;i<=9;i++)
		{
			if(a[t][i]==0&&b[n][i]==0&&c[m][i]==0)
			{
				a[t][i]=1;
				b[n][i]=1;
				c[m][i]=1;
				map[n][m]=i;
				dfs(s+1);
				a[t][i]=0;
				b[n][i]=0;
				c[m][i]=0;
				map[n][m]=0;
			}
		}
	}
	
}

int main()
{
	int i,j,k,l,x,y,cas=0;
	char str;
	while(cin>>str)
	{
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		memset(c,0,sizeof(c));
		cnt=0;
		if(str=='?')
		{
			map[1][1]=0;
			q[cnt].x=1;
			q[cnt++].y=1;
		}
		else
			map[1][1]=str-'0';
		for(i=2;i<=9;i++)
		{
			cin>>str;
			if(str=='?')
			{
				map[1][i]=0;
				q[cnt].x=1;
				q[cnt++].y=i;
			}
			else
				map[1][i]=str-'0';
		}
		for(i=2;i<=9;i++)
		{
			for(j=1;j<=9;j++)
			{
				cin>>str;
				if(str=='?')
				{
					map[i][j]=0;
					q[cnt].x=i;
					q[cnt++].y=j;
				}	
				else
					map[i][j]=str-'0';
			}
		}
		for(i=1;i<=9;i++)				//阵 
		{
			if(i==1||i==4||i==7)
				x=1;
			else if(i==2||i==5||i==8)
				x=4;
			else
				x=7; 
			if(i==1||i==2||i==3)
				y=1;
			else if(i==4||i==5||i==6)
				y=4;
			else
				y=7;
			for(j=0;j<3;j++)
			{
				for(k=0;k<3;k++) 
				{
					l=map[x+j][y+k];
					a[i][l]=1;
				}	
			}
		}
		for(i=1;i<=9;i++)				//行 
		{
			for(j=1;j<=9;j++)
			{
				l=map[i][j];
				b[i][l]=1;
			}
		}
		for(i=1;i<=9;i++)				//列 
		{
			for(j=1;j<=9;j++)
			{
				l=map[j][i];
				c[i][l]=1;
			}
		}
		if(cas++)
			cout<<endl;
		dfs(0);
	}
	return 0;
}