本文共 3102 字,大约阅读时间需要 10 分钟。
“数独”是当下炙手可热的智力游戏。一般认为它的起源是“拉丁方块”,是大数学家欧拉于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):000011022013221113243333244455445555用下面的数据表示其已有字母的填写情况:02C03B05A20D35E53F很明显,第一列表示行号,第二列表示列号,第三列表示填写的字母。行号、列号都从0开始计算。一种可行的填写方案(此题刚好答案唯一)为:E F C B D AA C E D F BD A B E C FF B D C A EB D F A E CC E A F B D你的任务是:编写程序,对一般的拉丁方块问题求解,如果多解,要求找到所有解。【输入、输出格式要求】用户首先输入6行数据,表示拉丁方块的分组情况。接着用户输入一个整数n (n<36), 表示接下来的数据行数接着输入n行数据,每行表示一个预先填写的字母。程序则输出所有可能的解(各个解间的顺序不重要)。每个解占用7行。即,先输出一个整数,表示该解的序号(从1开始),接着输出一个6x6的字母方阵,表示该解。解的字母之间用空格分开。如果找不到任何满足条件的解,则输出“无解”例如:用户输入:000011022013221113243333244455445555602C03B05A20D35E53F则程序输出:1E F C B D AA C E D F BD A B E C FF B D C A EB D F A E CC E A F B D再如,用户输入:001111002113022243022443544433555553704B05A13D14C24E50C51A则程序输出:1D C E F B AE F A D C BA B F C E DB E D A F CF D C B A EC A B E D F2D C E F B AE F A D C BA D F B E CB E C A F DF B D C A EC A B E D F3D C F E B AA E B D C FF D A C E BB F E A D CE B C F A DC A D B F E4D C F E B AB E A D C FA D C F E BF B E A D CE F B C A DC A D B F E5D C F E B AE F A D C BA B C F E DB E D A F CF D B C A EC A E B D F6D C F E B AE F A D C BA B D F E CB E C A F DF D B C A EC A E B D F7D C F E B AE F A D C BA D B F E CB E C A F DF B D C A EC A E B D F8D C F E B AF E A D C BA D B C E FB F E A D CE B C F A DC A D B F E9D C F E B AF E A D C BA F C B E DB D E A F CE B D C A FC A B F D E
#includeusing namespace std;struct pos{ int x,y;};int color[6][6];int card[6][6];int tol = 0;vector same[6];bool check(int x, int y, int key){ //same[cls][i] i-(0..5) 得到同类的所有方块 并判断 for(int i = 0; i < 6; ++i){ int cls = color[x][y];//所属类别 if(card[i][y] == key || card[x][i] == key || card[same[cls][i].x][same[cls][i].y] == key) return false; } return true;} void output(int card[][6]) { for(int i = 0; i < 6; ++i){ for(int j = 0; j < 6; ++j){ printf("%c",card[i][j]+'A'); } printf("\n"); } }void dfs(int x, int y) { if(x > 5){ tol++; printf("%d\n",tol); output(card); printf("\n"); return; } if(card[x][y] == -1){ for(int i = 0; i <6; ++i){ if(check(x,y,i)){ card[x][y] = i; dfs(x+(y+1)/6,(y+1)%6); //当y==5时候 进入下一行第一个位置 card[x][y] = -1; } } } else{ dfs(x+(y+1)/6,(y+1)%6);//跳过这个 } }/* 这题的技巧就是 把同类的方块存储在一个一维数组里面 方便检查是否重复 记录类别 color*/int main() { int p; for(int i = 0; i < 6; ++i){ for(int j = 0; j < 6; ++j){ card[i][j] = -1; //初始化为 没有数字的情况 pos po; po.x = i; po.y = j; scanf("%d",&p); //读数据的时候如果连接在一起会被视为一个数 导致错误 color[i][j] = p;//记录所属类别 same[p].push_back(po);//把每一个类别的记录在一个行数组里面 } } int m; scanf("%d",&m); int x,y,c; for(int i = 0; i < m ;++i){ scanf("%d %d %c",&x,&y,&c);//要分开读 card[x][y] = c-'A'; //把A,B..转换成0-5数字存储 方便递归时候遍历 } dfs(0,0); return 0; }