1.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS11
* Problem: 989 Su Doku
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=11&page=show_problem&problem=930
*
* @author Burgmair Stefan
* @author YYY
* @version 1.0, 02/05/2011
*
* Method : Ad-Hoc
* Status : Accepted
* Runtime: 0.588
*/

public class Main
{
public static int boxsize;
public static boolean isLastOutput = false;

public static void main(String[] args) throws IOException
{
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
ArrayList<String[]> input = new ArrayList<String[]>();
int[][]map;
do
{
String inLine = reader.readLine();
boxsize = Integer.parseInt(inLine);
for (int i = 0; i < boxsize*boxsize; i ++)
{
inLine = reader.readLine();
if(!inLine.equals(""))
input.add(inLine.split(" "));
}
if(reader.ready())
reader.readLine();
map = createArrayMap(input);

if (reader.ready() == false)
isLastOutput = true;

if(findSolution(map) == false){
System.out.println("NO SOLUTION");
if (isLastOutput == false)
System.out.println();
}

input.clear();
boxsize = -1;

}
while(reader.ready());
}

public static int[][] createArrayMap(ArrayList<String[]> input)
{
int [][] map = new int [boxsize*boxsize][boxsize*boxsize];

for (int o = 0; o < boxsize*boxsize; o++)
{
String[] line = input.get(o);
for (int p = 0; p < boxsize*boxsize; p++)
{
map[o][p] = Integer.parseInt (line[p]);
}
}
//printMap(map, false);
return map;
}

public static boolean findSolution(int[][] map)
{
int col = -1;
int row = -1;
boolean mapIsFilled = true;

for(int i = 0; i < boxsize*boxsize; i++)
{
for(int j = 0; j < boxsize*boxsize; j++)
{
if(map[i][j] == 0 && col == -1 && row == -1)
{
col = i;
row = j;
}
else if (map[i][j] == 0)
{
mapIsFilled = false;
}
}
}
for(int k = 1; k <= boxsize*boxsize; k++)
{
if (set(col, row, k, map))
{
int[][] mapX = cloneMap(map);
mapX[col][row] = k;
if (mapIsFilled){
printMap(mapX, isLastOutput);
return true;
}
else
{
if (findSolution(mapX)){
return true;
}
}
}
}
return false;
}

public static boolean set(int col, int row, int value, int [][] map)
{
for(int i = 0; i < boxsize*boxsize; i++)
{
if(map[col][i] == value)
return false;
}
for(int i = 0; i < boxsize*boxsize; i++)
{
if(map[i][row] == value)
return false;
}
for(int i = getBox(col); i < boxsize+getBox(col); i++)
{
for(int j = getBox(row); j < boxsize+getBox(row); j++)
{
if(map[i][j] == value)
return false;
}
}
return true;
}

public static int getBox(int value)
{
if (value < boxsize)
return 0;
if (value < boxsize+boxsize)
return boxsize;
return boxsize+boxsize;
}

public static int[][] cloneMap(int[][] map)
{
int[][] cloneMap = new int[map.length][map.length];
for(int i = 0; i < map.length; i++)
{
for(int j = 0; j < map.length; j++)
{
cloneMap[i][j] = map[i][j];
}
}
return cloneMap;
}

public static void printMap(int[][] map, boolean isLastOutput)
{
for (int x = 0; x < map.length; x ++)
{
for (int y = 0; y < map.length; y ++)
{
System.out.print(map[x][y]);
if (y + 1 < map.length)
System.out.print(" ");
}
if (x + 1 < map.length | isLastOutput == false)
System.out.println();
}
if (isLastOutput == false)
System.out.println();
}
}




----------------------------------------------------
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();
}

}

}