1025 . 數獨問題
TopCoder
Tags
Description
所謂的數獨就是在一個九乘九的宮格（9個三乘三宮格）裡，填入1到9等9個數字，讓每個數字在每一行、列及所在的三乘三宮格裡都只出現一次。謎題中會預先填入若干數字，其他宮格位則留白讓玩家自行填入，通常數獨題目都會設計成唯一解。但本題之測試輸入可能會有多解，請你通通將其輸出。
你可以假設題目所給的數獨都是合法的，也就是不會有本身已經填好的數字不合規則的情形存在。題目的解數不會超過50組。
Input Format
一組數獨題目，依序由上到下、由左到右給出所有格子的內容，空白的格子將用0代表，其他數字則代表給定的格子內是什麼數字。各個數字之間將以空白隔開。
Output Format
對於題目所給的數獨題目，請依照字典順序輸出所有可能的解。最後請印出有幾組解。
Sample Input 1
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
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
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).
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 |