1. 
/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10
* Problem: 989 Su Doku
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=11&page=show_problem&problem=930
*
* @author Barny Porcio
* @version 1.0, 05/01/2010
*
* Method : Backtracking
* Status : Accepted
* Runtime: 0.748
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.TreeSet;



public class SuDoku989 {
static int n;
private static int[][] field;
private static TreeSet<Integer>[] rows;
private static TreeSet<Integer>[] colms;
private static TreeSet<Integer>[] fields;

private static boolean add (int row, int col, int val){
if (rows[row].contains(val) || colms[col].contains(val) || fields[(row/n)*n+col/n].contains(val))
return false;
rows[row].add(val);
colms[col].add(val);
fields[(row/n)*n+col/n].add(val);
field[row][col] = val;
return true;
}
private static void remove(int row, int col){
rows[row].remove(field[row][col]);
colms[col].remove(field[row][col]);
fields[(row/n)*n+col/n].remove(field[row][col]);
field[row][col] = 0;




}

private static boolean backtrack(int row,int col){
if (row == field.length-1 && col == field.length-1 ){
if (field[row][col] != 0)
return true;
else{
for(int i = 0; i <field.length;++i)
if (add(row,col,i+1))
return true;
return false;
}
}
else{
if (field[row][col] != 0){
return backtrack(row+(col+1)/field.length, (col+1)%field.length);
}
for(int i = 0; i <field.length; ++i){
if (add(row,col,i+1)){
if (backtrack(row+(col+1)/field.length, (col+1)%field.length))
return true;
else{
remove(row, col);
if (i == field.length-1)
return false;
}
}
else if (i == field.length-1)
return false;

}




}
System.out.println("error");
return true;

}

@SuppressWarnings("unchecked")
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
boolean first = true;
while(br.ready()){
n = Integer.parseInt(br.readLine());
int nsquare = n*n;
rows = new TreeSet[nsquare];
colms = new TreeSet[nsquare];
fields = new TreeSet[nsquare];
for (int i = 0; i < nsquare; ++i){
rows[i] = new TreeSet<Integer>();
colms[i] = new TreeSet<Integer>();
fields[i] = new TreeSet<Integer>();
}
field = new int[nsquare][nsquare];
//einlesen und initialisieren
for(int i = 0; i < nsquare ; ++i){
String zeile = br.readLine();
for (int i2 = 0 ; i2 < nsquare; ++i2){
int temp = Integer.parseInt(zeile.substring(i2*2, i2*2+1));
field[i][i2] = temp;
rows[i].add(temp);
colms[i2].add(temp);
fields[(i/n)*n+i2/n].add(temp);
}
}
if (first)
first = false;
else
System.out.println();
if (!backtrack(0, 0))
System.out.println("NO SOLUTION");

else {
for (int[] ia : field){
for(int i = 0; i < ia.length; ++i){
if (i != 0)
System.out.print(" ");
System.out.print(ia[i]);
}
System.out.println();

}

}
br.readLine();
}

}

}