主題

ZeroJudge - d263: 00989 - Su Doku 解題心得

Not In My Back Yard | 2021-05-08 00:00:03 | 巴幣 0 | 人氣 20

題目連結:


題目大意:
輸入有多筆測試資料。每筆測資第一列給定一正整數 n (1 ≦ n ≦ 3),代表接下來有一個 n ^ 2 × n ^ 2 大小的數獨。

接著有 n ^ 2 列,每列給定 n ^ 2 個整數(有些為 0 ,代表該格尚未填上數字;有些為 1 ~ 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


解題思維:
利用這題統計初始版面的數字出現情形。如果有數字重複出現於列、行或是九宮格之內,則代表版面不合法。此時直接輸出「NO SOLUTION」即可。

然後接著就按照上面那題的做法去找看看有沒有解。解的過程記得從最左上開始,由左到右從上至下解,然後由最小的數字開始試。這樣便可以確保如果有解的話,最先找到的解會是字典序最小的。有解就輸出該解的版面;無解就輸出「NO SOLUTION」。




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

創作回應

更多創作