Tecniche 9/1

 


 

Teoria Generale delle Catene Numeriche

Questo articolo presenta una Teoria Generale delle Catene Numericheusate per risolvere i Sudoku.

1 - I metodi semplici di risoluzione.

Le metodologie sviluppate in questo sito sono fatte per i giocatori che si interessano alle spiegazione anzichè alla valocità. Si tratta dunque di rispondere alla domanda "Perchè è così ? ".

Per rispondere a questa domanda, il giocatore deve identificare dei Valori Certi utilizzando le cifre presenti nel Sudoku. Le tecniche de base sono i tagli delle righe, colonne e settori, e i Candidati Unici Nascosti.

  A B C D E F G H I
1           4   2  
2   7         3    
3 4   1 3         8
4 2   6   1     8 3
5 1 X         9    
6 8   9   3     7 4
7 6   4 9         7
8   1         4    
9           8   3  

Esempio de taglio di un settore.

Avendo esaurito le possibilità de queste tecniche, il Sudoku è in bloccaggio diabolico. Osservando allora la dispozione delle cifre prsenti, (topologia della posizione bloccata) il giocatoreriesce talvolta a trovare dei nuovi dei Valori Certi topologici o multitopologici. Cioè dei Valori Certi per i quali le cifre che participano al ragionamento non sono tutte presenti nel Sudoku (tecniche di topologia semplice, caselle binarie, Tripletto., etc.).

 

  A B C D E F G H I
1     1   5        
2   2     4       1
3 7   4 8 1 3      
4     3   2 8 6    
5 8   9 7 6 5     2
6     2 3 9   8    
7     7 5 3 6     8
8         7     4  
9   3   4? 8 4? 7   5

Esempio de taglio topologico di una colonna.

Resta poi la possibilità di trovare delle Configurazioni Vietate di l'Unicità per evitare delle soluzioni numeriche multiple.

 

  A B C D E F G H I
1 6 3 7 4 1 9     8
2 4 9 5 23 7 8 6 1  
3 1 2 8 6   5   9 4
4 8 5   7   3   6 2
5 2 4   1   6      
6 7 6   5   2     9
7 5 7 6 23 23 4 9 8 1
8 3 8 2 9 6 1     5
9 9 1 4 8 5 7     6

Se il Sudoku resiste a queste tecniche, il giocatore deve allora considerare le relazioni numeriche che legano le caselle tra di loro, la Tabella dei Candidati diventa necessaria.

  A B C D E F G H I
1 1239 148 245689 2345 126 7 1458 48 48
2 1237 147 245 2345 12 8 1457 9 6
3 17 1478 4568 45 16 9 14578 3 2
4 1279 147 249 2347 8 34 6 5 3479
5 279 3 2489 1 5 6 2478 248 4789
6 6 5 248 2347 9 34 23478 1 3478
7 8 9 3 6 7 1 24 24 5
8 5 6 1 9 4 2 38 7 38
9 4 2 7 8 3 5 9 6 1

Esempio di Tabella dei Candidati.

2 - L'Analisi della Tabella dei Candidati.

Il giocatore ha ora una Tabella più o meno affolata di Candidati.

Certe configurazioni numeriche sono fácili da riconoscere, particolarmente quelle che hanno delle caselle binarie (che hanno esattamente due candidati ). La riconoscenza di queste ConfigurazioniNotevoli fornisce delle semplificazioni della Tabella dei Candidati e eventualmente dei dei Valori Certi indotti.

In questo sito, numerose Configurazioni Notevoli sono mostrate, come :i Esclusioni Parallele, le Esclusione Ortogonali, le catene in Rettangolos (XY wing), la topologia delle Maglie, ecc.

 

  A B C D E F G H I
1 3 9 5 12 12 7 4 8 6
2 7 4 8 9 6 3 5 1 2
3 6 2 1 5 8 4 79 79 3
4 8 56 7 46 459 59 2 3 1
5 2 3 49 16 15 8 679 4579 59
6 1 56 49 3 7 2 69 459 8
7 5 1 36 24 234 69 8 29 7
8 9 7 36 8 23 56 1 25 4
9 4 8 2 7 59 1 3 6 59

Esempio di Configurazione Notevole.

Le caselle C5 e H6 non possono valere 5, B6 = 5 è un Valore Certo.

Certi Sudoku molto difficili non sono risolti , a questo punto bisogna ricercare delle Catene Numeriche.

3 - I Legami Numerici.

La Tabella dei Candidati contiene dei legami numerici tra le caselle libere del Sudoku.

Queste relazioni sono dirette quando le due caselle sono situate in vista l'una dell'altra, cioè nella stessa riga, la stessa colonna o lo stesso settore. Sono indirette quando il legame risulta da una catena di legami diretti. Cioè dire quando i due caselle legate lo sono tramite una Catena Numerica.

I legami diretti tra due caselle possono essere forti quando sono reciproci. Ci sono due tipi di Legami Forti

Tipo Positivo

Le due relazioni sono vere simultaneamente

Case Iniziale = V1 implica Case Finale = V2

Case Finale = V2 implica Case Iniziale = V1

Tipo Negativo

Les due relazioni sono vere simultaneamente

Case Iniziale = V1 implica Case Finale <> V1 (<> signifie diverso di)

