Sudoku Solver

Di tanto in tanto mi diletto nel rilassarmi cercando di risolvere uno schema di un sudoku.

A volte non riesco a trovare la soluzione, il che invece di rilassarmi tende ad innervosirmi.

Da qui il passo che mi ha portato a cercare un aiuto informatico è stato brevissimo.

La domanda che mi sono posto è stata: Come implementare un risolutore "intelligente" di sudoku?

Con intelligente intendo che il risolutore non si basi sulla forza bruta, bensì proceda con la logica, come potrebbe fare un qualunque uomo (così da vedere dove diavolo eventualmente avevo sbagliato o cosa non avevo notato).

Lo so che magari non è proprio una domanda normale, tant'è che mi son messo di buona lena, acceso il PC, atteso il caricamento di Ubuntu, preso le mie adorate librerie Qt e per l'occasione utilizzato il QDevelop, tanto per vedere com'è tale ambiente di sviluppo.

Procediamo con ordine e vediamo come ho sviluppato il programma.

INTRODUZIONE

Debbo insegnare al software come si gioca!

I principi di base sono facili da riportare:

Lo schema consta di 1 tabella quadrata contenente una matrice di 3x3 quadrati a loro volta contenente una matrice di 3x3 caselle.

In ogni casella va inserito un numero da 1 a 9 secondo le seguenti semplici regole:

- In ogni quadrato ogni casella deve avere un numero diverso (quindi per ogni quadrato ci sarà una ed una solo occorrenza di un numero)

- In ogni riga ed in ogni casella della tabella non ci possono essere più occorrenze dello stesso numero

Dalle due regole si ricava immediatamente il semplice corollario:

- Per ogni riga ed ogni colonna della tabella si avranno tutti e soli i nove numeri possibili.

PASSO 1

Partiamo dalla tabella vuota.

Per ogni casella avremo tutti e nove i numeri possibili. Si veda figura 1.

PASSO 2

Inserire i numeri che andranno a formare lo schema iniziale da risolvere.

Nel software basta cliccare con il tasto sinistro sul numero da inserire. C'è anche la possibilità di salvare e successivamente caricare uno schema. I numeri inseriti manualmente avranno la casella con sfondo in grigio chiaro. Mentre si inseriscono i numeri le possibilità per ogni casella che vanno contro i principi base vengono eliminate. Si veda la figura 2 per un esempio di uno schema inserito e pronto per essere risolto.

PASSO 3

Scovare le possibilità "singole" così da risolvere alcune caselle. Ci sono quattro tipi di "possibilità singole":

A) c'è una sola possibilità per un tal numero in una casella;

B) c'è una sola possibilità per un tal numero in un quadrato (ovvero la matrice di 9x9 caselle);

C) c'è una sola possibilità per un tal numero in una colonna;

D) c'è una solo possibilità per un tal numero in una riga;

le figure qui di seguito relative ad uno stesso quadrato penso siano esplicative (casi A e B).

Ovviamente per ogni numero inserito si eliminano tutte le possibilità che contrastano con il nuovo inserimento secondo le regole descritte nell'introduzione, i numeri inseriti automaticamente avranno sfondo grigio scuro.

Se lo schema non è completamente risolto si continua la ricerca, se infruttuosa si passa al "passo 4".

Se lo schema è completo il gioco è fatto. Eureka!

PASSO 4

Quarto passo, trovare se vi sono alcune possibilità da eliminare.

Qui la mia mente ha partorito solo due metodi di eliminazione (che in pratica è lo stesso metodo ripetuto su righe e colonne):

Se in un quadrato tutte le possibilità di inserimento di un numero sono nella stessa riga/colonna, questo significa che per tale quadrato il numero sarà inserito in quella riga/colonna. Ciò comporta che tutti gli altri quadrati non potranno avere tale numero in tale riga/colonna.

La spiegazione forse non è chiarissima, le figure che seguono spero rendano il concetto più chiaro.

Nelle figure i quadratini di tonalità più scura indicano il numero eliminato (che stava all'interno di tale quadretto, uguale a quelli dei quadretti di tonalità più chiara).

Se si trovano possibilità da eliminare si reitera questo punto fintantoché non ve ne sono più e si torna dunque al punto "3", se non si trova alcuna possibilità da eliminare si passa al punto "5".

PASSO 5

Se si è arrivati qui la logica da sola non è stata sufficiente a risolvere lo schema.

Non è detto che tutti gli schemi siano risolvibili con le tecniche sopra elencate, fatto sta però che tutti quelli che ho inserito fin ora solo alcuni della categoria "diabolici" non vengono risolti medianti le tecniche descritte nei punti precedenti.

Sono alla ricerca di nuove regole per la risoluzione "logica" da introdurre nel software! Se qualcuno me ne inviasse una gliene sarei molto grato!

Quello qui sotto è un esempio di sudoku "diabolico", le caselle evidenziate in azzurro contengono due sole possibilità, su di queste ho concentrato la mia attenzione per trovare delle nuove tecniche risolutive, senza fortuna però.

Arrivati a questo punto non ho trovato di meglio che scegliere un numero a caso. Per massimizzare la possibilità di buona riuscita della scelta cerco prima la casella con meno possibilità (di norma 2), ne scelgo una (partendo dalla prima disponibile) e torno al punto 3. In caso non si riesca a risolvere lo schema torno ricorsivamente alla situazione precedente ed effettuo la scelta della possibilità successiva (e così via).

I numeri inseriti mediante scelta a caso avranno sfondo giallo.

Di seguito due schemi che hanno necessitato del passo 5 per la loro risoluzione, nel secondo si noti che è stato necessario fare più di una scelta a caso.

NOTE FINALI

In allegato trovate il software corredato di qualche schema, per eseguirlo dovete essere in un sistema operativo Linux con librerie Qt installate.