d250: 94北縣賽-2-數獨問題 (Sudoku)
內容
數獨 ”sudoku”來自日文,其概念源自「拉丁方塊」,是十八世紀瑞士數學家
歐拉發明的。遊戲規則很簡單:在九個九宮格里, 分別填入 1 到 9 的數字,讓每個
數字在每個行、列及九宮格里都只出現一次。謎題中會預先填入若干數字,但有部
分數字尚未填入,玩家得依謎題中數字分佈的狀況,推敲出尚未出現的數字。現在
我們簡化數獨的問題,假設九宮格中每一行及每一列尚未出現的數字都只有一個。
請你寫一個程式,從檔案讀入一個數獨題目,找出每一行尚未出現的數值。
如以下之數獨題目範例:
2 | 8 | 1 | 6 | 7 | 3 | 9 | 4 | |
---|---|---|---|---|---|---|---|---|
6 | 4 | 3 | 2 | 8 | 7 | 1 | 5 | |
1 | 7 | 3 | 4 | 9 | 2 | 6 | 8 | |
3 | 4 | 5 | 6 | 8 | 1 | 7 | 2 | |
8 | 1 | 7 | 3 | 4 | 9 | 5 | 6 | |
2 | 5 | 6 | 7 | 1 | 9 | 4 | 3 | |
4 | 3 | 5 | 8 | 1 | 6 | 2 | 9 | |
7 | 6 | 2 | 9 | 5 | 3 | 4 | 1 | |
9 | 8 | 1 | 6 | 4 | 2 | 5 | 3 |
則第一列之空格應填入 5,第二列之空格應填入 9,第三列之空格應填入 5,第四列
之空格應填入 9,第五列之空格應填入 2,第六列之空格應填入 8,第七列之空格應
填入 7,第八列之空格應填入 8,第九列之空格應填入 7。
填滿結果如以下所示
5 | 2 | 8 | 1 | 6 | 7 | 3 | 9 | 4 |
---|---|---|---|---|---|---|---|---|
6 | 4 | 9 | 3 | 2 | 8 | 7 | 1 | 5 |
1 | 7 | 3 | 4 | 9 | 5 | 2 | 6 | 8 |
3 | 9 | 4 | 5 | 6 | 8 | 1 | 7 | 2 |
8 | 1 | 7 | 2 | 3 | 4 | 9 | 5 | 6 |
2 | 5 | 6 | 7 | 1 | 9 | 4 | 8 | 3 |
4 | 3 | 5 | 8 | 7 | 1 | 6 | 2 | 9 |
7 | 6 | 2 | 9 | 5 | 3 | 8 | 4 | 1 |
9 | 8 | 1 | 6 | 4 | 2 | 5 | 3 | 7 |
輸入
每個測試檔案中共有九行,每一行中有 9 個連續且不重複的個位數,對應到九宮格
中的每一列。其中 8 個數字為 1 到 9 之間的數字,另外有一個數字為 0,表示空白
的位置。
028167394
640328715
173490268
304586172
817034956
256719403
435801629
762953041
981642530
輸出
依序輸出各列空白的空位應該填入的個位數。
5
9
5
9
2
8
7
8
7
解題思路
數獨每行元素必為 1~9 各一個,所以每行的總和為 45。
因此將 45 減去所有元素,剩下的值即是沒有填入的數,輸出該值即可。
完整程式碼
AC (2ms, 84KB)
|