题意

给出一个未解的数独谜题，解这个数独。

解答

这是一道搜索的基础题，我们用深度优先搜索解决它。 代码如下：

#include <bits/stdc++.h>
using namespace std;
int sd[11][11];//数独方阵定义 
bool p[11][11],l[11][11],fz[11][11];//行，列与方阵是否满足数独条件
void _init()
{
    	for(int i=1;i<=9;i++)
		for(int j=1;j<=9;j++)
		{
			int t;
			cin>>t;
			if(t!=0)
				p[i][t]=l[j][t]=fz[(i-1)/3*3+(j-1)/3+1][t]=true;
			//填充的不是0的话，表示原来有数字了。打上标记。
			sd[i][j]=t;//将数字填充进数独
		}	
}
void _out()
{
	for(int i=1;i<=9;i++)
	{	
  		for(int j=1;j<=9;j++)
			cout<<sd[i][j]<<" ";
		puts("");
	}
	exit(0);
}
void dfs(int x,int y)
{
	if(sd[x][y]!=0)//如果原来这个位置有数字，跳过。
		if(x==9&&y==9)_out();//当行列都为9，填充完成，输出
		else if(y==9)dfs(x+1,1);//当列数为9，搜索下一排。
		else dfs(x,y+1);//搜下一列
	else//原来的地方没有数字，进行搜索
		for(int i=1;i<=9;i++)
			if((!p[x][i])&&(!l[y][i])&&(!fz[(x-1)/3*3+(y-1)/3+1][i]))
			{
				sd[x][y]=i;//填充
				p[x][i]=l[y][i]=fz[(x-1)/3*3+(y-1)/3+1][i]=true;//打上标记。
				if(x==9&&y==9)_out();
				else if(y==9)dfs(x+1,1);//搜下一行。
				else dfs(x,y+1);//搜下一列。
				sd[x][y]=0; //恢复标记。
				p[x][i]=l[y][i]=fz[(x-1)/3*3+(y-1)/3+1][i]=false;//恢复标记。
			}
}
int main()
{
    _init();//输入
    dfs(1,1);//深度优先搜索
    return 0;
}

我们用样例来解释程序是如何运作的。

输入这个样例，首先我们搜索(1,1)位置，发现这里原来的数字是0，可以填充，于是我们遍历第一行，第一列与第一个3×3方格，发现只有5未被填入，我们填入5，并在这一行这一列与这一方格打上5已被填入的标记，继续搜索下一格，发现接下来的格都是已经填过数字的，直到最后一行第一格，我们再次遍历，发现只能填入9，直到遍历完成之后输出结果。

时间复杂度:$O(1)O(1)$，数独为9×9，可以认为只花费常数时间。 空间复杂度:$O(1)O(1)$，只消耗存储数独的空间以及常数级别的栈空间。