[Java]Risolutore sudoku

[tonio123]

Allora ho realizzato un programmino in java che risolve sudoku sfruttando questo algoritmo:
1)ogni casella all'inizio ha 9 valori possibili a meno che non le sia già stato assegnato un valore
2)scorro tutte le caselle togliendo ad ognuna i valori che non può avere perché già presenti nella sua riga/colonna/riquadro
3)se ad una casella rimane 1 solo valore possibile allora quello diventa il suo valore
4)se una casella è l'unica nella sua riga/colonna/riquadro che può assumere un certo valore lo assume
5)riparte dal punto 2 finché non fa un ciclo a vuoto, cioè senza cambiare valore a nessuna casella

In teoria così dovrei poter ottenere sempre una soluzione e in effetti con i sudoku medio/facili funziona, con quelli classificati come difficili invece non riesce a raggiungere una soluzione e rimane un 50% di caselle in bianco.
Quindi arrivando alla domanda, il mio algoritmo è incompleto/sbagliato?
Cioè senza ricorrere alla forza bruta randomizzando numeri c'è un modo per ottenere sempre una soluzione?

[sottovento]

Allora ho realizzato un programmino in java che risolve sudoku sfruttando questo algoritmo:
1)ogni casella all'inizio ha 9 valori possibili a meno che non le sia già stato assegnato un valore
2)scorro tutte le caselle togliendo ad ognuna i valori che non può avere perché già presenti nella sua riga/colonna/riquadro
3)se ad una casella rimane 1 solo valore possibile allora quello diventa il suo valore
4)se una casella è l'unica nella sua riga/colonna/riquadro che può assumere un certo valore lo assume
5)riparte dal punto 2 finché non fa un ciclo a vuoto, cioè senza cambiare valore a nessuna casella

In teoria così dovrei poter ottenere sempre una soluzione e in effetti con i sudoku medio/facili funziona, con quelli classificati come difficili invece non riesce a raggiungere una soluzione e rimane un 50% di caselle in bianco.
Quindi arrivando alla domanda, il mio algoritmo è incompleto/sbagliato?
Cioè senza ricorrere alla forza bruta randomizzando numeri c'è un modo per ottenere sempre una soluzione?


Quando ho tempo libero, gioco al sudoku. Non sono un esperto, ma mi piace cimentarmi con quelli medio/difficili.
Le regole che hai inserito sono ottime, ma non sufficienti, perche' per i puzzle piu' difficili devi "guardare avanti" di qualche mossa.

Puoi cominciare inserendo qualche regola in piu', per esempio:
- Supponi di avere 3 caselle libere in un riquadro 3x3. Nelle prime due caselle puoi inserire, per esempio, i numeri 5, 7 mentre nella terza casella puoi inserire i numeri 5, 7, 8 (cioe' un sovrainsieme dei precedenti).
Evidentemente potrai mettere il numero 8 nella terza casella, giusto?

In questo caso, seguendo le tue regole non potevi inserire alcun numero; in realta', potevi completare una casella. Si possono trovare altre regole di questo tipo.

[tonio123]

Quando ho tempo libero, gioco al sudoku. Non sono un esperto, ma mi piace cimentarmi con quelli medio/difficili.
Le regole che hai inserito sono ottime, ma non sufficienti, perche' per i puzzle piu' difficili devi "guardare avanti" di qualche mossa.

Puoi cominciare inserendo qualche regola in piu', per esempio:
- Supponi di avere 3 caselle libere in un riquadro 3x3. Nelle prime due caselle puoi inserire, per esempio, i numeri 5, 7 mentre nella terza casella puoi inserire i numeri 5, 7, 8 (cioe' un sovrainsieme dei precedenti).
Evidentemente potrai mettere il numero 8 nella terza casella, giusto?

In questo caso, seguendo le tue regole non potevi inserire alcun numero; in realta', potevi completare una casella. Si possono trovare altre regole di questo tipo.
mm forse non ho capito bene, praticamente stai dicendo che se ho da completare solo 3 caselle in una riga/colonna/riquadro tali che:
1-->valori possibili:5,6
2-->valori possibili:5,6
3-->valori possibili:5,6,7
allora devo mettere la 3 al valore 7, se è così lo faccio già poiché la 3 è l'unica che può essere 7 e corrisponderebbe al passo 4 di quelli che ho scritta prima.
ma penso proprio di non aver capito

[sottovento]

mm forse non ho capito bene, praticamente stai dicendo che se ho da completare solo 3 caselle in una riga/colonna/riquadro tali che:
1-->valori possibili:5,6
2-->valori possibili:5,6
3-->valori possibili:5,6,7
allora devo mettere la 3 al valore 7, se è così lo faccio già poiché la 3 è l'unica che può essere 7 e corrisponderebbe al passo 4 di quelli che ho scritta prima.
ma penso proprio di non aver capito

Puoi trovare anche altre regole, te ne serve qualcuna in piu' per riuscire a risolvere tutti i possibili sudoku (ammesso che li abbiano creati in modo che si possano sempre risolvere, non so se esiste una regola).

Quello che dicevo e': hai un insieme di due caselle e hai determinato che in quelle caselle ci puo' stare il 5 ed il 6, ma non sai in quale ordine.
A questo punto, hai la fortuna di poter avere un SOVRAINSIEME delle stesse, cioe' tre caselle (le prime due caselle, piu' una terza). Ti accorgi che nel sovrainsieme i possibili numeri che ci possono stare sono 5,6,7. Domanda: dove andra' il 7? Ovviamente nella 3^ casella, anche se nella terza avrebbe potuto starci anche il 5 ed il 6...

Se vuoi, puoi anche pensare (per i puzzle veramente difficili) un sistema di "backtrack": hai applicato tutte le regole che conosci ma non sei riuscito a finire. Beh, allora fai un "tentativo ragionato", mettendo un numero (beh, saranno sempre due) in una posizione ragionevole e tentando la risoluzione. Se non risulta, puoi cancellare tutti i numeri fino al punto di backtrack e tentare una seconda volta...

[marco.r]

Allora ho realizzato un programmino in java che risolve sudoku sfruttando questo algoritmo:
1)ogni casella all'inizio ha 9 valori possibili a meno che non le sia già stato assegnato un valore
2)scorro tutte le caselle togliendo ad ognuna i valori che non può avere perché già presenti nella sua riga/colonna/riquadro
3)se ad una casella rimane 1 solo valore possibile allora quello diventa il suo valore
4)se una casella è l'unica nella sua riga/colonna/riquadro che può assumere un certo valore lo assume
5)riparte dal punto 2 finché non fa un ciclo a vuoto, cioè senza cambiare valore a nessuna casella

