TopCoder

User's AC Ratio

94.4% (51/54)

Submission's AC Ratio

61.1% (58/95)

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

For Testdata: 0 ~ 0, Score: 16
For Testdata: 1 ~ 1, Score: 16
For Testdata: 2 ~ 2, Score: 16
For Testdata: 3 ~ 3, Score: 16
For Testdata: 4 ~ 4, Score: 16
For Testdata: 5 ~ 5, Score: 20
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536
5 1000 65536 65536