数独

这个因为要进行试探某一位置是否可填,所以就是dfs,主要麻烦在某个数是否被使用.这里我们开3个布尔数组进行是否可填

h[N][N]:第i行的j是否被填过 l[N][N]:第i列的j是否被填过 x[N][N]:第i个小方格中是否填过j

#include<iostream>
#define x first
#define y second
using namespace std;
const int N=10;
int a[N][N];
bool h[N][N],l[N][N],b[N][N];
int xiao[N][N]={
	{0,0,0,0,0,0,0,0,0,0},
    {0,1,1,1,2,2,2,3,3,3},
    {0,1,1,1,2,2,2,3,3,3},
    {0,1,1,1,2,2,2,3,3,3},
    {0,4,4,4,5,5,5,6,6,6},
    {0,4,4,4,5,5,5,6,6,6},
    {0,4,4,4,5,5,5,6,6,6},
    {0,7,7,7,8,8,8,9,9,9},
    {0,7,7,7,8,8,8,9,9,9},
    {0,7,7,7,8,8,8,9,9,9},
};
pair<int,int>kong[N*N];
void print()
{
	for(int i=1;i<N;i++)
    {
    	for(int j=1;j<N;j++)
        	cout<<a[i][j]<<' ';
        cout<<endl;
    }
    cout<<endl;
    return ;
}
int cnt;
void dfs(int depth)//这里表示处理到了第depth,并没有处理完,所以终止条件时depth>cnt
{
	if(depth>cnt)
    {
    	print();
        return ;
    }
    int dx=kong[depth].x;
    int dy=kong[depth].y;
    for(int i=1;i<N;i++)
    {
        if(!h[dx][i]&&!l[dy][i]&&!b[xiao[dx][dy]][i])
        {
        	h[dx][i]=l[dy][i]=b[xiao[dx][dy]][i]=true;
            a[dx][dy]=i;
            dfs(depth+1);
            h[dx][i]=l[dy][i]=b[xiao[dx][dy]][i]=false;
        }
    }
}
int main()
{
	for(int i=1;i<N;i++)
    {
    	for(int j=1;j<N;j++)
        {
        	cin>>a[i][j];
            if(!a[i][j])
            {
            	kong[++cnt].x=i;
                kong[cnt].y=j;
            }
            else
            {
            	h[i][a[i][j]]=true;
                l[j][a[i][j]]=true;
                b[xiao[i][j]][a[i][j]]=true;
            }
        }
    }
    dfs(1);
    return 0;
}