/*
d263 , b053 sudo
本程式在 d263 可 AC 但在 b053 吃 *** SE !!!
*/
#include <iostream>
using namespace std;
const int MaxN = 3*3;
int sudo[MaxN][MaxN];
int n , m; // 輸入的 n 、 m=n*n
bool yes; // 是否有找到
bool chk(int r, int c)
{
// sudo[r][c] 所加入的數字是否合規定？
int i, j, r0, c0;
for(i=0; i<m; ++i) //檢查橫列
{
if(i==c) continue;
if( sudo[r][c] == sudo[r][i] ) return false;
}
for(i=0; i<m; ++i) //檢查直行
{
if(i==r) continue;
if( sudo[r][c] == sudo[i][c] ) return false;
}
r0 = r/n*n; c0 = c/n*n; //檢查小九宮
for(i=0;i<n;++i)
for(j=0;j<n;++j)
{
if(r==r0+i && c==c0+j) continue;
if( sudo[r][c] == sudo[r0+i][c0+j] ) return false;
}
// 皆過關
return true;
}
void dfs(int r, int c)
{
// sudo[r][c] r,c若已填完最後一格，則 印出
int i,j,k;
r += c/m; c%=m;
if(r==m) //都填入了
{
for(i=0;i<m;++i)
{
cout << sudo[i][0];
for(j=1;j<m;++j)
cout << " " << sudo[i][j];
cout << endl;
}
yes = true;
return;
}
else if( sudo[r][c] )
{
//此格已填，若原數字符合，則下一格
if( chk(r,c) ) dfs(r, c+1);
return ;
}
else
{
for( k=1; k<=m; ++k) // 填入 1 ~ n^2 ，
{
sudo[r][c] = k;
if( chk(r,c) ) dfs(r, c+1); // 檢查是否可填入，可的話往下一格 dfs(r , c+1 )
if(yes) return;
}
sudo[r][c] = 0; // 此格不過，改回 0
}
}
int main()
{
int r,c;
bool first=true;
while( cin >> n )
{
if(first) first = false; else cout << endl;
if(n==0) { cout << "NO SOLUTION" << endl; continue; }
m = n*n; // m 為 n^2 : n=2即 4x4 、 n=3 即 9x9
for(r=0; r<m; ++r)
for(c=0; c<m; ++c)
cin >> sudo[r][c];
yes = false;
dfs( 0 , 0 ); //由 (0,0)格 每一格填入 1 ~ n^2 試
if(!yes) cout << "NO SOLUTION" << endl;
}
return 0;
}
/* 輸入範例 ---
2
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1
0
2
0 3 0 0
4 0 0 0
1 0 0 0
0 0 2 0
2
2 3 4 0
0 4 0 0
1 0 2 0
0 2 0 3
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
3
3 6 0 1 9 4 7 5 8
4 1 8 0 7 5 6 2 9
2 7 0 0 8 0 4 1 3
8 3 1 4 5 7 2 9 6
9 5 4 8 6 2 1 3 7
7 2 6 9 0 3 5 8 4
5 9 3 7 0 1 8 6 2
1 8 7 2 3 6 9 4 5
6 4 2 5 0 8 3 7 1
輸出 ------------------
NO SOLUTION
1
2 3 1 4
4 1 3 2
1 2 4 3
3 4 2 1
NO SOLUTION
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
NO SOLUTION
*/