Blogger templates

Risolvere un sudoku a tempo di record

Il sudoku è un gioco di abilità numerica che richiede una certa dote di ragionamento astratto.
Tale tipo di ragionamento è visibile in almeno tre caratteristiche distinte:
  1. il sudoku ha generalmente una sola soluzione globale, per questo motivo non si devono sperimentare tutte le possibili combinazioni, ma partire dalle aree determinate, evidenti applicando un qualche metodo per isolare parti dei riquadri determinate da parti dei riquadri non determinate (approccio all'incontrario simile al metodo diagonale di Gauss)
  2. nel sudoku non ci si deve quasi mai concentrare l'attenzione su una singola casella, bensì ragionare per linee
  3. il sudoku può essere risolto velocemente applicando le tecniche di soluzioni più veloci ed intuitive. Tuttavia in funzione della difficoltà dello schema di sudoku, sta al giocatore indovinare con un colpo d'occhio quale di queste tecniche di soluzione sarà disponibile per continuare nella soluzione. Questo diventa la sfida del sudoku una volta imparate le tecniche di soluzione veloce.
Il metodo più lento e sbagliato per risolvere un sudoku è quello di concentrarsi su ogni singola casella e ragionare per probabilità di numeri che possono ricadere in una data casella.

Quasi tutti gli schemi di sudoku sono determinati globalmente e si può giungere alla determinazione globale, risolvendo le parti localmente determinate.
In rari casi, vengono proposti sudoku molto difficili, spesso con distribuzioni geometriche dei numeri simmetriche o antimetriche, con un numero superiore di soluzioni.
Generalmente questi sudoku sono risolvibili parzialmente fino ad un certo punto, nel quale tutte le tecniche di risoluzione parziale non forniscono una soluzione locale determinata.
Ciononostante, l'applicazione delle stesse regole di soluzione parziale (specialmente la prima) permettono di individuare una delle possibili soluzioni dello schema sudoku difficile a soluzioni multiple.

La regola che determina il sudoku è: in ogni riga, colonna e quadrato deve esserci una combinazione di numeri dall'1 al 9 senza ripetizioni.
Questa è la base di indagine che applicheremo in tutte le tecniche di soluzione basata sull'isodeterminazione e sull'esclusione delle caselle vuote tali da dare soluzioni localmente fallaci.



Prima tecnica: la più veloce ed intuitiva
Schema di esempio, nel quale si prende in considerazione il numero 4.


Individuati due numeri 4 su due blocchi attigui, sul terzo vuoto non potrà essere disposto un 4 sulle righe corrispondenti agli altri due.
Ne consegue l'intersezione delle linee con cancellazione di tutti gli spazi vuoti e l'individuazione della casella dove posizionare il nuovo numero.


Tale tecnica è estremamente veloce e preferibile... non può essere applicata sempre (vedi per esempio il numero 5 nello stesso schema).
Basta passarsi tutti i numeri dall'1 al 9 verificando che permetta di inserire nuovi numeri.
Tuttavia inserendo nuovi numeri con qualsiasi regola di soluzione, è possibile riapplicare in modo efficace questa tecnica di soluzione con i nuovi arrivati.



Seconda tecnica: orizzontale e verticale creano una distribuzione quasi completa
Schema di esempio, nel quale si prende in considerazione la casella indicata in rosso e si ragiona per la linea orizzontale e verticale passanti per la casella considerata.

Ora, il numero che deve cadere nella casella considerata 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.
Si può ben vedere che i numeri che stanno nell'intorno della casella di interesse sono una serie quasi completa: 1, 2, 3, 4, 5, 6, 8, 9.
Ovviamente si possono considerare anche i numeri interni al quadrato per ridurre le possibili alternative.
Quindi nella casella non può che ricadere il numero 7, senza creare doppioni sia nella linea orizzontale che verticale.


Il metodo di verifica è molto veloce, tuttavia rispetto alla tecnica precedente è più difficile individuare la casella che è circondata da una serie quasi completa.
Il metodo risulta lievemente più lento e richiede colpo d'occhio per non perdere tempo a passarsi tutte le caselle.
Può essere applicato quando la prima tecnica non fornisce più risultati.
Trovato un nuovo numero si può tornare ad applicare la prima tecnica per il nuovo numero disposto.



Terza tecnica: completezza fra i quadrati
In questa tecnica si considerano i numeri mancanti in una data linea (una distribuzione dall'1 al 9), rispetto ai numeri presenti ed alle caselle vuote, soprattutto considerando i vincoli derivanti dalle intersezioni con le corrispondenti linee verticali e con i numeri nel medesimo quadrato.
Lo schema preso in considerazione e la riga di interesse è visibile nell'immagine seguente


Nella linea orizzontale si può notare che mancano i numeri della serie: 1, 4, 5, 6, 7, 8.
Tali numeri andranno prima o poi disposti in tutte le caselle vuote presenti, ma a noi basta determinarne anche solo uno per continuare.
La presenza del numero 4 nei quadrati in cui ricadono alcune caselle vuote della linea presa in considerazione, invalida la disposizione del numero 4 nella linea cancellando così la soluzione in almeno quattro caselle vuote, indicata in seguito con una macchia rossa.
Le due celle rimanenti sono nel quadrato centrale, tuttavia una risulta libera, mentre l'altra si trova in colonna con un altro numero 4.
Da ciò si capisce dove disporre il numero 4 sulla riga considerata.
Da notare che se nel quadrato in basso il numero quattro si fosse trovato al centro, non si sarebbe potuto determinare una casella vuota nella riga in cui disporre la soluzione.


Da notare che l'esempio qui adottato è risolvibile anche con la prima tecnica, ma più in generale non è detto valga tale connubio.

Si può notare come questa tecnica sia poco intuitiva, dato che chiede al solutore di osservare la completezza della distribuzione di numeri fra i quadrati rispetto ad una riga; tuttavia rispetto alle precedenti è anche più laboriosa, dato che porta a valutare tutti i numeri di una serie su tutte le caselle vuote di una linea orizzontale o verticale.
Può essere furbo applicare questa tecnica a linee orizzontali o verticali quasi completamente risolte (due, tre o quattro caselle vuote sulle nove totali), sperando di trovare un incrocio con linee ortogonali che elimini tutte le caselle vuote meno una.
Oppure si può giocare sull'esclusione dei numeri nel medesimo quadrato, cercando di individuare una data linea orizzontale o verticale in cui un dato numero presente nel quadrato cancella il maggior numero di caselle vuote lasciandone poche nella linea (nell'esempio sopra indicato si escludono 4 caselle vuote con due quadrati in cui è presente il numero da disporre).
Dato che per tre quadrati in linea (con relativi numeri già presenti che non vanno inseriti nelle caselle vuote) passano tre righe, di queste tre si prende quella più zeppa di numeri, in modo tale da ridurre le possibili incognite o caselle vuote presenti.
Le due righe continue si trovano nelle medesime situazioni (passano per gli stessi tre quadrati) meno che per qualche numero assente e qualche numero presente: per questo motivo basta indagare solo per i numeri che vengono a mancare dalla riga prossima precedentemente esaminata.

Ciononostante negli schemi più difficili di sudoku si può arrivare ad applicare questa regola riuscendo a sbloccare una situazione ferma.
Può essere applicato quando la prima tecnica non fornisce più risultati.
Trovato un nuovo numero si può tornare ad applicare la prima tecnica per il nuovo numero disposto.


Quarta tecnica: la più semplice e la più inutile
Considerando un semplice quadrato od una linea verticale od orizzontale, quando la soluzione del sudoku è in fase avanzata, ci si dimentica spesso di riempire la sola casella vuota rimanente nel medesimo ambito.
In questo caso la soluzione semplicissima e veloce si basta sul passarsi i numeri presenti nel medesimo ambito (quadrato o riga orizzontale o riga verticale) per individuare il numero mancante.
La tecnica è inutile, perchè arriva a schema quasi completo e non risolve quasi mai fasi cruciali degli schemi sudoku.


Nessun commento:

Posta un commento