Case Finale <> V1 implica Case Iniziale = V1

I legami diretti sono deboli quando non sono reciproci.

Tipo Positivo

Case Iniziale = V1 implica Case Finale = V2 è vero allora Case Finale = V2 implica Case Iniziale = V1 è falso

Tipo Negativo

Case Iniziale = V1 implica Case Finale <> V1 (<> signifie diverso di) è vero allora Case Finale <> V1 implica Case Iniziale = V1 è falso

  A B C D E F G H I
1 25 6 8 3 147 1457 49 17 29
2 25 7 9 48 148 14568 34 16 23
3 34 34 1 2 9 67 5 67 8
4 1 89 6 5 2 378 379 4 39
5 7 2 3 9 14 14 8 5 6
6 89 5 4 78 6 378 379 2 1
7 39 39 7 1 5 2 6 8 4
8 48 1 5 6 3 48 2 9 7
9 6 48 2 478 478 9 1 3 5

Esempio de Legame debole Tipo negativo.

F3 = 7 implica E1 <> 7, la reciproca E1 <> 7 non implica F3 = 7.

 

4 - Le Catene Numeriche Chiuse.

Una Catena Numerica è costituita da diversi legami (forti o deboli)i quali stabiliscono un legame indiretto tra la casella Iniziale e la casella Finale della catena.

Una Catena Numerica è caratterizzata dal suo numero di legami che la compone, il tipo di legami (forti o deboli, positivi o negativi), le caselle "Iniziale" e "Finale".

Case Iniziale Case Finale Numero dei Legami Tipi di Legami Valori Nome
Qualunque = Case Iniziale Pari Forti-Deboli Alternati 1 CCA (Nice Loop)
Qualunque = Case Iniziale Dispari Forti-Deboli Alternati con Irregolarità 1 CCQA
Qualunque = Case Iniziale Qualunque Qualunque Diversi Catena Mista

 

Le Catene considerate per la risoluzione dei Sudoku sono chiuse. Il principio è di trovare un conflitto colla regola del Sudoku ae cosi trovare una semplificazioni della Tabella dei Candidati della casella iniziale o a un Valore Certo.

 

  A B C D E F G H I
1 5 1347 6 148 14789 47 2 1379 17
2 9 1247 1247 3 147 6 157 157 8
3 8 137 137 25 179 25 13679 13679 4
4 3 1257 127 9 247 8 1457 1457 6
5 17 6 9 45 347 3457 1347 8 2
6 4 2578 278 6 237 1 357 357 9
7 2 13479 1347 148 13468 34 14679 14679 5
8 6 148 148 7 5 9 14 2 3
9 17 349 5 24 1346 234 8 469 17

Esempio de Catena chiusa Alternata (Nice loop).

Le caselle in viola non possono valere 7 (<> 7).

  A B C D E F G H I
1 3789 36789 369 5679 2 4569 1 4678 34578
2 379 123679 5 679 146 8 237 2467 347
3 4 12678 126 3 16 156 257 9 78
4 2 3459 349 589 7 1359 39 18 6
5 379 3679 8 269 1346 13469 2379 5 1379
6 1 35679 369 3568 3569 4 278 3789
7 359 14 7 568 3568 356 59 14 2
8 58 248 24 1 9 27 6 3 457
9 6 1239 1239 4 35 27 8 17 1579

Esempio di una Catena Chiusa Mista 4 Legami.

C3 = 2?, C9 = 1, B7 = 4, C8 = 2, impossibile. C3 <> 2 è un Valore Certo.

 

5 - Il Paragone delle Catene Numeriche Aperte.

Quando tutti i valori di una Catena Numerica sono veri, allora l Catena è vera.

Al contrario, se un solo valore di una Catena Numerica è falsa allora tutta laCatena è falsa.

Il paragone di Catene Numeriche consiste nel fare il ragionamento

" se a partire di una stessa casella iniziale, esiste due catene Numeriche diverse che arrivano su di una stessa casella libera finale con lo stesso valore, allora una di queste due Catene è vera la casella finale ha il valore comune alle due Catene."

Questo ragionamento varia come indicato sotto

atene Casella Iniziale Valore Iniziale Casella Finale Valore Finale Numero dei Legami Conclusione Nome
1 e 2 Binaria V-W Commune = x Qualunque Finale = X CP
1 e 2 Binaria V-W Commune <> x Qualunque Finale <> X CN
1 e 2 Qualunque V Commune X et Y Qualunque iniziale <> V DRP
1 e 2 Qualunque <> V Commune X et Y Qualunque iniziale = V DRN

 

  A B C D E F G H I
1 3689 37   35 579   358   3678
2   137 19     1379 23   237
3 1368 1347 1468 235 1257 137 358 68  
4   15 158   69   189   168
5 18     345 459 39 49   18
6         46   47 67  
7   12345 1459 248 124   1238 89 1238
8 169 12 169 28     1278 789  
9 13   14   1247 17     123

Esempio de Paragone di Catene CP.

Catena 1 E4 = 6, I4 <> 6, I1 = 6

Catena 2 E4 = 9, E1 <> 9. A1 = 9, I1 = 6,I1 = 6 è un Valore Certo.

Le tecniche di Catene sono delle tecniche 9 stelle.

Bernard Gervais.