Q989: Su Doku

很多報紙上都有提供一種叫做「數獨」的遊戲，給你一個9*9的方陣，有些格子填有1~9的數字，有些格子則是空白。你的任務是完成這個方陣，使得每一列（橫的），每一行（直的），以及每一個小九宮格中的數字都剛好是1∼9。

下面的圖就是一個例子：左圖為開始時的方陣狀態，右圖為完成後方陣的樣子。

初始方陣       完成方陣

Input

輸入含有多組測試資料。

每組測試資料的第一列，有一個數字 n，（1 <= n <= 3）。接下來有一個n2*n2方陣，有些格子填有1~n2 的數字，有些格子則是0（代表空白）。你的任務是完成這個方陣，使得每一列（橫的），每一行（直的），以及每一個n*n小方陣中的數字都剛好是1∼n2 。
輸入格式請參考Sample Input。

Output

對每組測試資料，輸出該數獨的解。如果存在不只一組解，請輸出字典順序最小的那個（也就是越上方，越左方，比較小的那組）。如果沒有解，請輸出 NO SOLUTION。

各組測試資料間請輸出一空白列。

Sample Input Sample Output 
3
0 6 0 1 0 4 0 5 0
0 0 8 3 0 5 6 0 0
2 0 0 0 0 0 0 0 1
8 0 0 4 0 7 0 0 6
0 0 6 0 0 0 3 0 0
7 0 0 9 0 1 0 0 4
5 0 0 0 0 0 0 0 2
0 0 7 2 0 6 9 0 0
0 4 0 5 0 8 0 7 0
 
9 6 3 1 7 4 2 5 8
1 7 8 3 2 5 6 4 9
2 5 4 6 8 9 7 3 1
8 2 1 4 3 7 5 9 6
4 9 6 8 5 2 3 1 7
7 3 5 9 6 1 8 2 4
5 8 9 7 1 3 4 6 2
3 1 7 2 4 6 9 8 5
6 4 2 5 9 8 1 7 3