1.
/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS09
* Problem: 989 Su Doku
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=11&page=show_problem&problem=930
*
* @author Christoph Hausmann
* @version 0.1, 11/4/2009
*
* Method : Iterative Backtracking
* Status : Accepted
* Runtime: 0.536
*/

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;


public class SuDoku_989 {

/**
* Represents a Grid.
*
*/
public static class Grid implements Comparable<Grid> {
int[][] grid;
int curRow;
int curCol;

public Grid(final int[][] grid, int curRow, int curCol) {
this.grid = grid;
this.curRow = curRow;
this.curCol = curCol;
}

@Override
public Grid clone() {
return new Grid(copy(grid),curRow,curCol);
}

private static int[][] copy(int[][] source) {
final int[][] newGrid = new int[source.length][source[0].length];

for (int a=0;a<source.length;a++) {
System.arraycopy(source[a],0,newGrid[a],0,source[a].length);
}


return newGrid;
}

public void next() {
curCol++;
if(curCol >= grid.length) {
curCol = 0;
curRow++;
}
}

@Override
public int compareTo(Grid o) {
final int comp = (curRow*grid.length+curCol) - (o.curRow*o.grid.length+o.curCol);
return comp;
}

public boolean isComplete() {
return curRow >= grid.length;
}
}

public static void main(String... args) {
final Scanner scanner = new Scanner(System.in);

while(true) {
final int n = scanner.nextInt();
final int[][] grid = new int[n*n][n*n];
for(int row = 0; row < n*n; row++) {
for(int col = 0; col < n*n; col++) {
grid[row][col] = scanner.nextInt();
}
}

final Grid lexLowest = fillGrid(new Grid(grid,0,0), n);

if(lexLowest == null) {
System.out.println("NO SOLUTION");

} else {

for(int row = 0; row < n*n; row++) {
for(int col = 0; col < (n*n)-1; col++) {
System.out.print(lexLowest.grid[row][col] + " ");
}
System.out.println(lexLowest.grid[row][lexLowest.grid.length-1]);
}
}

if(scanner.hasNextInt())
System.out.println();
else
break;
}
}

/**
* Fills the grid and returns a solution, null otherwise.
* @param grid
* @param n
* @return
*/
private static Grid fillGrid(final Grid grid, int n) {
final List<Grid> gridsToCheck = new ArrayList<Grid>();

gridsToCheck.add(grid);

while(gridsToCheck.size() > 0) {

final Grid curGrid = gridsToCheck.remove(0);

if(curGrid.grid[curGrid.curRow][curGrid.curCol] == 0) {
for(int posNum : getPossibleNumbers(curGrid.grid, n, curGrid.curRow, curGrid.curCol)) {
final Grid newGrid = curGrid.clone();
newGrid.grid[newGrid.curRow][curGrid.curCol] = posNum;
newGrid.next();

if(newGrid.isComplete())
return newGrid;

gridsToCheck.add(0,newGrid);
}
} else {
curGrid.next();

if(curGrid.isComplete())
return curGrid;

gridsToCheck.add(0,curGrid);
}
}

return null;
}

/**
* Returns a list of numbers that are allowed in a given grid at a given position.
*
* @param curGrid
* @param n
* @param curRow
* @param curCol
* @return
*/
private static List<Integer> getPossibleNumbers(int[][] curGrid, int n, int curRow, int curCol) {
final int n_square = n*n;

final Set<Integer> possibleNums = new HashSet<Integer>();

// add all numbers
for(int i = 1; i <= n_square; i++)
possibleNums.add(i);

// remove all numbers in a row
for(int col = 0; col < n_square; col++)
possibleNums.remove(curGrid[curRow][col]);

// remove all numbers in a column
for(int row = 0; row < n_square; row++)
possibleNums.remove(curGrid[row][curCol]);

// remove all numbers in the box
int rowStart = (curRow/n)*n;
int colStart = (curCol/n)*n;

for(int rInc = 0; rInc < n; rInc++) {
for(int cInc = 0; cInc < n; cInc++) {
possibleNums.remove(curGrid[rowStart+rInc][colStart+cInc]);
}
}

final List<Integer> possibleNumsList = new ArrayList<Integer>(possibleNums);
Collections.sort(possibleNumsList, new Comparator<Integer>() {

@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}});

return possibleNumsList;
}
}