1.

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS10/11
* Problem: 989 - Su Doku
* Link: http://uva.onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&page=show_problem&category=&problem=930&mosmsg=Submission+received+with+ID+8488207
*
* @author Manuel Hager
* @version 1.0, 12/30/2010
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.404
*/

import java.util.Scanner;

public class Main
{
private final int[][] grid;
private final int Q;
private final int N;

private static final String LF = System.getProperty("line.separator");
private static boolean first = true;

public Main(Scanner scanner)
{
Q = scanner.nextInt();
N = Q * Q;
grid = new int[N][N];
for(int y = 0; y < N; y++)
for(int x = 0; x < N; x++)
grid[y][x] = scanner.nextInt();
}

public void process() {
if(!first) {
System.out.println();
} else {
first = false;
}

if(backtrack()) {
StringBuilder result = new StringBuilder((N + 1) * (N + 1));
for(int y = 0; y < grid.length; y++) {
for(int x = 0; x < N - 1; x++) {
result.append(grid[y][x] + " ");
}
result.append(grid[y][N - 1] + LF);
}
System.out.print(result.toString());
} else {
System.out.println("NO SOLUTION");
}
}

private boolean backtrack()
{
for(int y = 0; y < N; y++) {
for(int x = 0; x < N; x++) {
if(grid[y][x] == 0) {
for(int n = 1; n <= N; n++) {
if(rowCollision(y, n))
continue;
if(colCollision(x, n))
continue;
if(tileCollision(x/Q*Q, y/Q*Q, n))
continue;

grid[y][x] = n;

if(backtrack()) {
return true;
}
grid[y][x] = 0;
}
return false;
}
}
}
return true;
}

private boolean rowCollision(final int y, final int num)
{
for(int x = 0; x < N; x++)
if(grid[y][x] == num)
return true;
return false;
}

private boolean colCollision(final int x, final int num)
{
for(int y = 0; y < N; y++)
if(grid[y][x] == num)
return true;
return false;
}

private boolean tileCollision(final int x, final int y, final int num)
{
for(int dy = 0; dy < Q; dy++)
for(int dx = 0; dx < Q; dx++)
if(grid[y + dy][x + dx] == num)
return true;
return false;
}

public static void main(final String[] args) {
Scanner scanner = new Scanner(System.in);
while(scanner.hasNextInt()) {
new Main(scanner).process();
}
}
}




2.
/**
* 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();
}

}

}