690 . 數獨

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

1xlc

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Tags

apcsc apcsc-enumerate

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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 524288 65536 1 2
1 1000 524288 65536 1 2
2 1000 524288 65536 2
3 1000 524288 65536 2
4 1000 524288 65536 2
5 1000 524288 65536 2
6 1000 524288 65536 2
7 1000 524288 65536 2
8 1000 524288 65536 2
9 1000 524288 65536 2
10 1000 524288 65536 2
11 1000 524288 65536 2
12 1000 524288 65536 2
13 1000 524288 65536 2
14 1000 524288 65536 2
15 1000 524288 65536 2
16 1000 524288 65536 2
17 1000 524288 65536 2
18 1000 524288 65536 2
19 1000 524288 65536 2
20 1000 524288 65536 2
Submit
Back to Top