Metodi di risoluzione

A differenza di noi umani, che per risolvere un Sudoku aggiungiamo dei numeri allo schema, il programma segue il percorso inverso: partendo da una griglia in cui tutte le 81 caselle contengono i 9 numeri, compie una serie di eliminazioni fino ad arrivare alla soluzione finale.

Ovviamente le prime eliminazioni avvengono con la lettura dello schema iniziale, poi il programma comincia ad utilizzare i metodi di risoluzione.

Questi metodi vengono utilizzati in ordine progressivo, dal più semplice al più complesso. Dopo ogni cambiamento avvenuto nella griglia, il programma riparte dal Metodo A e prosegue.

Ogni volta che un metodo viene effettivamente utilizzato, dei punti vengono aggiunti al livello di difficoltà. Questo ci consentirà di avere una valutazione di ogni schema risolto dal programma.

Metodo A

Controlla se all'interno di una riga, di una colonna o di un quadrato, un determinato numero è presente solo una volta. La conseguenza è ovvia: la casella interessata può contenere solo quel numero.

Punti aggiunti al livello di difficoltà: 4

Metodo B

Controlla se in una riga, un numero è presente solo in una delle 3 sezioni che compongono la riga stessa. Se così, nel quadrato che comprende quella sezione, si potrà eliminare quel numero dalle altre due sezioni. Lo stesso metodo si ripete per colonne e quadrati.

Nel caso dei quadrati, la sezione in cui è presente il numero farà parte di una riga se orizzontale o di una colonna se verticale e il numero si potrà eliminare dalle altre due sezioni della riga o della colonna.

Punti aggiunti al livello di difficoltà: 8

Metodo C

Controlla se all'interno di una riga, di una colonna o di un quadrato, una coppia di numeri si ripete in due caselle ed è assente anche singolarmente nelle altre sette. In questo caso si possono eliminare gli altri numeri presenti nelle due caselle. Lo stesso metodo è ripetuto per gruppi di 3 o più numeri (in 3 o più caselle).

Punti aggiunti al livello di difficoltà: 16

Metodo D    AGGIORNATO !

Il codice di questo metodo è stato scritto da Alan Chambers - Grazie Al !

Controlla se all'interno di una riga, di una colonna o di un quadrato, sono presenti un gruppo di N caselle che contengono solo un gruppo di N numeri. In tal caso i numeri andranno sicuramente in quelle caselle e si potranno eliminare dalle altre.

Non è necessario che i numeri siano tutti presenti in tutte le caselle (vedi esempio).

Per esempio in questa riga:

1         2         3         4         5         6         7         8         9
---------------------------------------------------------------------------------
378       38        6789      37        458       2         34568     489       1

Le colonne 1, 2, 4 contengono i numeri 3, 7, 8.

Possiamo eliminare i numeri 7, 8 dalla colonna 3, il numero 8 dalla colonna 5, i numeri 3, 8 dalla colonna 7 e il numero 8 dalla colonna 8.

Successivamente la riga si presenta così:

1         2         3         4         5         6         7         8         9
---------------------------------------------------------------------------------
378       38        69        37        45        2         456       49        1

Per un esempio pratico, guarda questa pagina (in inglese)

Punti aggiunti al livello di difficoltà: 32 (2 numeri), 48 (3 numeri), 64 (4 numeri).

Metodo E - Non implementato

Questo metodo è stato proposto per risolvere uno dei nostri Sudoku Illogici (non risolvibili solo con la logica), ma non è stato ancora tradotto in codice. Per vedere questo metodo o per provare a scrivere il codice, clicca qui (in inglese).

Metodo F    AGGIORNATO !

Questo metodo è conosciuto come X-Wing:

Se in una riga un numero è presente solo in due caselle (esempio B3 B7) e se in un altra riga lo stesso numero è presente solo in due caselle che si trovano nelle stesse colonne delle due caselle della prima riga (esempio H3 H7), allora quel numero si potrà eliminare dalle altre caselle delle due colonne. Se le due righe o le due colonne fanno parte dello stesso quadrato, il numero si potrà eliminare anche dalle altre caselle dei due quadrati che contengono le quattro caselle in cui è presente il numero.

Il metodo si ripete per le colonne:

Se in una colonna un numero è presente solo in due caselle e se in un altra colonna lo stesso numero è presente solo in due caselle che si trovano nelle stesse righe delle due caselle della prima colonna, allora quel numero si potrà eliminare dalle altre caselle delle due righe. Se le due colonne o le due righe fanno parte dello stesso quadrato, il numero si potrà eliminare anche dalle altre caselle dei due quadrati che contengono le quattro caselle in cui è presente il numero.

Esiste un metodo equivalente per i quadrati:

Se in un quadrato un numero è presente solo in due caselle (esempio A1 C2) e in un altro quadrato lo stesso numero è presente solo in due caselle che si trovano sulle stesse due righe o colonne delle due caselle del primo quadrato (esempio A5 C4), allora quel numero si potrà eliminare dalle altre caselle delle due righe o colonne (nell'esempio le caselle sono A7 A8 A9 C7 C8 C9).

Credo che il metodo per i quadrati non sia stato implementato. (N.d.T.)

Se le caselle coinvolte sono 9 (3 righe x 3 colonne) il metodo si chiama Swordfish.

In realtà non è necessario che un determinato numero sia presente in tutte le 9 caselle, basta che sia presente in almeno 2 caselle su 3 in ciascuna riga e colonna.

Se le caselle sono 16 (4 x 4) si chiama Jellyfish.

Se le caselle sono 25 (5 x 5) si chiama Squirmbag.

Per valori superiori a 5 si usa il termine Uber-Squirmbag.

Anche il codice di questo metodo è stato scritto da Alan Chambers.

Punti aggiunti al livello di difficoltà: 48 (X-Wing), 64 (Swordfish o superiori)

Altri metodi di risoluzione

Altri metodi sono visionabili nel sito di John Perry. Sono piuttosto complicati, ma tu potresti essere in grado di scrivere il codice Javascript ! (in inglese)

Cosa sono le supposizioni ?

Non tutti i Sudoku si possono risolvere solo con la logica. Se i metodi conosciuti non consentono di arrivare alla soluzione, è necessario ricorrere ad una supposizione. In pratica si tratta di un tentativo. In una casella con due possibili opzioni, si sceglie un numero e si prosegue utilizzando di nuovo i metodi logici fino ad arrivare o alla soluzione o ad una contraddizione.

Ovviamente nel primo caso il numero scelto era quello giusto, nel secondo caso era quello sbagliato e di conseguenza quello giusto era l'altro. Esistono Sudoku in cui una supposizione non è sufficiente per arrivare alla soluzione, ma ne servono due o più.

Il programma ricorre alle supposizioni solo dopo aver verificato l'impossibilità di proseguire solo con metodi logici. Disattivando "Utilizza le supposizioni" il programma non sarà in grado di risolvere Sudoku di questo tipo.

Punti aggiunti al livello di difficoltà: 1000 (per ogni supposizione)

Mostra la prima soluzione

Alcuni Sudoku risolvibili solo con le supposizioni potrebbero presentare più soluzioni (non quelli pubblicati su quotidiani e pubblicazioni specializzate che sono garantiti con soluzione unica). Disattivando "Mostra la prima soluzione" il programma analizzerà tutte le possibili ramificazioni per verificare se la soluzione è unica.

Ringraziamenti

Grazie a Riccardo Riva per la traduzione del sito in lingua italiana.

Torna all'indice