算法分析

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

#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;
}