TopCoder

Thumb mikasa mikoto furikae
Omelet
ㄏ一ㄏ一 $$AC \approx (111111111)_2$$

User's AC Ratio

93.9% (93/99)

Submission's AC Ratio

66.0% (132/200)

Description

  所謂的數獨就是在一個九乘九的宮格(9個三乘三宮格)裡,填入1到9等9個數字,讓每個數字在每一行、列及所在的三乘三宮格裡都只出現一次。謎題中會預先填入若干數字,其他宮格位則留白讓玩家自行填入,通常數獨題目都會設計成唯一解。但本題之測試輸入可能會有多解,請你通通將其輸出
  你可以假設題目所給的數獨都是合法的,也就是不會有本身已經填好的數字不合規則的情形存在。題目的解數不會超過50組。

Input Format

一組數獨題目,依序由上到下、由左到右給出所有格子的內容,空白的格子將用0代表,其他數字則代表給定的格子內是什麼數字。各個數字之間將以空白隔開。

Output Format

對於題目所給的數獨題目,請依照字典順序輸出所有可能的解。最後請印出有幾組解。

Sample Input

1 2 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
7 9 8 1 2 3 4 5 6
2 1 4 3 6 5 8 9 7
3 6 5 8 9 7 2 1 4
8 7 9 2 1 4 3 6 5
5 3 2 9 4 1 6 7 8
6 4 1 5 7 8 9 3 2
0 0 0 0 0 0 0 0 0

Sample Output

1 2 3 4 5 6 7 8 9
4 5 6 7 8 9 1 2 3
7 9 8 1 2 3 4 5 6
2 1 4 3 6 5 8 9 7
3 6 5 8 9 7 2 1 4
8 7 9 2 1 4 3 6 5
5 3 2 9 4 1 6 7 8
6 4 1 5 7 8 9 3 2
9 8 7 6 3 2 5 4 1

1 2 6 4 5 9 7 8 3
4 5 3 7 8 6 1 2 9
7 9 8 1 2 3 4 5 6
2 1 4 3 6 5 8 9 7
3 6 5 8 9 7 2 1 4
8 7 9 2 1 4 3 6 5
5 3 2 9 4 1 6 7 8
6 4 1 5 7 8 9 3 2
9 8 7 6 3 2 5 4 1

there are a total of 2 solution(s).

Hints

這裡的測試資料比校內能力競賽的測試資料複雜一點點。

Problem Source

原TIOJ1025 / 96建中校內資訊能力競賽(prob2)

Subtasks

No. Testdata Range Score
1 0 16
2 1 16
3 2 16
4 3 16
5 4 16
6 5 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5
5 1000 65536 262144 6