2012蓝桥杯决赛最后一题解法.doc

2012蓝桥杯决赛最后一题解法【编程题】(满分33分)“数独”是当下炙手可热的智力游戏。一般认为它的起源是“拉丁方块”,是大数学家欧拉于1783年发明的。如图[]所示:6x6的小格被分为6个部分(图中用不同的颜色区分),每个部分含有6个小格(以下也称为分组)。开始的时候,某些小格中已经填写了字母(ABCDEF之一)。需要在所有剩下的小格中补填字母。全部填好后,必须满足如下约束:,B,C,D,E,F中的某一个。,所填写的字母不能重复。,所填写的字母不能重复。(参见图中不同颜色表示)包含的6个小格中,所填写的字母不能重复。为了表示上的方便,我们用下面的6阶方阵来表示图[]对应的分组情况(组号为0~5):000011022013221113243333244455445555用下面的数据表示其已有字母的填写情况:02C03B05A20D35E53F很明显,第一列表示行号,第二列表示列号,第三列表示填写的字母。行号、列号都从0开始计算。一种可行的填写方案(此题刚好答案唯一)为:EAFBD你的任务是:编写程序,对一般的拉丁方块问题求解,如果多解,要求找到所有解。【输入、输出格式要求】用户首先输入6行数据,表示拉丁方块的分组情况。接着用户输入一个整数n(n<36),表示接下来的数据行数接着输入n行数据,每行表示一个预先填写的字母。程序则输出所有可能的解(各个解间的顺序不重要)。每个解占用7行。即,先输出一个整数,表示该解的序号(从1开始),接着输出一个6x6的字母方阵,表示该解。解的字母之间用空格分开。如果找不到任何满足条件的解,则输出“无解”例如:用户输入:000011022013221113243333244455445555602C03B05A20D35E53F则程序输出:EAFBD再如,用户输入:001111002113022243022443544433555553704B05A13D14C24E50C51A则程序输出:1DCEFBAEFADCBABFCEDBEDAFCFDCBAECABEDF2DCEFBAEFADCBADFBECBECAFDFBDCAECABEDF3DCFEBAAEBDCFFDACEBBFEADCEBCFADCADBFE4DCFEBABEADCFADCFEBFBEADCEFBCADCADBFE5DCFEBAEFADCBABCFEDBEDAFCFDBCAECAEBDF6DCFEBAEFADCBABDFECBECAFDFDBCAECAEBDF7DCFEBAEFADCBADBFECBECAFDFBDCAECAEBDF8DCFEBAFEADCBADBCEFBFEADCEBCFADCADBFE9DCFEBAFEADCBAFCBEDBDEAFCEBDCAFCABFDE【注意】请仔细调试!您的程序只有能运行出正确结果的时候才有机会得分!在评卷时使用的输入数据与试卷中给出的实例数据可能是不同的。请把所有函数写在同一个文件中,调试好后,拷贝到【考生文件夹】下对应题号的“”中即可。相关的工程文件不要拷入。源代码中不能使用诸如绘图、Win32API、中断调用、硬件操作或与操作系统相关的API。允许使用STL类库,但不能使用MFC或ATL等非ANSIc++标准的类库。例如,不能使用CString类型(属于MFC类库);例如,不能使用randomize,random函数(不属于ANSIC++标准)解题思路:深度搜索(DFS),注意边界的控制。源代码如下:#include<>#include<>intq=0;chars[8][8],h[8][8];intfff(inta,intb,intc)