60 . 數獨

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

roychuang

User's AC Ratio

84.0% (21/25)

Submission's AC Ratio

48.4% (59/122)

Tags

Algo Algo25_a

Description

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

圖一：一個數獨的範例。

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

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

Input Format

輸入的第一行包含一個數字 $T\, (T \leq 10)$ ，代表測試資料的數量。每筆測試資料僅一行，包含 $81$ 個字元。這些字元可能為 $1\sim 9$，代表已經填上數字，或者可能為 .，代表此格尚未填上數字。

每筆測試資料未填上數字的格子數保證不超過 $15$ 個。注意已填上的數字本身可能是不符規則的。

輸入的順序以圖一為例為：.2738..1..1...6735.......293.5692.8...........6.1745.364.......9518...7..8..6534.

Output Format

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

如果不存在任何一組合法解的話，請輸出一行 No solution.

Sample Input 1

2
5.73284911324697..4895712638437951267956123842168.35793519876426281549379742.6815
8.762513.5123.7689..6.8925767391482.2548763.11895324.69254687134..751962.612935.8

Sample Output 1

567328491132469758489571263843795126795612384216843579351987642628154937974236815
897625134512347689346189257673914825254876391189532476925468713438751962761293548

Hints

Problem Source

NEOJ Problem 62

Subtasks

No. Testdata Range Constraints Score
1 0~3 未填上數字的格子數恰為 $5$ 個 40
2 0~10 無額外限制 60

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1 2
1 1000 65536 65536 1 2
2 1000 65536 65536 1 2
3 1000 65536 65536 1 2
4 1000 65536 65536 2
5 1000 65536 65536 2
6 1000 65536 65536 2
7 1000 65536 65536 2
8 1000 65536 65536 2
9 1000 65536 65536 2
10 1000 65536 65536 2
Submit
Back to Top