Algoritmo generazione Sudoku

[Javino89]

Ecco, dopo la grafica i problemi con la logica non potevano mancare. Quello della generazione/risoluzione di Sudoku è un problema ampio risolvibile in molti modi a quanto leggo. Comunque, un risolutore ce l'ho, e sto cercando di modificarlo per fare un generatore.

L'algoritmo che sto scrivendo per ora è così:

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) {
        
        int riga = -1;
        int colonna = -1;
        int risolto = 0;
        
        System.out.println();
        
        //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];
            
            //Estraggo un valore 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);
                
                //Ricorsione
                risolto = (vuote == 1) ? 1 : makeSudoku(sudoku, vuote - 1); 
                
                //Backtracking
                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");
        }
    }
}

In sostanza è una ricorsione con backtracking. Tramite una matrice di ArrayList mi mantengo tutti i valori che posso provare ad inserire all'interno di una cella.
L'algoritmo si blocca dopo 8 iterazioni. Ossia inserisce i primi 8 numeri nella prima riga, poi si impunta.

Non son sicuro di dover sempre rimuovere il valore inserito. In effetti da questo punto di vista si intuisce ad occhio che l'algoritmo è logicamente errato.

[Javino89]

Non esce mai dal while(risolto == 0)... lo schema ricorsivo per la semplice risoluzione prevede questa logica:

while(valore = 1; valore <= 9; risolto == 0; valore ++)

Però io devo inserire un elemento random per creare un sudoku diverso ogni volta.