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