题目描述
“数独”是当下炙手可热的智力游戏。一般认为它的起源是“拉丁方块”，是大数学家欧拉于1783年发明的。
如图[1.jpg]所示：6×6的小格被分为6个部分（图中用不同的颜色区分）,每个部分含有6个小格（以下也称为分组）。
开始的时候，某些小格中已经填写了字母（ABCDEF之一）。需要在所有剩下的小格中补填字母。
全部填好后，必须满足如下约束：
1. 所填字母只允许是A,B,C,D,E,F 中的某一个。
2. 每行的6个小格中，所填写的字母不能重复。
3. 每列的6个小格中，所填写的字母不能重复。
4. 每个分组（参见图中不同颜色表示）包含的6个小格中，所填写的字母不能重复。
为了表示上的方便，我们用下面的6阶方阵来表示图[1.jpg]对应的分组情况（组号为0~5）：
000011
022013
221113
243333
244455
445555
用下面的数据表示其已有字母的填写情况：
02C
03B
05A
20D
35E
53F
很明显，第一列表示行号，第二列表示列号，第三列表示填写的字母。行号、列号都从0开始计算。
一种可行的填写方案（此题刚好答案唯一）为：
E F C B D A
A C E D F B
D A B E C F
F B D C A E
B D F A E C
C E A F B D
你的任务是：编写程序，对一般的拉丁方块问题求解，如果多解，要求找到所有解。
输入
用户首先输入6行数据，表示拉丁方块的分组情况。
接着用户输入一个整数n (n<36), 表示接下来的数据行数
接着输入n行数据，每行表示一个预先填写的字母。
输出
输出所有可能的解（各个解间的顺序不重要）。
每个解占用7行。
即，先输出一个整数，表示该解的序号（从1开始），接着输出一个6×6的字母方阵，表示该解。
解的字母之间用空格分开。
如果找不到任何满足条件的解，则输出“无解”
样例输入
000011
022013
221113
243333
244455
445555
6
02C
03B
05A
20D
35E
53F
样例输出
1
E F C B D A
A C E D F B
D A B E C F
F B D C A E
B D F A E C
C E A F B D
参考代码
#include<stdio.h>
#include<string.h>
int a[10][10];
char b[6][6];
int k=0,kj=0;
void f(int n)
{
int x,y;
int i,j;
if(n==36-k+1)
{
kj++;
printf("%dn",kj);
for(i=0;i<6;i++){
for(j=0;j<6;j++){
if(j!=5)printf("%c ",b[i][j]);
else printf("%cn",b[i][j]);
}
}
}
int f2=0;
for(i=0;i<6;i++){
for(j=0;j<6;j++)
if(!b[i][j]){
x=i,y=j;
f2=1;
break;
}
if(f2)break;
}
int d[6];
memset(d,0,sizeof(d));
for(i=0;i<6;i++)
if(b[x][i])
d[b[x][i]-'A']=1;
for(i=0;i<6;i++)
if(b[i][y])
d[b[i][y]-'A']=1;
for(i=0;i<6;i++)
for(j=0;j<6;j++){
if(a[i][j]==a[x][y]){
if(b[i][j])
d[b[i][j]-'A']=1;
}
}
for(i=0;i<6;i++){
if(!d[i]){
b[x][y]=i+'A';
f(n+1);
b[x][y]=0;
}
}
}
int main(){
// freopen("f.txt","r",stdin);
int i,j;
memset(b,0,sizeof(b));
for(i=0;i<6;i++)
{for(j=0;j<6;j++){
char c1;
scanf("%c",&c1);
a[i][j]=c1-'0';
}
getchar();
}
int n;
scanf("%d ",&n);
k=n;
while(n--){
char x,y,c;
scanf("%c%c%c ",&x,&y,&c);
b[x-'0'][y-'0']=c;
}
f(1);
if(kj==0)printf("æ 解");
}
解析
暂无
