数独挑战

巧妙的三招

1.读入数据的时候直接记录第cnt个需要填充的数组元素的x、y坐标 space结构体元素

2.用已经填充了多少个数字dep，作为dfs搜索深度.

struct ty {
	int x, y;
}space[90];
int mp[12][12];

//判断第i行，是否存在已经有数字j了
int h[12][12], l[12][12], gogn[12][12];
int cnt = 0;


//打表，用以判断坐标x，y的点是在第几个九宫格里面，

const int g[10][10] = { {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}, };
void print() {
	for ( int i = 1; i < 10; i++ ) {
		for ( int j = 1; j < 10; j++ ) {
			cout << mp[i][j];
			if ( j == 9 )cout << '\n';
			else cout << " ";
		}
	}
}
void dfs(int dep) {
	if ( dep > cnt )
	{
		print();
		return;
	}
	for ( int i = 1; i < 10; i++ )
	{
// 		if ( !h[space[dep].x][i] && !l[space[dep].y][i] && !gogn[g[space[dep].x][space[dep].y]][i])
// 		{
// 			h[space[dep].x][i] = 1;
// 			l[space[dep].y][i] = 1;
// 			gogn[g[space[dep].x][space[dep].y]][i] = 1;
// 			mp[space[dep].x][space[dep].y] = i;
// 			dfs(dep + 1);	
// 			h[space[dep].x][i] = 0;
// 			l[space[dep].y][i] = 0;
// 			gogn[g[space[dep].x][space[dep].y]][i] = 0;
// 		}
         int xx=space[dep].x,yy=space[dep].y;
         if(h[xx][i]==0&&l[yy][i]==0&&gogn[g[xx][yy]][i]==0){
                h[xx][i]=1;
                l[yy][i]=1;
                gogn[g[xx][yy]][i]=1;
                mp[xx][yy]=i;
                dfs(dep+1);
                h[xx][i]=0;
                l[yy][i]=0;
                gogn[g[xx][yy]][i]=0;
                mp[xx][yy]=0;
            }        
	}
}
int main(int arg, char** argv) {
// 	ios::sync_with_stdio(false);
// 	cin.tie(nullptr);
// 	cin.tie(nullptr);
	for ( int i = 1; i <10; i++ )
	{
		for ( int j = 1; j < 10; j++ )
		{
			cin >> mp[i][j];
			if ( mp[i][j] == 0 )
			{
				space[++cnt].x = i;
				space[cnt].y = j;
			}else{
                h[i][mp[i][j]]=1;
                l[j][mp[i][j]]=1;
                gogn[g[i][j]][mp[i][j]]=1; 
            }
		}
	}
	dfs(1);
	return 0;
}