#include<bits/stdc++.h>
using namespace std;
const int N=10;
char g[N][N];
bool row[N][N],col[N][N],cell[3][3][N];
bool dfs(int x,int y)
{
	if(y==9)
	{
		x++,y=0;
	}
	if(x==9)
	{
		for(int i=0;i<9;i++)
		{
			cout<<g[i]<<endl;
		}
		return 1;
	}
	if(g[x][y]!='.') return dfs(x,y+1);
	for(int i=0;i<9;i++)
	{
		if(!row[x][i]&&!col[y][i]&&!cell[x/3][y/3][i]){
			g[x][y]=i+'1';
			row[x][i]=col[y][i]=cell[x/3][y/3][i]=true;
			if(dfs(x,y+1)) return true;
			row[x][i]=col[y][i]=cell[x/3][y/3][i]=false;
			g[x][y]='.';
		}
	
	}
	return false;
}
int main()
{
	for(int i=0;i<9;i++)
	{
		cin>>g[i];
		for(int j=0;j<9;j++)
		{
			if(g[i][j]!='.')
			{
				int t=g[i][j]-'1';
				row[i][t]=col[j][t]=cell[i/3][j/3][t]=true;
			}
		}
	}
	dfs(0,0);
	return 0;
}

算法分析

每一行，按照列搜索，列搜索完了，就搜索到下一行，搜索完所有行以后即找到正确的答案。

#include<bits/stdc++.h>
using namespace std;
const int N=10;
char g[N][N];
bool row[N][N],col[N][N],cell[3][3][N]; 
//row[x][i]=true表示第x行填了数i,cell[i][j][x]表示第i行第j列的小格子填了数x
bool dfs(int x,int y)
{
    if(y==9) x++,y=0; //行已经到了结尾
    if(x==9) //搜索完成
    {
        for(int i=0;i<9;i++)
        {
            cout<<g[i]<<endl;
        }
        return true;
    }
    if(g[x][y]!='.') return dfs(x,y+1); //如果已经有数，就搜索下一列
    for(int i=0;i<9;i++) //枚举当前格子需要填写的数
    {
        if(!row[x][i]&&!col[y][i]&&!cell[x/3][y/3][i])
        {
            g[x][y]=i+'1';
            row[x][i]=col[y][i]=cell[x/3][y/3][i]=true;
            if(dfs(x,y+1)) return true;
            row[x][i]=col[y][i]=cell[x/3][y/3][i]=false;
            g[x][y]='.';
        }
    }
    return false; //找不到
}
int main()
{

    for(int i=0;i<9;i++)
    {
        cin>>g[i];
        for(int j=0;j<9;j++)
        {
            if(g[i][j]!='.') //对于已经有了的数进行标记
            {
                int t=g[i][j]-'1';
                row[i][t]=col[j][t]=cell[i/3][j/3][t]=true;
            }
        }
    }

    dfs(0,0);
    return 0;
}