蓝桥杯C本科组决赛第5题-方块填数 - sbw Blog

蓝桥杯C本科组决赛第5题-方块填数

来源: 石博文博客 | 浏览: 6502 | 评论: 0 发表时间: 2013-03-23

“数独”是当下炙手可热的智力游戏。一般认为它的起源是“拉丁方块”,是大数学家欧拉于1783年发明的。6x6的小格被分为6个部分(图中用不同的颜色区分),每个部分含有6个小格(以下也称为分组)。开始的时候,某些小格中已经填写了字母(ABCDEF之一)。需要在所有剩下的小格中补填字母。本文给出了此题的C++语言解法。



如图所示:6x6的小格被分为6个部分(图中用不同的颜色区分),每个部分含有6个小格(以下也称为分组)。

初始方块

开始的时候,某些小格中已经填写了字母(ABCDEF之一)。需要在所有剩下的小格中补填字母。

全部填好后,必须满足如下约束:

1. 所填字母只允许是A,B,C,D,E,F 中的某一个。

2. 每行的6个小格中,所填写的字母不能重复。

3. 每列的6个小格中,所填写的字母不能重复。

4. 每个分组(参见图中不同颜色表示)包含的6个小格中,所填写的字母不能重复。


为了表示上的方便,我们用下面的6阶方阵来表示图对应的分组情况(组号为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

你的任务是:编写程序,对一般的拉丁方块问题求解,如果多解,要求找到所有解。如果找不到任何满足条件的解,则输出“无解”


C++ 解法示例



没有人评论过此文,还不快抢个沙发
  • 昵称: *
  • 邮箱:
  • 网址:
  • 记住我的信息
  • Color
  • Red
  • Blue
  • Code
  • bash
  • cpp
  • css
  • java
  • js
  • perl
  • php
  • python
  • ruby
  • sql
  • xml