拉丁方塊填數字 /* 方塊填數 “數獨”是當下炙手可熱的智力游戲。一般認為它的起源是“拉丁方塊”,是大數學家歐拉于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):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的字母方陣,表示該解。 解的字母之間用空格分開。 如果找不到任何滿足條件的解,則輸出“無解” 例如:用戶輸入: 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
再如,用戶輸入: 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 */
新聞熱點
疑難解答