Risolutore di Sudoku



Sono rimasto incuriosito dal gioco del Sudoku per un motivo molto semplice.. è un gioco molto stupido che viene esaltato in un modo incredibile. Non nego che per risolverlo velocemente sia necessario anche, qualche volta, un buon colpo d'occhio per identificare velocemente la mossa migliore da fare, ma, come risulta evidente con un minimo di analisi la strategia di risoluzione è molto semplice e "meccanica". Altri giochi "da scacchiera" hanno regole semplici come il nostro Sudoku ma non per questo hanno una strategia risolutiva così banale.

In cosa consiste la strategia risolutiva? semplicemente in quello che c'è scritto sul Corriere della Sera nella pagina che si occupa di questo gioco: nell'identificare la casella nella quale è possibile inserire solo una cifra delle nove disponibili, identificare cioè la cella con la "mossa obbligata". Una volta fatta tale mossa, automaticamente, per la presenza di un numero in più nel quadrato, altre mosse saranno vietate e dunque una seconda cella diventerà la cella con una sola possibilità reiterando dall'inizio il gioco fino al completamento di tutte le 81 caselle. Il problema nasce quando non c'è una cella con la mossa obbligata ma solo celle con 2 o più mosse possibili. In questo caso, si prova la prima possibilità e si procede nel gioco. se si arriva ad un vicolo cieco si torna inetro e si prova la seconda possibilità e poi la terza... fino a trovare quella giusta. Quindi, come consiglia il Corriere della Sera, matita e gomma per scrivere e cancellare continuamente numeri!

Il vero problema del gioco è, a mio parere, il fatto che non ci sono "trucchi": è esattamente semplice come appare.
Intendo questo: conoscete per esempio il gioco della "Settimana Enigmistica" che si chiama "Calcolo .... Enigmatico"? Questo rompicapo consiste nel sostituire a dei simboli delle cifre. A simbolo uguale corrisponde cifra uguale. La soluzione si ottiene quando tutte le operazioni matematiche rappresentate (somme, sottrazioni, moltiplicazioni e divisioni) sono corrette. In questo gioco si può procedere in due modi: o come il Sudoku, provando e riprovando le varie cifre al posto di ogni simbolo, utilizzando cioè la forza bruta, oppure guardando con attenzione le operazioni aritmetiche e la composizione dei simboli e utilizzando dei trucchetti. Uno dei truccehtti più banali è: se se l'ultimo simbolo (cifra) di un addendo è uguale all'ultimo simbolo (cifra) della somma, molto probabilmente l'ultimo simbolo del secondo addendo rappresenta uno zero. Bene, il Sudoku non presenta "trucchetti" di questo tipo. Può essere solo affrontato e risolto attraverso un approccio di forza bruta. Per questo è noioso.

Per dimostrare come questa procedura sia banale, semplice e meccanica ho realizzato un semplice programma in excel che risolve tutti i Sudoku del mondo sia nella versione tradizionale 9x9 sia nella versione SUPER Sudoku (4 blocchi da 4 celle per un totale di 16x16 celle dove inserire i numeri da 1 a 16). L'algoritmo di risoluzione è lo stesso per entrambi i tipi di Sudoku. L'algoritmo usato (Ricorsivo con Backtracking) non è certamente il più efficiente e dunque sulla versione 16x16 bisogna avere più pazienza che nella versione 9x9. Il tempo medio necessario per la risoluzione di un Suer Sudoku è stimabile nell'ordine delle decine di minuti. La logica dell'algoritmo garantisce che se esiste una soluzione essa verrà trovata.

 

Unicità della soluzione?

Per verificare che uno schema di Sudoku nella versione 9x9 abbia una unica soluzione, è disponibile un altro piccolo file che calcola tutte le possibili soluzioni.

Si può limitare il numero massimo di soluzioni da cercare con un parametro contenuto in una cella gialla del file. Infatti è facile che un determinato schema abbia un numero molto grande di soluzioni. Il parametro evita all'algoritmo di cercare migliaia di soluzioni facendolo arrestare al numero impostato.

Per limitazioni legate a Excel, il numero massimo di soluzioni trovate è comunque limitato a 6.000.


NOTA: Il risolutore è stato sviluppato con Excel 2000. Non funziona con la versione 97.


Un Generatore di schemi di Sudoku da parte di Gianni Giaccaglini!

Un caro amico nonché appassionato di Excle ci ha gentilmente permesso di pubblicare il suo generatore di Sudoku che è scaricabile dal questa pagina!


Il modello è molto interessante e veloce, vi permetterà di generare i vostri schemi personalizzati!





Altri siti interessanti riguardo al Suduku e ad altri divertenti questioni matematiche e giochi:

 

questo articolo è stato citato su Punto Informatico!

 

Ho ricevuto degli spendidi contributi sul Sudoku dai lettori: 

SudokuStella



Licenza Creative Commons

Questa opera è pubblicata sotto una Licenza Creative Commons.

Sudoku Tradizionale
Versione 9x9:

Sudoku
Tradizionale:
TUTTE LE SOLUZIONI
DI UNO SCHEMA

Super Sudoku
Versione 16x16:


iscriviti cancellati




Commenti a questa pagina:   Inviate una mail