Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
SudokuSolver

SudokuSolver

19121_size.jpg
Questo programma risolve ogni possibile griglia del sudoku e mostra la soluzione, non è stato progettato per giocare, solo risolvere!
Credo che sia abbastanza intuitivo: la celletta blu chiaro indica la cella selezionata, per inserire i numeri usate la tastiera, se il numero che cercate di inserire non viene visualizzato vuol dire che lo stesso numero è già presente nella riga, colonna o quadrato 3x3, se il numero venisse inserito sarebbe contro le regole del sudoku. Per cambiare la cella selezionata potete cliccare con il mouse sulla nuova cella, oppure più comodamente usare i tasti freccia. Per cancellare il contenuto di una cella selezionate la e cliccate il tasto '0' oppure backspace, cancel o spazio.
Per risolvere il sudoku vengono usati 3 potenti algoritmi: il primo lavora per scelte obbligate, si crea una lista di tutti i possibili valori che possono andare in una cella e quando trova una cella dove può andare solo un valore allora lo inserisce lì e ricomincia da capo. Se il primo non è stato sufficiente a risolvere il sudoku interviene ip secondo che lavora per esclusione: se in una riga, colonna o quadrato 3x3 esiste una e una sola cella che può contenere un numero allora viene inserito lì e si ritorna all'inizio (al primo algoritmo). I sudoku medi e semplici a questo punto sono stati risolti, ma per quelli più difficili esiste un terzo algoritmo:  brute force, a differenza degli altri due che collaborano lui lavora da solo e conta il numero di soluzioni perchè prova sole tutte potrebbe trovarne anche più di una, ovviamente se ne trova più di una avete sbagliato la griglia! Viene fatto uso di una funzione ricorsva che richiama se stessa per aggiungere ogni volta un numero se sbaglia salta direttamente a quello successivo per e itare calcoli inutili e quando non c'è più nulla da aggiungere verifica la soluzione e la riporta sulla griglia. È importante che la brute force non sia da sola poichè maggiore è il numero di celle bianche minore è l'efficienza, quindi è meglio che si trovi una griglia con qualche valore già inserito.
Vi è anche un immagine che contiene un sudoku di esempio, il più difficile che fin ora ho fatto provare al software e trova la soluzione in un tempo relativamente breve.
Proprio perchè la brute force diventa estremamente lenta all'aumenteade delle celle bianche sconsiglio vivamente di inserire pochi numero ammenochè non stiate seguendo una griglia.


Categoria: Matematica e fisica / C
Piattaforma:

Downloads: 665
Rating: (2 voti)
Data: 27/04/2012
Download

A proposito dell'autore

Ho una conoscenza media del vb.net, una medio-Bassa del C#, studio sia C che C++ da due anni, conosco mediamente le api di Windows e OpenGL.

Aggiungi un commento

Inserisci il tuo commento qui
Esegui il login oppure registrati per inviare commenti
  • ottimo programma, bell'interfaccia grafica..
    l'unico problema è quando si inserisce una griglia con troppe caselle vuote il programma non risponde più..
    inoltre  si può inserire i valori solo con i tastierini numerici sopra alle lettere e non quelli a destra