Aiuto algoritmo generazione Sudoku

[Groove89]

Salve. So che in questa sezione si è già parlato molto di questo argomento, solo che le discussioni sono molto vecchie e non mi è sembrato il caso di riesumarle. Sto cercando di modificare un algoritmo per la risoluzione di un Sudoku con uno per la generazione. Per ora sto provando questo:

public class Sudoku {
	
	private ArrayList<Integer>[][] possibleValues = new ArrayList[9][9];
	private int[][] sudoku; 
	private int vuote = 81;
	
	public Sudoku() {		
		sudoku = new int[9][9];
		initPossibileValues();
		makeSudoku(sudoku,vuote);
	}
	
	private void initPossibileValues() {		
		for(int i = 0; i < possibleValues.length; i++) {
			for(int j = 0; j < possibleValues[i].length; j++) {
				possibleValues[i][j] = new ArrayList<Integer>();
				ArrayList<Integer> currentValues = possibleValues[i][j];
				for(int x = 1; x < 10; x++) {
					currentValues.add(x);
				}
			}
		}
	}
	
	private int makeSudoku(int[][] sudoku, int vuote) {
		
		System.out.println(vuote);
		
		int riga = -1;
		int colonna = -1;
		int risolto = 0;
		
		//Cerco una cella vuota da riempire
		for(int i = 0; i < 9 && riga == -1; i++) {
			for(int j = 0; j < 9 && riga == -1; j++) {
				//Abbiamo trovato la cella vuota, ci salviamo le coordinate
				if(sudoku[i][j] == 0) {
					riga = i;
					colonna = j;
				}
			}
		}	
		
		while(risolto == 0) {
			//Ottengo i possibili valori inseribili nella casella riga, colonna
			ArrayList<Integer> values = possibleValues[riga][colonna];
			//Ne estraggo uno random
			int randomIndex = (int)(Math.random() * values.size() - 1);
			//Valore candidato all'inserimento in posizione riga,colonna
			int valore = values.get(randomIndex);
			
			if(verificaInserimento(sudoku,valore,riga,colonna)) {
				
				sudoku[riga][colonna] = valore;
				//Ho aggiunto il valore, lo tolgo dalla lista delle possibilità
				values.remove(valore);
				
				risolto = (vuote == 1) ? 1 : makeSudoku(sudoku, vuote - 1); //ricorsione
				
				if(risolto == 0) {
					sudoku[riga][colonna] = 0;
					values.remove(valore);
				}
			}
		}
		
		return risolto;
	}
	
	private boolean verificaInserimento(int[][] sudoku, int valore, int riga, int colonna) {
		int rg= riga - riga % 3;
		int cg = colonna - colonna % 3; //coordinate del gruppo
		
		boolean risultato = true;
		
		//Verifico la riga
		for(int j = 0; j < 9; j++) {
			if(sudoku[riga][j] == valore) {
				risultato = false;
			}
		}
		
		//Verifico la colonna
		for(int i = 0; i < 9; i++) {
			if(sudoku[i][colonna] == valore) {
				risultato = false;
			}
		}
		
		//Verifico il gruppo
		for(int i = 0; i < 3; i++) {
			for(int j = 0; j < 3; j++) {
				if(sudoku[rg + i][cg + j] == valore) {
					risultato = false;
				}
			}
		}
		
		return risultato;
	}

	public void stampa() {
		for(int i = 0; i < sudoku.length; i++) {
			for(int j = 0; j < sudoku[i].length; j++) {
				System.out.print("\t" + sudoku[i][j]);
			}
			System.out.println("\n");
		}
	}
}

Da quello che si può vedere è un algoritmo ricorsivo con backtracking, in sostanza utilizziamo la forza bruta.
La mia idea per generare un Sudoku è di creare una matrice di ArrayList in cui ogni ArrayList all'inizio contiene i valori da 1 a 9, ossia quelli potenzialmente inseribili in quella cella, quindi:

1) Trova una cella vuota
2) Ottieni l'ArrayList dei valori possibili per quella cella
3) Estrai un valore a caso da questo ArrayList
4) Controlla se il valore estratto è inseribile nella cella
4) Se è inseribile rimuovi tale valore dalla lista dei valori possibili
per quella cella
5) Chiamata ricorsiva che controlla il numero di celle vuote
6) Se la strada non è praticabile, rimetti a 0 il valore nella matrice e rimuovi comunque il valore dalle possibilità della cella (backtracking)

L'algoritmo è ovviamente enormemente sbagliato (non si ferma mai) ma non sono molto pratico. Mi piacerebbe farlo funzionare per soddisfazione personale almeno, poi mi impegnerò ad utilizzare algoritmi migliori

Ps: credo di dover aggiungere qualche condizione nel while, perché credo che si blocchi dentro di esso dopo 9 chiamate ricorsive perché se provo a stampare all'inizio le celle vuote ottengo:
81
80
79
78
77
76
75
74
73