sudo

題目敘述

在數獨遊戲中，遊戲給你一個 $9\times 9$ 的方陣，其中還可以分成 $9$ 個 $3\times 3$ 的子方陣。例如：

圖一：一個數獨的範例。

數獨的遊戲規則是這樣的，最後完成數獨的時候，每個格子都必須填上 $1\sim 9$ 其中一個數字，並且在每一行、每一列、每一個子方陣中，都不能有重複的數字。

現在給你一個 $9\times 9$ 的方陣，上面有一些格子已經寫上數字了，你的任務是完成這個數獨。

輸入說明

測試資料中包含多筆測試資料(不超過 $10$ 筆)，每筆測試資料僅一行，包含 $81$ 個字元。這些字元可能為 $1\sim 9$，代表已經填上數字，或者可能為'.'，代表此格尚未填上數字。

輸入的最後一行會是"end"，代表測試資料已經結束，不需要對此行做任何輸出。

除了最後一筆測資外，每筆測試資料未填上數字的格子數保證不超過 $15$ 個。

輸入的順序以圖一為例為：

.2738..1..1...6735.......293.5692.8...........6.1745.364.......9518...7..8..6534.

輸出說明

對於每筆測試資料，輸出數獨完成後的結果，若存在多組解的話，請輸出字典序最小的一組解(可將輸出視為一個大整數，請輸出值最小的解)。

如果不存在任何一組合法解的話，請輸出一行"No solution."(不含雙引號)

範例輸入

5.73284911324697..4895712638437951267956123842168.35793519876426281549379742.6815
8.762513.5123.7689..6.8925767391482.2548763.11895324.69254687134..751962.612935.8
end

範例輸出

567328491132469758489571263843795126795612384216843579351987642628154937974236815
897625134512347689346189257673914825254876391189532476925468713438751962761293548

子題一[40%]

未填上數字的格子數恰為 $5$ 個。

子題二[60%]

上述子題的條件不再成立。

Judge Setting

run-time limit: 20 ms
memory limit: 65536 byte
測資數量: 0