Tecniche e Metodologie risolutive per giocare a Sudoku

Esistono diverse metodologie risolutive per questo gioco, tutte poco legate alla logica ed alla matematica ma strettamente connesse all'operatività manuale ed alla pazienza.

Alcune tecniche mirano a trovare la soluzione della cella analizzando le righe, colonne e sottogriglie analizzandone i possibili candidati delle caselle. Altre teniche mirano alla sola cancellazione di alcuni candidati da delle precise celle. I candidati di una cella sono i numeri che sono ammessi come soluzione nella medesima, ossia è la lista dei 9 numeri esclusi quelli gia presenti nelle righe, colonne e sottogriglie.

Per eliminazioni successive (Naked Single)

Questa metodologia prevede che si possa cancellare il contenuto delle celle. Si inizia scrivendo in ogni quadretto libero tutti i numeri ammessi e non ammessi, dopo aver eliminato dalle nove cifre quelle già presenti nella riga, nella colonna e nella regione 3x3 a cui il quadretto appartiene; si esamina poi la tabella alla ricerca di scelte obbligate e si procede alla cancellazione successiva delle scelte effettuate dalle corrispondenti celle della colonna, della riga e della regione. In altre parola si va ad inserire la soluzione in una cella quando questa ha un solo possibile candidato.

Per "zone proibite" (Hidden Single)

Questa tecnica da sola non è sufficiente a risolvere completamente un Sudoku (a meno che non sia molto facile), ma è un valido complemento nella risoluzione di tutti gli schemi, e accelera di molto la ricerca della soluzione. Si tratta di esaminare la disposizione di uno dei numeri nelle varie regioni per controllare se, in regioni dove non è presente, impedisce tutte le altre posizioni meno una, che quindi deve essere quella giusta per quel numero.

In figura accanto si riporta un esempio per il numero sei: i tre "sei" considerati (in giallo) impediscono la presenza di altri sei nelle caselle vuote evidenziate in violetto. Nella regione centrale sinistra rimane una sola casella "permessa" per il sei (evidenziata in verdino): e poiché deve esistere un sei per ogni regione, si deduce che il sei di quella regione è proprio lì.

Block and Column / Row Interactions

Nell'immagine a destra, i numeri grandi sono i numeri inseriti all'inizio, mentre quelli piccoli sono i candidati possibile della cella.

Se andiamo ad osservare la prima sottogriglia notiamo che il candidato 7 è presente solo nelle caselle in arancione che si trovano entrambi sulla seconda colonna. In quella sottogriglia il 7 è obbligato a stare nella seconda colonna. Questa informazione è sufficente per procedere all'eliminazione del candidato 7 dalla seconda colonna dalle celle che non appartengono alla prima sottogriglia (le celle in azzurro).

Per applicare questo algoritmo ad un programma per computer è sufficente verificare solo i candidati a gruppi nelle sottogriglie. Se il solito candidato e presente più volte solo sulla stessa riga o sulla stessa colonna possiamo procedere all'eliminazione dei candidati fuori dalla sottogriglia che stiamo analizzando in quel momento.

Block Interactions

Questa tecnica è leggermente più complessa da realizzare al computer ma non più lunga.

Dobbiamo analizzare i candidati delle celle a gruppi di due sottogriglie orizzontali o verticali tra di loro. Nell'esempio viene analizzato la sottogriglia centrale con quella in centrale in alto. Nell'immagine notiamo che il candidato 3 è presente in due sole colonne tra le due sottogriglie prese in analisi. Se nella sottogriglia più in alto, il candidato 3 sta nella quarta colonna, nella sottogriglia più in basso il candidato 3 dovrà risidere obbligatoriamente nella quinta colonna. Nel secondo caso il candidato 3 sta nella sottogriglia più alto, nella quinta colonna obbligando nella sottogriglia centrale, l'inserimento del 3 nella quarta colonna. In tutti i casi possibili il 3 viene escluso dalla possibilità di essere inserito nelle celle in azzurro.

Per questo motivo, l'informazione che un candidato, tra due sottogriglie sia presente in due sole colonne, ci consente di eliminare il candidato dalle celle in quelle colonne, che pero' non appartengono alle sottogriglie che abbiamo appena analizzato (le celle in azzurro).

Se le due sottogriglie che andiamo ad analizzare, sono orizzontali tra di loro dobbiamo verificare che i candidati siano presenti in due sole righe. Se le sottogriglie sono verticali tra loro, come nell'esempio, dobbiamo verificare solo che tra loro siano su due sole colonne.

Naked Pair

A differenza delle precedenti due tecniche, questa si applica a tutti i gruppi possibili (colonne, righe e sottogriglie). Prendiamo come esempio la lista completa dei candidati possibili in una sottogriglia (possiamo escludere dalla lista le celle che hanno gia assegnata la soluzione).

{4,5}, {4,7,9}, {4,5}, {7,9}, {4,5,9,1}

Se ci sono due celle che hanno due, identici candidati, è possibile rimuovere i due candidati dalle altre celle del gruppo preso. Nell'esempio due celle hanno come candidati il 4 e il 5, in questo caso possiamo andare ad elimanerli nelle altre celle e semplificare così l'insieme delle soluzioni possibili. Il 4 e il 5 sono obbligati ad essere nelle due celle trovate. In tutti gli altri casi possibili, se il 4 o il 5 fossero in celle differenti arriveremo ad avere una soluzione impossibile come delle celle senza candidati. Provate per credere. Questa è la soluzione semplificata:

{4,5}, {7,9}, {4,5}, {7,9}, {9,1}

Semplificando le soluzioni abbiamo trovato due nuove celle che hanno gli stessi due candidati {7,9}. Usiamo nuovamente la stessa tecnica sul solito gruppo:

{4,5}, {7,9}, {4,5}, {7,9}, {1}

Abbiamo appena trovato una soluzione.