拉丁方块填数字

拉丁方块填数字

时间: 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("无解");
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注