若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。


  • 运维

  • 前端

  • 编程

  • 随笔

  • hust-oj

1318: 拉丁方块填数字

发表于 2017-10-06   |   分类于 HUSTOJ   |   阅读次数 1,316

题目描述

“数独”是当下炙手可热的智力游戏。一般认为它的起源是“拉丁方块”,是大数学家欧拉于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("无解");
}

解析

暂无

hustoj

发表评论 取消回复

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

*
*


hoxis wechat
著作权归作者所有
站点更新说明
  • 文章目录
  • 站点概览
若是凉夜已成梦

若是凉夜已成梦

青春里 总有些事情要努力去做 总有些梦想要拼命去追。

1904 日志
6 分类
12 标签
RSS
weibo github twitter facebook

友情链接

Dreams孤独患者 原站点 Skip
© 2017 若是凉夜已成梦
Powered by WordPress | 已运行
Theme By NexT.Mist