Risolvere schemi Sudoku

Stampa
( 4 Votes ) 
Valutazione attuale:  / 4
ScarsoOttimo 
Categoria: Informatica
Data pubblicazione
Scritto da Fragger Visite: 12650
SUDOKU  SUDOKU
Un Sudoku è una griglia di 81 celle composta da 9 righe e 9 colonne. La griglia, a sua volta è suddivisa in 9 settori (dette anche zone,regioni, blocchi o riquadri) di 3x3 celle. Ogni cella può contenere solo numeri da 1 a 9.

Il Sudoku ha una solo regola ed è la seguente:
Un Sudoku è completo o risolto, quando in ogni colonna, in ogni riga e in ogni settore sono presenti tutte le cifre da 1 a 9 ma senza ripetizioni ovvero ogni numero deve comparire una volta sola.

Per risolvere un Sudoku non serve la matematica ma una buona dose di logica, metodo e tanta pazienza. Non è necessario eseguire calcoli numerici ma è un classico problema le cui soluzioni devono essere cercate fra un numero più o meno elevato di possibilità o combinazioni.

Ma quante sono le combinazioni? Tante, un numero inconcepibile: Più di 6.670 miliardi di miliardi! Se un computer ne risolvesse 1.000 al secondo impiegherebbe 211 miliardi di anni per risolverli tutti.

Quelli che troviamo sulle riviste di enigmistica, giornali ecc. sono schemi di partenza e possono avere un numero variabile di numeri già inseriti. Sono schemi che possono avere una unica soluzione o averne più di una.
La quantità dei numeri già inseriti di solito ne determina la difficoltà di risoluzione ma quest'ultima può essere determinata anche dalla posizione dei numeri nella griglia.

Per la risoluzione di un sudoku ci sono numerose metodologie, dalle più semplici alle più complesse e queste possono essere usate sia da un abile giocatore umano che da un computer. La sola differenza è che il computer è piu veloce.


COME SI RISOLVE UN SUDOKU

Partendo da una schema inizale di Sudoku la prima osservazione è quella di contare i numeri presenti nella griglia. Infatti la difficoltà di risoluzione di un Sudoku è proprio il totale dei numeri inseriti.
Per schemi facili si parte da un minimo di 32-34 numeri, per passare a schemi difficili con meno di 28 numeri. Quindi in funzione dei numeri iniziali si adottano le tecniche diverse.
Si parte dalle righe, colonne, settori con il maggior numero di elementi per individuare immediatamente i numeri mancanti.
Righe, colonne e settori sono i tre elementi base del Sudoku, osservare questi tre elementi come un insieme unico e non come tre entità separate. Queste sono le aree che controllerete e ricontrollerete in continuazione quando affronterete uno schema, qualunque sia il livello di difficoltà. In altre parole, un Sudoku costringe a un esercizio di elasticità mentale, che obbliga il solutore a mettere a fuoco via via l'area che offre maggiori probabilità di successo. Se una strada non porta da nessuna parte, prendetene un'altra. Ovvero, se esaminando le righe restate bloccati, osservate le colonne poi i settori e qundo riuscite a inserire un numero certo nella griglia, si ricomincia dall'inizio.
Non bisogna mai dimenticare che la soluzione di un Sudoku è un'operazione a catena: i numeri che mano a mano si trovano, a loro volta permettono di scoprire nuovi numeri......e così via fino alla soluzione completa dello schema.

TECNICHE DI BASE

Iniziamo con le tecniche di base che ci permettono di risolvere schemi facili, ed è altrettanto facile capire queste tecniche.

Candidato in settore
CandidatoSettore
Prendiamo in esame il settore celeste. Il 7 in A1 lo escude in D1 e E1. Il 7 in I3 lo esclude in E3 e F3. Il 7 in F6 lo escude in F3. Il 7 in D7 lo esclude in D1 e D2. Quindi il candidato che sicuramente farà parte della suluzione è il 7 in E2.

Candidato in Riga
Candidato Riga
Prendiamo in esame la riga celeste. L'1 in C1 escude in C7, G2 esclude in G7, D4 esclude in D8 e D9, I4 esclude in E7, B5 esclude in B7, A8 esclude in A7,H9 esclude in H7. Quindi il candidato che sicuramente farà parte della soluzione è l'1 in E7. Si può fare anche un'altro tipo di ragionamento. Notare che i settori adiacenti hanno già l'1 quindi escludono le 3 celle superiori dei rispettivi settori. La cella F7 è esclusa dall' 1 in F3, quindi anche a colpo d'occhio si vede la soluzione. Se notate bene quì si può applicare anche la tecnica del Candidato in Settore

Candidato in Colonna
CandidatoColonna
Le prime tre celle della colonna sono escluse dall' 1 in quanto è già presente nel settore centrale, la E6 è esclusa ugualmente dall' 1 per la presenza in I6, il settore centrale è privo del numero 1, quindi il candidato sicuro, che farà parte della soluzione finale dello schema, è l'1 in E4.

