algoritmi risoluzione Sudoku

[g.b99pm10]

Buongiorno, non so se ho fatto bene a inserire questa discussione nel forum Java perchè in realtà il mio problema non è esattamente collegato al linguaggio, più che altro è relativo al Sudoku.
Per familiarizzare con il linguaggio, specialmente con gli elementi grafici, gli eventi ecc... ho deciso di scrivere una piccola applicazione che possa risolvere i sudoku. Ho fatto in questo modo:
Ho creato la classe Cella che estende JTextField, infatti un oggetto Cella rappresenta una delle 81 celle del Sudoku. Come metodi, oltre ai costruttori, ho inserito controllaRighe(), controllaColonne() e controllaQuadrante(). Ogni cella ha un vector di 9 elementi che rappresentano i 9 possibili numeri che possono essere inseriti nella cella. i metodi sopra indicati hanno il compito di cercare dei valori sicuri nella riga, nella colonna e nel qudrante di ogni cella eliminando questi numeri dal vector dei possibili numeri. Una volta che nel vector è rimasto un solo numero, esso diventerà il numero certo. Utilizzando questo metodo sono riuscito a risolvere i sudoku facili e medi, ma appena ho provato con quelli difficili.... il programma ha raggiunto solo pochi numeri sicuri.... quindi non so come andare avanti . Ho pensato ad andare a caso provando tutte le possibilità, ma ce ne sono troppe, ci metterebbe ore . Qualche consiglio in merito?

[valia]

un consiglio, pensa inizialmente indipendentemente dalla grafica (non serve): l'algoritmo di risoluzione ha come input e come output un qualcosa che decidi di mandare in grafica, non in grafica.

detto questo, la logica che hai seguito va bene per i medi/facili, non va bene per i difficili in cui con carta e penna ragioni con "in quella colonna è sicuro che vanno 2 numeri, non so dove, ma in questo modo li escludi dalle altre celle".
diciamo che un diverso approccio risolutivo ti aiuterebbe.
Qui ho trovato un approccio:

http://www.math.cornell.edu/~mec/Sum..._Sudoku_I.html

ma cercando sicuramente ne trovi altri

[g.b99pm10]

Grazie mille per la risposta. Leggendo la pagina che mi hai consigliato ho notato che l'autore utilizza fin dall'inizio il metodo "a tentativi" ovvero provando tutte le possibili combinazioni fino ad ottenerne una che non violi le regole del Sudoku. Purtroppo, volendo risolvere anche i Sudoku diabolici in un tempo che non superi i 5 secondi, la sua tecnica da sola non potrebbe funzionare:

The Sudoku solver took about 5 minutes to come up with the following solution:

Quindi ho deciso di fondere la mia tecnica (aggiungendo degli algoritmi che non tentino tutte le probabilità) con l'algoritmo utilizzato dall'autore della pagina.

Credo che oltre ai 3 metodi che avevo scritto per il controllo delle righe colonne e quadranti, aggiungerò il tuo

in quella colonna è sicuro che vanno 2 numeri, non so dove, ma in questo modo li escludi dalle altre celle".

e quello per cui se in una riga c'è una casella che ha un numero possibile che le altre caselle non hanno, allora quel numero sarà il numero definitivo di quella cella, in quanto non può andare in nessun'altra nella riga.

Utilizzando questi due nuovi algoritmi + andando a Random, dovrei riuscire ad ottenere la risoluzione in tempi consoni.

Vi faccio sapere se funziona

ciao e grazie ancora

[valia]

ti ripeto, io ti ho dato solo uno dei primi che ho trovato usando google, ovvio che ce ne sono di migliori.
Attendo tue nuove,

[g.b99pm10]

