dovrei realizzare un algoritmo ricorsivo con backtrack che risolva un sudoku sia con valori preimpostati, sia completamente vuoto.
Ecco uno "skizzo" dell'algoritmo:
il problema è: non riesco ad impostare il caso di uscita e non capisco come fargli gerera tutte le soluzioni possibili... le ho provate davvero tutte...codice:public void riempi(int row, int col){ if(row > 8){ possibiliSoluzioni[count++] = sudoku;// salvo la soluzione corrente return; } if(sudoku[row][col].getVal() != 0)// se la cella è stata preassegnata... avanza(row, col); else{ for(int n = 1; n < 10; n++){// tenta tutti i numeri da 1 a 9 if(count == possibiliSoluzioni.length) return; else if(assegnabile(row, col, n)){ assegna(row, col, n);// e assegna il primo assegnabile avanza(row, col);// poi passa alla prossima cella } } // backtrack, si arriva qui solo se non è stata trovata una // soluzione valida della cella, quindi si ritorna nel for del chiamante deassegna(row, col); } } 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); } private void deassegna(int row, int col){ sudoku[row][col].setVal(0); } private boolean assegnabile(int row, int col, int n){ // controllo sulla riga for(int i = 0; i < sudoku[0].length; i++) if(sudoku[row][i].getVal() == n) return false; // controllo sulla colonna for(int i = 0; i < sudoku.length; 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; }
Rispondi quotando
