問題 H: 方塊填數（2012年藍橋決賽第5題）
時間限制: 1 Sec 內存限制: 128 MB

[提交][狀態][討論版]
題目描述

“數獨”是當下炙手可熱的智力游戲。一般認為它的起源是“拉丁方塊”，是大數學家歐拉于1783年發明的。

如圖[1.jpg]所示：6x6的小格被分為6個部分（圖中用不同的顏色區分）,每個部分含有6個小格（以下也稱為分組）。

開始的時候，某些小格中已經填寫了字母（ABCDEF之一）。需要在所有剩下的小格中補填字母。

全部填好后，必須滿足如下約束：

所填字母只允許是A,B,C,D,E,F 中的某一個。

每行的6個小格中，所填寫的字母不能重復。

每列的6個小格中，所填寫的字母不能重復。

每個分組（參見圖中不同顏色表示）包含的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的字母方陣，表示該解。

解的每個字母后輸出一個空格。

如果找不到任何滿足條件的解，則輸出“無解”

例如：用戶輸入：

000011022013221113243333244455445555602C03B05A20D35E53F

則程序輸出：

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

再如，用戶輸入：

001111 002113 022243 022443 544433 555553 7 04B 05A 13D 14C 24E 50C 51A

則程序輸出：

1 D C E F B A E F A D C B A B F C E D B E D A F C F D C B A E C A B E D F 2 D C E F B A E F A D C B A D F B E C B E C A F D F B D C A E C A B E D F 3 D C F E B A A E B D C F F D A C E B B F E A D C E B C F A D C A D B F E 4 D C F E B A B E A D C F A D C F E B F B E A D C E F B C A D C A D B F E 5 D C F E B A E F A D C B A B C F E D B E D A F C F D B C A E C A E B D F 6 D C F E B A E F A D C B A B D F E C B E C A F D F D B C A E C A E B D F 7 D C F E B A E F A D C B A D B F E C B E C A F D F B D C A E C A E B D F 8 D C F E B A F E A D C B A D B C E F B F E A D C E B C F A D C A D B F E 9 D C F E B A F E A D C B A F C B E D B D E A F C E B D C A F C A B F D E

輸入
輸出
提示
/*
dfs爆搜，依次搜索每個位置可以滿足條件的字母即可，
當前位置放一個字母，判斷范圍：每行，每列，同一組的
*/
AC_code:

#include <bits/stdc++.h> using namespace std; struct Map {int num;char alp;int flag; }mp[8][8]; vector<int>group[37]; int ans = 0; bool check(int x,int y,char p) {for(int i = 0; i < 6; i++){if(mp[x][i].alp == p || mp[i][y].alp == p) return false;int temp = group[mp[x][y].num][i];if(mp[temp/6][temp%6].alp == p) return false;}return true; } void dfs(int s) {if(s == 36){printf("%d\n",++ans);for(int i = 0; i < 6; i++){putchar(mp[i][0].alp);for(int j = 1; j < 6; j++){printf(" %c",mp[i][j].alp);}printf("\n");}return;}else{int sx = s / 6, sy = s % 6;if(mp[sx][sy].flag) //一開始就固定了的直接搜索下一個位置{dfs(s+1);}for(char i = 'A'; i <= 'F'; i++){if(check(sx,sy,i)&&mp[sx][sy].alp=='#'){mp[sx][sy].alp = i;dfs(s+1);mp[sx][sy].alp = '#';}}} } int main() {char s[10];for(int i = 0; i < 6; i++){scanf("%s",s);for(int j = 0; j < 6; j++){mp[i][j].num = s[j]-'0';mp[i][j].alp = '#';mp[i][j].flag = 0;group[mp[i][j].num].push_back(i*6+j); }}int n;scanf("%d",&n);while(n--){int x,y;scanf("%s",s);x = s[0]-'0';y = s[1]-'0';mp[x][y].alp = s[2];mp[x][y].flag = 1;}dfs(0);return 0; }

總結

以上是生活随笔為你收集整理的问题 H: 方块填数（2012年蓝桥决赛第5题--dfs）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。