主題

ZeroJudge - d352: 10957 - So Doku Checker 解題心得

Not In My Back Yard | 2021-05-07 00:00:06 | 巴幣 0 | 人氣 66

題目連結:


題目大意:
輸入有多筆測試資料,每筆測資(每筆測資之間有一列空白列)佔九列,每列給定九個整數(只會是 0 ~ 9, 0 代表未填數字的格子),代表一個數獨的版面。

試問該數獨的版面為以下何種狀態:
Illegal,該數獨不合法。
Unique,該數獨有唯一解。
Ambiguous,該數獨有多種解。
Impossible,該數獨不可解。

其中因為 Illegal 根據文義也是屬於 Impossible 的一部分,此時只需輸出 Illegal 即可。

輸出格式參見範例輸出。



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


範例輸出:
Case 1: Unique.
Case 2: Ambiguous.
Case 3: Illegal.
Case 4: Impossible.


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

接著就是按照上面那題的方式去解解看,看解的數量有多少個。一個解,則輸出「Unique」、多個解則輸出「Ambiguous」、無解就輸出「Impossible」。




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

創作回應

更多創作