aggiungendo l'algoritmo "se in una riga c'è una casella che ha un numero possibile che le altre caselle non hanno, allora quel numero sarà il numero definitivo di quella cella, in quanto non può andare in nessun'altra nella riga."
incredibilmente si risolvono i difficili e i diabolici (ne ho provati 1 difficile e 1 diabolico). Inoltre ho eseguito il controllo solo su righe e colonne, ancora non ho inserito quello sul quadrante... pensavo fosse moolto più lungo il discorso adesso provo a fare tanti diabolici e vedo se bastano questi algoritmi o ne devo mettere altri.

Grazie per la consulenza

ciao

[g.b99pm10]

Scusate se riapro il post... per quelli che ne hanno bisogno:
con un algoritmo BackTrack si risolvono i sudoku intorno ai 2.216 secondi(tempo di esecuzione del sudoku "più difficile del mondo" http://www.focus.it/tecnologia/digit...do-123-6132-81).

Non è dunque necessario utilizzare gli algoritmi che avevo scritto inizialmente.

[MacApp]

Scusate se riapro il post... per quelli che ne hanno bisogno:
con un algoritmo BackTrack si risolvono i sudoku intorno ai 2.216 secondi(tempo di esecuzione del sudoku "più difficile del mondo" http://www.focus.it/tecnologia/digit...do-123-6132-81).

Non è dunque necessario utilizzare gli algoritmi che avevo scritto inizialmente.

Ciao qui puoi trovare una versione in C/C++ da linea di comando che lo risolve in meno di 13 centesimi di secondo, a discesa ricorsiva esaustiva:
https://github.com/isghe/sudoku

$ uname -a
Darwin isghe-MacBook-Pro-3.local 13.3.0 Darwin Kernel Version 13.3.0: Tue Jun  3 21:27:35 PDT 2014; root:xnu-2422.110.17~1/RELEASE_X86_64 x86_64
$ time ./sudoku.out example/focus.sdk 
main: isi::GetGnuVersion (): 4;
__FILE__: main.cpp;
__DATE__: Jun 26 2014;
__TIME__: 14:00:04;
main: isi::BoolToStr (isi::IsDebugVersion ()): false;
my_main: theFileName: example/focus.sdk;
my_main: std::count_if (aCell, aCell + kDim * kDim, IsInitValue): 23;
aRow:
    0,     0,     5,     3,     0,     0,     0,     0,     0, 
    8,     0,     0,     0,     0,     0,     0,     2,     0, 
    0,     7,     0,     0,     1,     0,     5,     0,     0, 
    4,     0,     0,     0,     0,     5,     3,     0,     0, 
    0,     1,     0,     0,     7,     0,     0,     0,     6, 
    0,     0,     3,     2,     0,     0,     0,     8,     0, 
    0,     6,     0,     5,     0,     0,     0,     0,     9, 
    0,     0,     4,     0,     0,     0,     0,     3,     0, 
    0,     0,     0,     0,     0,     9,     7,     0,     0, 
HandleNextRecursive: aCurrentSolution: 1;
HandleNextRecursive: gNumOfCall: 31033;
HandleNextRecursive: static_cast <double >(gNumOfCall)/aCurrentSolution: 31033;
theRowVector:
    1,     4,     5,     3,     2,     7,     6,     9,     8, 
    8,     3,     9,     6,     5,     4,     1,     2,     7, 
    6,     7,     2,     9,     1,     8,     5,     4,     3, 
    4,     9,     6,     1,     8,     5,     3,     7,     2, 
    2,     1,     8,     4,     7,     3,     9,     5,     6, 
    7,     5,     3,     2,     9,     6,     4,     8,     1, 
    3,     6,     7,     5,     4,     2,     8,     1,     9, 
    9,     8,     4,     7,     6,     1,     2,     3,     5, 
    5,     2,     1,     8,     3,     9,     7,     6,     4, 
HandleNextRecursive: BoolToStr (IsGoodSolution (theSchema)): true;
my_main: isi::gNumOfCall: 1329262;
my_main: isi::gNumOfSolution: 1;
main: rit: 0;
main: std::clock () - aStart: 128584;


real    0m0.134s
user    0m0.127s
sys    0m0.005s