Description 一个n*n的数独，每一行每一列数字都不同，一个数组表示该位置放这么高的塔，已经填好一些数字并且给出一些限制，如某一行左边的限制为从左边看这一行能看到多少塔，上下左右都可能有类似的限制，问是否存在一个合法的数独满足这些条件，如果有则输出一组合法解，否则输出no Input 第一行一整数T表示用例组数，每组用例首先输入一整数n表示数独大小，然后是一个(n+2)*(n+2)的矩阵，第一行和最后一列分别表示上面和下面的限制，第一列和最后一列分别表示左边和右边的限制，-表示没有限制，中间的n*n矩阵表示数独初始状态，-表示没填数(3<=n<=5) Output 如果存在一个合法的数独满足这些条件则输出一组合法解，否则输出no Sample Input Sample Output Solution 暴力dfs，dfs的时候先不管四周的限制，只根据数独的限制去放数，等所有数字都放完再判断其是否满足周围的限制 Code
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> #include<cmath> #include<vector> #include<queue> #include<map> #include<set> #include<ctime> using namespace std; typedef long long ll; #define INF 0x3f3f3f3f #define maxn 7 int T,n,flag,mark[maxn],a[maxn][maxn]; char s[maxn][maxn]; bool check1() { for(int i=1;i<=n;i++) { memset(mark,0,sizeof(mark)); for(int j=1;j<=n;j++) if(a[i][j]) { if(mark[a[i][j]])return 0; mark[a[i][j]]=1; } } for(int j=1;j<=n;j++) { memset(mark,0,sizeof(mark)); for(int i=1;i<=n;i++) if(a[i][j]) { if(mark[a[i][j]])return 0; mark[a[i][j]]=1; } } return 1; } bool check2() { for(int i=1;i<=n;i++) { int temp,num; if(s[i][0]!='-') { temp=num=0; for(int j=1;j<=n;j++) if(a[i][j]>temp)temp=a[i][j],num++; if(num!=s[i][0]-'0')return 0; } if(s[i][n+1]!='-') { temp=num=0; for(int j=n;j>=1;j--) if(a[i][j]>temp)temp=a[i][j],num++; if(num!=s[i][n+1]-'0')return 0; } } for(int j=1;j<=n;j++) { int temp,num; if(s[0][j]!='-') { temp=num=0; for(int i=1;i<=n;i++) if(a[i][j]>temp)temp=a[i][j],num++; if(num!=s[0][j]-'0')return 0; } if(s[n+1][j]!='-') { temp=0,num=0; for(int i=n;i>=1;i--) if(a[i][j]>temp)temp=a[i][j],num++; if(num!=s[n+1][j]-'0')return 0; } } return 1; } int dfs(int x,int y) { if(flag)return 1; if(y==n+1)x++,y=1; if(x==n+1) { if(check2()==1) { flag=1; return 1; } return 0; } if(a[x][y])return dfs(x,y+1); int gg=1; for(int i=1;i<=n;i++) { a[x][y]=i; if(check1()) { if(dfs(x,y+1)) { gg=0; flag=1; return 1; } } a[x][y]=0; } if(gg)return 0; } int main() { scanf("%d",&T); while(T--) { scanf("%d",&n); for(int i=0;i<=n+1;i++)scanf("%s",s[i]); memset(a,0,sizeof(a)); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(s[i][j]>='0'&&s[i][j]<='9') a[i][j]=s[i][j]-'0'; flag=0; dfs(1,1); if(flag) { for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++)printf("%d",a[i][j]); printf("\n"); } } else printf("no\n"); printf("\n"); } return 0; }