690 . 數獨
TopCoder
Tags
Description
你知道數獨嗎？數獨是一個填數字的遊戲。遊戲會給你一個 $9\times 9$ 的方陣，其中這個方陣會被切分成 $9$ 個 $3\times 3$ 的子方陣。數獨中的 $9\times 9=81$ 個格子中有的有填數字，有的是空白。範例如下圖：
數獨的規則是這樣的，你不能動已經填有數字的格字；對於所有空白的格子，你必須要填上 $1\sim 9$ 其中一個數字，使得每一列、每一列、每一個子方陣中都不能有重複的數字。
現在給你一個數獨，你的任務是寫一個程式來完成這個數獨。
Input Format
輸入只有一行，包含 $81$ 個字元；這些字元可能是 $1\sim 9$，代表這格已經填上數字，或者是 . ，代表這格還沒填上數字。這 $81$ 的字元的第 $0\sim 8$ 的字元對應到數獨的第一列、$9\sim 18$ 的字元對應到數獨的第二列、以此類推。我們保證未填上數字的格字不超過 $15$ 個。
Output Format
請輸出一行代表數獨完成後的結果，格式和輸入格式一樣。若存在多組解的話，請輸出字典序最小的解（字典序的定義請參考這裡）。若無解的話，請輸出 No solution.。
Sample Input 1
1263549873476891255897216437.18624.9465193872298475316652948.31914237568873516294
Sample Output 1
126354987347689125589721643731862459465193872298475316652948731914237568873516294
Sample Input 2
2.5.9.18614653.7.2789216435.27953618968.745235136829..8517293643...652716.23.18.9
Sample Output 2
235497186146538792789216435427953618968174523513682947851729364394865271672341859
Hints
Problem Source
NEOJ
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~20 | 無額外限制 | 100 |