主題

ZeroJudge - b053: 4. 數獨遊戲 解題心得

Not In My Back Yard | 2021-05-02 00:00:09 | 巴幣 0 | 人氣 83

題目連結:


題目大意:
輸入有多筆測試資料。每筆測資第一列給定一正整數 n (1 ≦ n ≦ 3),代表有一個數獨版面有 n ^ 2 列 × n ^ 2 行。而就像典型的 9 × 9 (當 n = 3 時,就是典型的版面)數獨,每列、每行、每個子區域(原始數獨為 3 × 3,現在是 n × n)中的數字應為 1 ~ n 且每種數字只會出現一次。

接著有 n ^ 2 列,每列給定 n ^ 2 個整數(數字為 0 ~ n ^ 2),代表這個數獨的初始版面。

請輸出該數獨的任一組解。如果無解,則輸出「NO SOLUTION」。
 


範例輸入:
3
0 6 0 1 0 4 0 5 0
0 0 8 3 0 5 6 0 0
2 0 0 0 0 0 0 0 1
8 0 0 4 0 7 0 0 6
0 0 6 0 0 0 3 0 0
7 0 0 9 0 1 0 0 4
5 0 0 0 0 0 0 0 2
0 0 7 2 0 6 9 0 0
0 4 0 5 0 8 0 7 0


範例輸出:
9 6 3 1 7 4 2 5 8
1 7 8 3 2 5 6 4 9
2 5 4 6 8 9 7 3 1
8 2 1 4 3 7 5 9 6
4 9 6 8 5 2 3 1 7
7 3 5 9 6 1 8 2 4
5 8 9 7 1 3 4 6 2
3 1 7 2 4 6 9 8 5
6 4 2 5 9 8 1 7 3


解題思維:
先掃過一次初始版面,然後統計每列、每行、每個子區域(英文稱為 Boxes、Blocks 或是 Regions 等等)原本的 1 ~ 9 之出現情形。在此,我們定義 R[i][1] 、 C[i][1] 、 B[i][1] 分別代表為第 i 列、第 i 行以及第 i 個子區域(從左上開始,從左到右由上至下編號)裡有沒有數字 1 。其他如 R[i][7] 、C[i][8] 等等也是與此同理。

接著我們從數獨版面中任一一格開始(為了方便,我們從左上角開始,即第 0 列第 0 行):
對於每個位置 (i, j),我們掃過 1 ~ 9,對於那些沒有在 R 、 C 、 B 裡面的數字 k (即 R[i][k] 、 C[j][k] 、 B[block(i, j)][k] 都為假(False)),因此代表著本格可能要填數字 k 。其中 block(i, j) 為 floor(i ÷ 3) × 3 + floor(j ÷ 3),而 floor() 為下高斯函數。

所以對於每個數字 k ,我們就填填看 k (因此 R[i][k] 、 C[j][k] 、 B[block(i, j)][k] 要設為真(True)),然後遞迴到下一個格子看這個猜測是否可行。如果可行(也就是我們已經遞迴到最後一個格子然後成功地回來了),則代表我們成功地找到了一組解。此時的版面即為所求。

而遞迴的停止條件如下:
當沒有格子可以繼續遞迴時,即代表著我們解完該版面了。

例如,我們從 (0, 0) 開始,下一層可能是走到 (0, 1)。再下一層可能是 (0, 2)……然後到 (1, 0)……最後到 (8, 8),此時如果該格也有數字可以填,之後就沒有下一格可以走了。

由上面的步驟,我們便可以窮舉出所有可能的數字填法。因此找到一組解(如果有的話)。倘若窮舉完後如果沒有解,則輸出「NO SOLUTION」。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作