Una regola del Sudoku: l'unicità di soluzione.
Quando risolviamo un sudoku sappiamo che una delle regole è che la griglia iniziale possa dare UNA UNICA soluzione. C'è una regola matematica per verificare questo: cioè che abbia una UNICA soluzione, prima di risolverlo?
Risposte
Posso dirti con certezza che un sudoku per avere una sola soluzione deve avere ALMENO 8 numeri già presenti. Per il resto non credo che prima di risolverlo puoi dire se la soluzione è una o no.
Ti assicuro che ciò è possibile: ci sono alcuni siti che permettono di verificare questo (uno è : http://www.abcroma.com/SudokuImmissione.asp). Digiti i numeri e ti dice immediatamente se ha una o più soluzioni. L'ho verificato ed è vero... chissà che calcola fa...
Bè.. eheh l'algoritmo non ci mette niente a risolverlo e allo stesso tempo vedere se la soluzione è univoca.. Penso prorpio che l'unicità della soluzione la verifica nel tempo stesso in cui lo risolve. Poi che la soluzione finale ti viene mostrata dopo è un altro discorso.
E' la disposizione dei numeri della griglia iniziale che determina l'unicità della soluzione finale. Se i numeri di aiuto per risolvere il sudoku è errata, il solutore si ritrova ad avere più soluzioni.
Sì, oppure nessuna.
Dall'ultima tua risposta si deduce che non hai afferrato il problema. Lasciamo perdere. C'è qualcun'altro che mi sa rispondere? Grazie
Veramente non ho capito qual era la richiesta nel tuo penultimo messaggio.. Hai detto una cosa giusta e amen, ma io prima ti avevo scritto che molto probabilmente il programma rileva se un sudoku ha più soluzioni o meno nel momento stesso in cui lo risolve e non prima di risolverlo.. Poi chiaramente a te i tentativi di risoluzione non vengono mostrati graficamente, ma vedi solo la soluzione finale se è unica.
"xXStephXx":
Posso dirti con certezza che un sudoku per avere una sola soluzione deve avere ALMENO 8 numeri già presenti. Per il resto non credo che prima di risolverlo puoi dire se la soluzione è una o no.
questo è falso. Posso trovarti un sudoku che ha 8 numeri ma che non ha una soluzione unica.
Ad esempio un sudoku che ha 8 numeri sulla stessa cella/riga/colonna ha milioni di possibili soluzioni
8 numeri sono sufficienti solo se sono disposti su colonne/righe/celle diverse.
Si esiste una regola che permette di sapere in anticipo l'unicità del sudoku, a mio tempo ho scritto programmini in C che risolvevano vari tipi di sudoku. E anche in grado di crearli casualmente. (ho poi provato a trasporli in C++ ma mi sono stufato e ho lasciato a metà) Non so se esiste una dimostrazione matematica per ciò. Ma puoi stare certo che se crei un sudoku e rimouvi i numeri seguendo regole precise la soluzione sarà sempre unica.
Aspetta aspetta, forse mi sono espresso male o forse sono stato un po' impreciso.. Quello che volevo dire è che per far sì che un sudoku potrebbe avere un'unica soluzione è necessario che ci siano almeno 8 numeri già inseriti. In altre parole: Se un sudoku ha meno di 8 numeri pre-inserinti è impossibile che la soluzione sia unica.
Su questo invece concordo 
. Ti interesserà estendere il ragionamento a sudoku con celle elementari composte da altri quadrati (4, 16, 25 etc.)
. Ti interesserà estendere il ragionamento a sudoku con celle elementari composte da altri quadrati (4, 16, 25 etc.)
Da diversi anni ho realizzato una pagina che permette di giocare a sudoku ( http://www.secerchitrovi.com/sudoku/)
Ho dovuto studiare un metodo per determinare se la soluzione proposta è unica o meno. Ho anche verificato che non controllando tale situazione si generano quasi sempre sudoku con più soluzioni.
Dopo aver creato uno schema casuale, in base al livello di difficoltà rendo bianche più o meno caselle. Affinché la soluzione sia unica:
- per ogni quadrante guardo i 4 quadranti della stessa riga e colonna
- per i quadranti della stessa riga, confronto ogni colonna del quadrante corrente (3 colonne) con tutte le colonne degli altri 2 quadranti (6 colonne)
- in ognuna delle 3 colonne non può esistere una permutazione con 2 o 3 numeri presente anche in una delle altre 6 colonne in cui tutti i numeri siano lasciati in bianco. Nel caso in cui la permutazione sia con 2 numeri, almeno 1 dei 4 numeri non deve essere bianco, nel caso in cui siano 3, almeno 2 numeri della stessa colonna (sui 6 numeri totali) non devono essere bianchi.
- per i quadranti della stessa colonna, confronto ogni riga del quadrante corrente (3 righe) con tutte le righe degli altri 2 quadranti (6 righe)
- in ognuna delle 3 righe non può esistere una permutazione con 2 o 3 numeri presente anche in una delle altre 6 righe in cui tutti i numeri siano lasciati in bianco.
Ho dovuto studiare un metodo per determinare se la soluzione proposta è unica o meno. Ho anche verificato che non controllando tale situazione si generano quasi sempre sudoku con più soluzioni.
Dopo aver creato uno schema casuale, in base al livello di difficoltà rendo bianche più o meno caselle. Affinché la soluzione sia unica:
- per ogni quadrante guardo i 4 quadranti della stessa riga e colonna
- per i quadranti della stessa riga, confronto ogni colonna del quadrante corrente (3 colonne) con tutte le colonne degli altri 2 quadranti (6 colonne)
- in ognuna delle 3 colonne non può esistere una permutazione con 2 o 3 numeri presente anche in una delle altre 6 colonne in cui tutti i numeri siano lasciati in bianco. Nel caso in cui la permutazione sia con 2 numeri, almeno 1 dei 4 numeri non deve essere bianco, nel caso in cui siano 3, almeno 2 numeri della stessa colonna (sui 6 numeri totali) non devono essere bianchi.
- per i quadranti della stessa colonna, confronto ogni riga del quadrante corrente (3 righe) con tutte le righe degli altri 2 quadranti (6 righe)
- in ognuna delle 3 righe non può esistere una permutazione con 2 o 3 numeri presente anche in una delle altre 6 righe in cui tutti i numeri siano lasciati in bianco.
Piccola nota:
man mano si amplia il numero di riquadri più difficile sarà trovare una soluzione in tempi umani.
se il sudoku standard ha $9$ celle in altezza e $3$ riquadri perciò $3x3$ celle e $3^2x3^2$ riquadri.
Generalizzando ad $n$, l'algoritmo che risolve il problema del sudoku $n^2xn^2$ ci metterà tempo superpolinomiale, perciò non si troverà una soluzione nel breve termine, e che sia unica o meno non importa.
"Vitalluni":
Ti interesserà estendere il ragionamento a sudoku con celle elementari composte da altri quadrati (4, 16, 25 etc.)
man mano si amplia il numero di riquadri più difficile sarà trovare una soluzione in tempi umani.
se il sudoku standard ha $9$ celle in altezza e $3$ riquadri perciò $3x3$ celle e $3^2x3^2$ riquadri.
Generalizzando ad $n$, l'algoritmo che risolve il problema del sudoku $n^2xn^2$ ci metterà tempo superpolinomiale, perciò non si troverà una soluzione nel breve termine, e che sia unica o meno non importa.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo