d250: 94北縣賽-2-數獨問題 (Sudoku)

內容

數獨 ”sudoku”來自日文，其概念源自「拉丁方塊」，是十八世紀瑞士數學家

歐拉發明的。遊戲規則很簡單：在九個九宮格里， 分別填入 1 到 9 的數字，讓每個
數字在每個行、列及九宮格里都只出現一次。謎題中會預先填入若干數字，但有部
分數字尚未填入，玩家得依謎題中數字分佈的狀況，推敲出尚未出現的數字。現在
我們簡化數獨的問題，假設九宮格中每一行及每一列尚未出現的數字都只有一個。
請你寫一個程式，從檔案讀入一個數獨題目，找出每一行尚未出現的數值。
如以下之數獨題目範例：

則第一列之空格應填入 5，第二列之空格應填入 9，第三列之空格應填入 5，第四列
之空格應填入 9，第五列之空格應填入 2，第六列之空格應填入 8，第七列之空格應
填入 7，第八列之空格應填入 8，第九列之空格應填入 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;
}