Test Message

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)
#include <stdio.h>

int main()
{
int ans;
char input[10], output[2] = { 0 };
while (gets(input))
{
ans = 45;
for (int i = 0; i < 9; i++)
ans -= input[i] ^ '0';
output[0] = ans | '0';
puts(output);
}
return 0;
}