In teoria così dovrei poter ottenere sempre una soluzione e in effetti con i sudoku medio/facili funziona, con quelli classificati come difficili invece non riesce a raggiungere una soluzione e rimane un 50% di caselle in bianco.
Quindi arrivando alla domanda, il mio algoritmo è incompleto/sbagliato?
Cioè senza ricorrere alla forza bruta randomizzando numeri c'è un modo per ottenere sempre una soluzione?
Con una semplice estensione al tuo algoritmo si puo' ottenerne uno che ottiene la soluzione in tempi molto rapidi.
In pratica quando non trovi nessuna casella con una soluzione possibile, ne prendi una con due e scegli uno dei due valori, se non raggiungi una soluzione torni indietro con l'altra strada. se non ci sono caselle con due valori ne prendi una da tre e cosi' via.
All'atto pratico funziona abbastanza bene.
Comunque se cerchi nel forum c'e' un vecchio contest in cui ci si cimentava nello scrivere solutori per sudoku, troverai diverse idee interessanti.

[banryu79]

Quoto marco.r, con un algoritmo brute force + backtracking.
Ed eccoti il link al vecchio contest sul sudoku.
http://www.hwupgrade.it/forum/showthread.php?t=1995326

[marco.r]

Quoto marco.r, con un algoritmo brute force + backtracking.
Ed eccoti il link al vecchio contest sul sudoku.
http://www.hwupgrade.it/forum/showthread.php?t=1995326
Il concetto e' che all'atto pratico provare tutte le varie euristiche ha un suo costo in termini di cicli di cpu. Se l'esplorazione dell'albero delle scelte non va mai piu' di tanto in profondita', puo' essere meno costoso fare un paio di prove e scegliere la strada giusta.
Questo a patto di scegliere le alternative in modo intelligente (quella con la minor probabilita' di essere sbagliata), e impostando la struttura dati in modo che il "costo" per fare un tentativo sia molto basso.
Se guardi il mio esempio, riesce a risolvere in pochi millisecondi anche i sudoku piu' difficili elencati sulla pagina di wikipedia

http://en.wikipedia.org/wiki/Algorithmics_of_sudoku#Exceptionally_difficult_Sudokus_.28hardest_Sudokus.29

[banryu79]

Il concetto e' che all'atto pratico provare tutte le varie euristiche ha un suo costo in termini di cicli di cpu. Se l'esplorazione dell'albero delle scelte non va mai piu' di tanto in profondita', puo' essere meno costoso fare un paio di prove e scegliere la strada giusta.

Immagino parli di questo:

In pratica quando non trovi nessuna casella con una soluzione possibile, ne prendi una con due e scegli uno dei due valori, se non raggiungi una soluzione torni indietro con l'altra strada. se non ci sono caselle con due valori ne prendi una da tre e cosi' via.

e ok, sono d'accordo che è un'algoritmo più efficente.

Intendevo dire che per giungere a una soluzione è sufficiente introdurre il backtracing. Anche col backtracking si riesce a risolvere qualsiasi schema sudoku corretto, non importa quando sia "hard".
Certo il tuo algoritmo è più intelligente ed efficente.

[marco.r]

Immagino parli di questo:

e ok, sono d'accordo che è un'algoritmo più efficente.

Intendevo dire che per giungere a una soluzione è sufficiente introdurre il backtracing. Anche col backtracking si riesce a risolvere qualsiasi schema sudoku corretto, non importa quando sia "hard".
Certo il tuo algoritmo è più intelligente ed efficente.

Ah ma non stavo criticando il tuo intervento :D, era che ho premuto quote invece che rispondi, ma stiamo dicendo la stessa cosa :D.
La mia soluzione e' proprio bruteforce+backtracking, volevo solo elaborare sull'argomento e spiegare perche' funziona bene.

[banryu79]

La mia soluzione e' proprio bruteforce+backtracking, volevo solo elaborare sull'argomento e spiegare perche' funziona bene.

Ok di nuovo: la differenza è che io nel contest non ho postato una soluzione al problema (il contest era relativo ad un solutore di schemi validi ma incompleti) invece avevo postato un generatore di schemi validi (usando lo stesso algoritmo, bf + backtracking).