拉丁方块填数字
时间： 1ms 内存：128M
描述：
“数独”是当下炙手可热的智力游戏。一般认为它的起源是“拉丁方块”，是大数学家欧拉于1783年发明的。
如图[1.jpg]所示：6x6的小格被分为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开始），接着输出一个6x6的字母方阵，表示该解。
解的字母之间用空格分开。
如果找不到任何满足条件的解，则输出“无解”
示例输入：
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提示：
参考答案（内存最优[1092]）：
#include<cstdio>
int a[7][8];//初始时特殊区域分布
int vis[7][8];//特殊区域记录
int hi[7][8];//行记录
int hj[7][8];//列记录
int map[7][8];
int n;
int sum;
void print()
{
for(int i=0;i<6;i++)
{
for(int j=0;j<6;j++)
printf("%c ",map[i][j]+'A'-1);
printf("\n");
}
}
void dfs(int now)
{
if(now==36)//当全部填完时
{
printf("%d\n",++sum);
print();
return;
}
for(int i=0;i<6;i++)
{
for(int j=0;j<6;j++)
{
if(map[i][j]==0)
{
for(int k=1;k<=6;k++)
{
if(hi[i][k]==1||hj[j][k]==1||vis[a[i][j]][k]==1)
continue;
hi[i][k]=1;
hj[j][k]=1;
vis[a[i][j]][k]=1;
map[i][j]=k;
dfs(now+1);
hi[i][k]=0;
hj[j][k]=0;
vis[a[i][j]][k]=0;
map[i][j]=0;
}
return;
}
}
}
}
int main()
{
int x,y;
char str;
for(int i=0;i<6;i++)
{
for(int j=0;j<6;j++)
scanf("%1d",&a[i][j]);
}
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%1d%1d%c",&x,&y,&str);
int k=str-'A'+1;
vis[a[x][y]][k]=1;//将行列和特殊区域的字母设为已用
hi[x][k]=1;
hj[y][k]=1;
map[x][y]=k;
}
dfs(n);//当前已经填完的方格数量
if(sum==0)
printf("无解");
return 0;
}参考答案（时间最优[0]）：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
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("%d\n",kj);
for(i=0;i<6;i++){
for(j=0;j<6;j++){
if(j!=5)printf("%c ",b[i][j]);
else printf("%c\n",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((int)b[x][i])
d[(int)b[x][i]-'A']=1;
for(i=0;i<6;i++)
if((int)b[i][y])
d[(int)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((int)b[i][j])
d[(int)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("无解");
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。