Scusa Snuffz era da una vita che non guardavo questa sezione...
Il tuo programma non esiste (collegamento mancante), ma immagino che faccia tutto e di piu' del mio. Se ti interessa te lo spedisco lo stesso (devo spedirtelo perche' 7ede la pass non me la vuole proprio far sapere...), ma penso che ti interessi di piu' sapere come funziona.
-
Come risolve un sudoku:
Parte con una lista di 81 liste, dove ogni lista contiene i valori che la casella corrispondente puo' assumere (omg non capisco gia' piu' niente...).
Qui inizia il ciclo che continua fino alla risoluzione completa, ossia quando tutte le liste hanno lunghezza 1.
a) Se una casella puo' assumere un valore solo (ad es tutte le celle che hanno il valore dato dal problema iniziale), il suo valore viene tolto da tutte le caselle che fanno parte della sua riga, della sua colonna e del suo quadrato.
b) Se in un quadrato, in una riga o in una colonna c'e' solo una casella che puo' assumere un certo valore, tale valore le viene assegnato (e scatta automaticamente il punto a).
c) Se sia a) che b) non possono risolvere piu' niente, una (qualsiasi) delle caselle che puo' assumere meno valori li assume tutti, uno alla volta.
Si torna a provare a) e b), e se caso si fa ancora c) finche' non si puo' piu' fare niente: se si trova una soluzione la si scrive nello schema, se invece c'e' un conflitto (si trova una casella che non puo' assumere alcun valore), si torna indietro fino ad un punto c) e si prova con un altro valore per quella casella.
(Se sai cos'e la
recursione e' semplice.)
Questo metodo si basa sul
back-tracking, il pc prova tutte le strade finche' una non lo porta alla fine. Ci sarebbero anche ragionamenti piu' sofisticati da fare e aggiungere ad a) e b) prima di fare c) (tipo se ci sono due caselle nella stessa riga che solo loro possono assumere 2 valori, togliere tali valori come possibili per le altre caselle di quella riga), ma i test da fare sarebbero troppi rispetto al numero di possibilita' che vengono scartate.
Il mio programma assegna un livello di difficolta' ai sudoku, relativo al numero di recursioni che necessita per risolverlo.
Spero che si capisca altrimenti non esitate a chiedere!
-
Come generare un sudoku:
Parte dalla soluzione: crea un sudoku (risolto) il piu' possibile a caso. Ciclo fino a sudoku completo: prende una casella con valore non ancora assegnato qualsiasi e le assegna un valore qualsiasi tra quelli che puo' assumere (se il sudoku non puo' piu' essere risolto dopo l'assegnamento, un'altro valore viene testato).
Una volta che si ha il sudoku finito, si procede all'inverso.
Per ottantun volte si prende una casella (che non sia gia' stata scelta) a caso, le si toglie il valore fisso e si prova a risolvere il sudoku: se la soluzione e' ancora una sola, la casella viene sbiancata; se invece ci sono piu' soluzioni, quel numero e' indispensabile e viene riassegnato a quella casella, e si passa a testarne un'altra.
Le prime testate "perdono" praticamente sempre il loro valore, le ultime mai: per questo e' importante testarle in ordine casuale. Se si vuole un sudoku bizzarro, ad esempio con la prima riga completamente vuota, si possono testare le caselle seguendo il loro ordine "geografico".
Forse dovreste pagarmi per queste idee...