Programma che risolve sudoku

[Luffio]

Ciao a tutti. Tempo fa ho cominciato a creare un programma che risolve un sudoku in modo automatico, e facendo delle prove ero riuscito a farlo funzionare con schemi di livello facile e medio, mentre avevo difficoltà con quelli di livello difficile. Adesso è qualche giorno che ho ripreso in mano il programma con l'intento di completarlo! (Sto anche praticamente riscrivendo l'intero codice semplificando la base dati perchè avevo usato una mappatura troppo complicata da capire e probabilmente è per questo che non mi veniva )

Ad ogni modo, chiedo gentilmente agli amanti del sudoku che frequentano questo forum (spero ce ne siano abbastanza) di aiutarmi a elencare TUTTI GLI ALGORITMI che un normale solutore utilizzerebbe, dal più facile al più difficile. Questo mi aiuterebbe sia a vedere se esistono metodi più facili di quelli che uso io, sia a rendermi conto se conosco tutti i modi possibili di risolvere un sudoku.

Grazie per la collaborazione

[dreadnaut]

Ottimo articolo a riguardo, spiega tre possibili metodi. Include sorgenti, etc.

[Luffio]

Grazie dreadnaut, ho trovato l'articolo davvero interessante, anche se non serve esattamente ai miei scopi :D
...cioè, come funziona il programma con la webcam mi è piaciuto, anche come è spiegato con le immagini, però quei 3 metodi non mi sono molto utili: il metodo 2 e 3 vanno bene ma risolvono solo un sudoku di livello facile e "forse" medio; il metodo della forza bruta ovviamente non è il più indicato per la ovvia lentezza del processo, nonché il fatto che è più adatto ai computer mentre io volevo i metodi che un solutore UMANO userebbe. ;)

PS: non ho scaricato il codice perchè richiede la registrazione

[dreadnaut]

Codeproject è un ottimo sito su cui essere registrati, meglio di Facebook probabilmente.

I metodi che usa, messi assieme come spiegato in fondo all'articolo, risolvono sudoku in pochi microsecondi. Se non ti vanno bene e pensi di poter fare di meglio, beh, chiedere aiuto su un forum non credo ti sia di alcuna utilità

I metodi usati da una persona sono varianti del secondo e del terzo, con un po' di intuizione e tirare a caso qua e la, che non hanno però a disposizione un memoria estesa e precisa come può fare l'algoritmo. Non credo che implementarli di porterebbe alcun vantaggio. Il sudoku non è un rompicapo che richieda soluzioni interessanti (è solo un CSP), è facilmente risolvibile e quindi "rompicapo" solo perché non possiamo tenere a mente sufficienti informazioni.

[Luffio]

Cercherò di farmi capire meglio.

Il mio programma, oltre che risolvere un sudoku, vuole anche essere di "apprendimento/esercizio", illustrando -all'utente che lo desidera- la soluzione passo-passo, con tanto di spiegazione del perchè un certo numero è stato messo lì o perchè non può essere messo là. Quindi non mi interessano i microsecondi, a me interessano quelle "varianti" che hai citato tu. ^_^

[dreadnaut]

Allora implementa i metodi di cui sopra, ma limita le posizioni di cui l'algoritmo può tenere traccia, prima di cambiare idea e fare backtracking. Otterrai un algoritmo un po' rotto che potrebbe sembrare una persona