EDIT: ho aggiornato un po il metodo risolvi, e le parti della classe a esso relative, comunque è rimasto all'incirca lo stesso, e soprattutto il problema è lo stesso...
codice:
 
package sudoku_solver;

import util.Cella;

public class SudokuSolver3{

	private Cella[][] sudoku;
	private Cella[][][] possibiliSoluzioni;
	int count = 0;

	public SudokuSolver3(Cella[][] sudoku, int numeroSoluzioni){
		if(sudoku.length != 9 || sudoku[0].length != 9 || numeroSoluzioni < 1)
			throw new IllegalArgumentException();
		this.sudoku = sudoku;
		this.possibiliSoluzioni = new Cella[numeroSoluzioni][9][9];
	}

	public void risolvi(){
		riempi(0, 0);
	}

	private void riempi(int row, int col){
		if(sudoku[row][col].getState() == Cella.Stato.IMPOSTATO)
			avanza(row, col);
		else{
			for(int n = 1; n < 10; n++){
				if(assegnabile(row, col, n)){
					assegna(row, col, n);
					if(row == 8 && col == 8)
						salvaSoluzione();
					else
						avanza(row, col);
				}
				deassegna(row, col);
			}
		}
	}

	private void salvaSoluzione(){
		for(int i = 0; i < 9; i++)
			for(int j = 0; j < 9; j++)
				possibiliSoluzioni[count][i][j] = new Cella(sudoku[i][j]);
	}

	private void avanza(int row, int col){
		if(col < 8)
			riempi(row, col + 1);// vai avanti sulla stessa riga
		else
			riempi(row + 1, 0);// altrimenti vai a capo
	}

	private void assegna(int row, int col, int n){
		sudoku[row][col].setVal(n);
		sudoku[row][col].setState(Cella.Stato.ASSEGNATO);
	}

	private void deassegna(int row, int col){
		sudoku[row][col].setVal(0);
		sudoku[row][col].setState(Cella.Stato.NON_ASSEGNATO);
	}

	private boolean assegnabile(int row, int col, int n){
		// controllo sulla riga
		for(int i = 0; i < 9; i++)
			if(sudoku[row][i].getVal() == n)
				return false;
		// controllo sulla colonna
		for(int i = 0; i < 9; i++)
			if(sudoku[i][col].getVal() == n)
				return false;
		//@formatter:off
		//determinamento del settore da controllare
//		int r, c;
//		if(row < 3)
//			r = 0;// si trova nella prima riga
//		else if(row >= 3 && row < 6)
//			r = 3;// nella seconda
//		else
//			r = 6;// nella terza
//		if(col < 3)
//			c = 0;// si trova nella prima colonna
//		else if(col >= 3 && col < 6)
//			c = 3;// nella seconda
//		else
//			c = 6;// nella terza
		//@formatter:on
		row = (row / 3) * 3;// migliore del codice precedente,
		col = (col / 3) * 3;// molto più sintetico
		// controllo del settore
		for(int i = row; i < row + 3; i++)
			for(int j = col; j < col + 3; j++)
				if(sudoku[i][j].getVal() == n)
					return false;
		return true;
	}

	public Cella[][][] getSolutions(){
		return possibiliSoluzioni;
	}

	public static String toString(Cella[][] m){
		StringBuilder sb = new StringBuilder(500);
		for(int i = 0; i < 9; i++){
			sb.append("|  ");
			for(int j = 0; j < 9; j++){
				if(j == m[0].length - 1){
					sb.append(m[i][j].toString());
					sb.append("  |");
					if(i == 2 || i == 5)
						sb.append("\n------------------+-----------------+------------------\n");
					else if(i != 8)
						sb.append("\n|                 |                 |                 |\n");
				}else{
					sb.append(m[i][j].toString());
					sb.append("  |  ");
				}
			}
		}
		return sb.toString();
	}

	public static void main(String[] args){
		int[][] a = new int[][]{{7, 3, 9, 1, 4, 2, 0, 8, 6}, {0, 5, 1, 9, 8, 6, 3, 4, 7}, {4, 6, 8, 0, 0, 0, 0, 0, 0}, {5, 1, 6, 0, 0, 7, 2, 3, 0}, {8, 4, 7, 2, 3, 5, 6, 1, 0}, {0, 0, 3, 0, 0, 0, 7, 5, 8}, {0, 0, 0, 0, 0, 8, 4, 7, 2}, {0, 8, 0, 0, 0, 0, 0, 6, 0}, {0, 0, 0, 5, 2, 3, 8, 9, 0}};
		Cella[][] s = new Cella[9][9];
		for(int i = 0; i < 9; i++)
			for(int j = 0; j < 9; j++){
				s[i][j] = new Cella(a[i][j]);
				if(a[i][j] != 0)
					s[i][j].setState(Cella.Stato.IMPOSTATO);
			}
		// for(int i = 0; i < 9; i++)
		// for(int j = 0; j < 9; j++)
		// s[i][j].setVal(0);
		SudokuSolver3 solver = new SudokuSolver3(s, 1);
		solver.risolvi();
		Cella[][][] soluzioni = solver.getSolutions();
		for(int i = 0; i < soluzioni.length; i++){
			System.out.println("Soluzione trovata " + (i + 1));
			System.out.println(toString(soluzioni[i]));
		}
	}
}