新数独
下面是一个没有数字，只有大小关系（没错！那些尖角都是“大于”符号！）的数独：
除了大小关系外（注意相邻格子不能相同），还需要满足通常的数独规则：
l 每个格子都是1~9 的数字
l 每行都是1~9的排列
l 每列都是1~9的排列
l 每个3*3的子矩阵（上图中用粗线隔开，一共有3*3个这样的子矩阵）都是1~9的排列
为了美观，每个3*3子矩阵的所有12对相邻格子的大小关系都将给出。
【输入格式】
输入一共15行，包含一个新数独的实例。第奇数行包含左右方向的符号（<和>），第偶数行包含上下方向的符号（^和v）。
【输出格式】
输出包含9行，每行9个1~9的数字，以单个空格隔开。输入保证解惟一。
【输入输出样例】
> < < < > < v ^ v v ^ v ^ ^ v < < < > < < v ^ v ^ v v ^ ^ v < < < < > > < > > > < > v v ^ ^ v ^ ^ v v < > > < > > ^ v v v ^ v v ^ v > < < > > > < > > > > < v v v v ^ ^ ^ ^ ^ > < < < < < ^ ^ ^ ^ ^ v v v ^ > > < > < < 5 3 9 4 6 8 2 1 7 2 4 8 1 9 7 3 5 6 1 6 7 2 3 5 9 8 4 6 8 1 7 4 2 5 9 3 3 7 5 9 1 6 8 4 2 9 2 4 5 8 3 7 6 1 7 9 6 8 2 1 4 3 5 4 1 2 3 5 9 6 7 8 8 5 3 6 7 4 1 2 9 考试拿到这个题不敢写啊，没想到直接搜都能得到满分。。。（无力吐槽） #include<iostream> #include<cstring> #include<algorithm> #include<cstdlib> #include<cstdio> using namespace std; const int INF=0x3f3f3f3f; const int MAXN=110; struct Node{ int v; int Flag; Node *Next; }; Node *adj[MAXN*10]; Node edge[MAXN*MAXN]; Node *Cnt1=&edge[0]; void addedge( int u, int v, int Flag){ Node *p=++Cnt1; p->v=v; p->Flag=Flag;p->Next=adj[u]; adj[u]=p; } int High[MAXN*10],Low[MAXN*10]; inline int Get_Pos( int x, int y){ return (x-1)*9+y; } int Ans[MAXN*MAXN],visc[MAXN],visr[MAXN],visk[MAXN]; inline int Get_c( int x, int y){ return y; } inline int Get_r( int x, int y){ return x; } inline int Get_k( int x, int y){ return (x%3==0?x/3-1:x/3)*3+(y%3==0?y/3:y/3+1); } void DFS( int x, int y){ if (x>9){ for ( int i=1;i<=9;++i){ for ( int j=1;j<=8;++j) printf ( "%d " ,Ans[Get_Pos(i,j)]); printf ( "%d\n" ,Ans[Get_Pos(i,9)]); } exit (0); } if (y>9){ DFS(x+1,1); return ; } int Pos=Get_Pos(x,y); int MaxSize=9,MinSize=1; for (Node *p=adj[Get_Pos(x,y)];p;p=p->Next){ int v=p->v,Flag=p->Flag; if (Ans[v]!=INF){ if (Flag==1){ MinSize=max(MinSize,Ans[v]+1); } else { MaxSize=min(MaxSize,Ans[v]-1); } } } for ( int a=max(MinSize,Low[Pos]);a<=min(MaxSize,High[Pos]);++a){ int c,r,k; c=Get_c(x,y); r=Get_r(x,y); k=Get_k(x,y); if ((!(1<<a&visc[c]))&&(!(1<<a&visr[r]))&&(!(1<<a&visk[k]))) { visc[c]^=(1<<a); visr[r]^=(1<<a); visk[k]^=(1<<a); Ans[Get_Pos(x,y)]=a; DFS(x,y+1); visc[c]^=(1<<a); visr[r]^=(1<<a); visk[k]^=(1<<a); Ans[Get_Pos(x,y)]=INF; } } } int main() { //freopen("sudoku4.in","r",stdin); for ( int i=0;i<MAXN*10;++i){ High[i]=9; Low[i]=1; } memset (Ans,0x3f, sizeof (Ans)); for ( int i=0;i<3;++i){ //分块 char ch; for ( int j=0;j<3;++j) for ( int k=1;k<=2;++k){ do {ch= getchar ();} while (ch!= '>' &&ch!= '<' ); if (ch== '>' ){ Low[i*27+j*3+k]++; High[i*27+j*3+k+1]--; addedge(i*27+j*3+k,i*27+j*3+k+1,1); addedge(i*27+j*3+k+1,i*27+j*3+k,0); } if (ch== '<' ){ High[i*27+j*3+k]--; Low[i*27+j*3+k+1]++; addedge(i*27+j*3+k,i*27+j*3+k+1,0); addedge(i*27+j*3+k+1,i*27+j*3+k,1); } } for ( int j=1;j<=9;++j){ do {ch= getchar ();} while (ch!= 'v' &&ch!= '^' ); if (ch== 'v' ){ Low[i*27+j]++; High[i*27+j+9]--; addedge(i*27+j,i*27+j+9,1); addedge(i*27+j+9,i*27+j,0); } if (ch== '^' ){ High[i*27+j]--; Low[i*27+j+9]++; addedge(i*27+j,i*27+j+9,0); addedge(i*27+j+9,i*27+j,1); } } for ( int j=0;j<3;++j) for ( int k=1;k<=2;++k){ do {ch= getchar ();} while (ch!= '<' &&ch!= '>' ); if (ch== '>' ){ Low[i*27+9+j*3+k]++; High[i*27+9+j*3+k+1]--; addedge(i*27+9+j*3+k,i*27+9+j*3+k+1,1); addedge(i*27+9+j*3+k+1,i*27+9+j*3+k,0); } if (ch== '<' ){ High[i*27+9+j*3+k]--; Low[i*27+9+j*3+k+1]++; addedge(i*27+9+j*3+k,i*27+9+j*3+k+1,0); addedge(i*27+9+j*3+k+1,i*27+9+j*3+k,1); } } for ( int j=1;j<=9;++j){ do {ch= getchar ();} while (ch!= 'v' &&ch!= '^' ); if (ch== 'v' ){ Low[i*27+9+j]++; High[i*27+18+j]--; addedge(i*27+9+j,i*27+18+j,1); addedge(i*27+18+j,i*27+9+j,0); } if (ch== '^' ){ High[i*27+9+j]--; Low[i*27+18+j]++; addedge(i*27+9+j,i*27+18+j,0); addedge(i*27+18+j,i*27+9+j,1); } } for ( int j=0;j<3;++j) for ( int k=1;k<=2;++k){ do {ch= getchar ();} while (ch!= '<' &&ch!= '>' ); if (ch== '>' ){ Low[i*27+18+k+j*3]++; High[i*27+18+k+1+j*3]--; addedge(i*27+18+k+j*3,i*27+18+k+1+j*3,1); addedge(i*27+18+k+j*3+1,i*27+18+k+j*3,0); } if (ch== '<' ){ High[i*27+18+k+j*3]--; Low[i*27+18+k+1+j*3]++; addedge(i*27+18+k+j*3,i*27+18+k+1+j*3,0); addedge(i*27+18+k+j*3+1,i*27+18+k+j*3,1); } } } /*for(int i=1;i<=9;++i){ for(int j=1;j<=9;++j) printf("%d ",High[Get_Pos(i,j)]); printf("\n"); } printf("\n"); for(int i=1;i<=9;++i){ for(int j=1;j<=9;++j) printf("%d ",Low[Get_Pos(i,j)]); printf("\n"); } printf("\n");*/ DFS(1,1); return 0; }转载于:https://www.cnblogs.com/Return-0/archive/2013/04/01/2994251.html
相关资源：数据结构—成绩单生成器