Candidati Unici in Settore
UnicoCandidatoSettore
Indipendentemente dai numeri presenti fuori dal settore in celeste l'unico  candidato mancante non può essere che il 9. Ovviamente bisogna controllare che sia rispettata la regola del Sudoku.

Candidati Unici in
Riga/Colonna
UnicoCandidatoRC
Anche in questo esempio, sia nella colonna che nella riga, manca un solo candidato che, sempre rispettando la regola del gioco, sarà sicuramente parte della soluzione: 4 in E3, 6 in D2

Metodo a esclusione
MetodoEsclusione
Prendiamo in considerazione la casella in azzurro e si ragiona per la linea orizzontale e verticale passanti per la casella considerata. Il candidato che deve cadere nella casella deve essere coerente con la linea verticale e la linea orizzontale, da cui consegue che non deve essere un doppione nè dei numeri
nella linea orizzontale nè di quella verticale. I numeri che stanno nell'intorno della casella e quindi da escludere sono: 1, 2, 4, 6 all'interno del settore, 1,2,5,6 nella colonna, 3,4,8 nella riga.
Quindi nella casella non può che ricadere il numero 7, senza creare doppioni sia nella linea orizzontale che verticale. Questa tecnica è più difficile da adottare.


Metodi  per deduzione.

Deduzione1

Cerchiamo l'8 nella casella rossa. Da una prima analisi con la tecnica del Candidati in settore, restano possibili due posizioni, G1 e G3. Ma in realtà possiamo fare qualche altra osservazione. Nel settore centrale in alto non possiamo sapere esattamente dove sta l'8, ma certamente starà in una delle caselle grige, perchè la riga 3 è già completa e la riga 2 contiene l'8 in A2.
Dunque ci sarà un 8 in D1 o E1 o F1 e questo esclude la possibilità di un 8 in G1 nel settore azzurro e allora possiamo affermare con certezza che l'8 in G3 (rosso), farà parte della soluzione finale.


Deduzione2

Vediamo se è possiblile inserire qualche numero nel settore azzurro, procedendo con una serie di deduzioni incatenate. Nella riga 4 mancano 4 e 5 in B4 e C4, anche se non sappiamo in che ordine. Ne consegue che nello stesso settore, nelle 3 caselle della riga 5, ci staranno i rimanenti numeri 1,2 e 7, anche se ancora una volta non sappiamo in che ordine. Ne consegue ancora che nelle tre caselle rosse ci saranno 3,4 e 6, perchè sono gli ultimi 3 numeri che mancano nella riga 5;
ma questa volta sappiamo anche la posizione esatta, per via dei numeri già presenti nelle colonne D ed E;
il 4 non può che andare in F5
il 6 di conseguenza deve andare in D5
il 3 non resta che la E5.
Notare che così restano anche determinati i 3 numeri che completano il settore azzurro (5,7,8) anche se ancora non sappiamo in quale ordine, che scopriremo man mano che andiamo avanti nel gioco inserendo nuovi numeri(si spera).

Deduzione3

Concentriamoci sulle caselle rosse!
Consideriamo la riga 2 le colonne D ed E.
Nella collonna D mancano 2 e 8, che vanno in D3 e D5.
Nella colonna E mancano 8 e 9 che vanno in E3 ed E5.
Nella riga 2 mancano 8 e 9 che vanno in F2 e G2.
Ma ora, considerando il settore centrale in alto, notiamo che entrambe le celle E3 ed F2 devono avere o l'8 o il 9;
dunque l'8 è neccessariamente in una di queste due e quindi non può essere in D3, di conseguenza in D3 ci va il 2, in D5 l'8, in E5 il 9, in E3 l'8, in F2 il 9 e infine in G2 di nuovo l'8!


Con questi 3 esempi di metodi per deduzione, abbiamo terminato questa panoramica di tecniche di base. Ovviamente non sono esaustive, ma danno sicuramente l'idea a quali problematiche bisogna affrontare per la risoluzione di un Sudoku. Queste tecniche o metodi descritti sono anche detti "Metodi a colpo d'occhio" in quanto, trovato il numero lo si inserisce nello schema.
All'inizio ho detto che le tecniche di base si adottano in genere per schemi facili o almeno fino a che riusciamo ad inserire numeri. Quando adottando ripetutamente tutti i metodi conosciuti e le varie annotazioni sembrano non portare a niente, ecco che bisogna passare alla tecniche piu evolute, armarsi di gomma e matita, scoprire i candidati e avere tanta, tanta pazienza.

TECNICHE AVANZATE

Che significa scoprire i candidati, come detto sopra?
Prendiamo uno schema vuoto, senza numeri, quindi ogni casella potenzialmente può contenere tutti i numeri da 1 a 9 come in figura.
 ScopriCandidatijpg

Continua.......