d352. 10957 - So Doku Checker - 高中生程式解題系統

內容

一個好玩的益智遊戲，通常只是由簡單的點子演變而來的。數獨就是這樣的一個益智遊戲。雖然數獨已經有二十多年的歷史了，然而直到最近幾年，數獨才開始快速的席捲全世界。現今有上百份的報紙和網站，都有在刊載數獨謎題，數獨可以說是每天的活動了。大家應該很好奇數獨到底是什麼，就讓我來做個詳細的介紹：

上面就是一個數獨謎題。大家可以看到盤面呈9x9的方格，其中有些方格填上了1到9之間的數字；此外，盤面也可以看作是呈3x3的大方格（深顏色的線）。數獨的目的，就是要用1到9的數字，填滿所有空白的方格，還要符合下面三個規定：

　‧每一行都恰有1到9。

　‧每一列都恰有1到9。

　‧每個大方格都恰有1到9。

玩數獨時，可以準備紙筆作紀錄，利用消去法逐步推理出答案。當然，數獨也必須設計成可以找出答案。所以一個完善的數獨，必須要符合規定（行、列、大方格之內不能出現同樣的數字）、可以求解（有辦法將所有空白方格填上數字，並且符合規定）、答案要唯一（只有一種解法）。這些都是你的程式要檢查的地方。

輸入說明

輸入包括好幾個數獨謎題，每個謎題佔有9行，每行9個數字，剛好代表一個9x9的盤面，盤面上的空白方格則以0來代替。每個數字之間都會空一格。每個數獨謎題之間都會空一行。

輸出說明

根據輸入的盤面，判斷該數獨謎題是下面四種情形當中的哪一種：

　‧Illegal，一開始的盤面，就違反了上面那三個規定。

　‧Unique，只有一種解法。

　‧Ambiguous，有多種解法。

　‧Impossible，沒有解法。

然後印出一行判斷結果。輸出格式請參考 Sample Output。

注意：根據上述定義，Illegal同時也會是Impossible，在這種情形下，你的程式只要印出Illegal就好了。當輸入的盤面符合規定，卻無法按照規定填滿方格時，這時候就要印Impossible。

範例輸入 #1

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

範例輸出 #1

Case 1: Unique.
Case 2: Ambiguous.
Case 3: Illegal.
Case 4: Impossible.

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (100%): 1.0s , <1M

提示：

Translated by DJWS

標籤:

出處:

UVa 10957 [管理者： pcsh710742 (ms0472904) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」