www.argio-logic.net

adolfo ha scritto:La tecnica della "terzina sporca" , come la chiama Guido non è poi così campata in aria.
Qualcosa di simile , ma più sicuro , dimostrato matematicamente , si ritrova nella tecnica conosciuta come
"Almost Locked Sets" (ALCS) che esamina n+1 candidati in in insieme di n celle , confrontando un altro insieme (di m+ 1 candidati in m celle ) si arriva ad escludere in modo certo un candidato.. .

Adolfo ha aggiunto al discorso un tocco di grande pregio, come sa ben fare.

Istintivamente concentriamo la nostra attenzione sui Set “completi” di candidati.

Una Terzina è un Set completo, perché ha tre diversi candidati presenti (tutti o in parte) in tre celle. Ad esempio:

r1c1 12
r2c1 13
r3c1 123

Quindi il numero dei candidati è pari al numero delle celle che li contengono.

Anche una quartina è un Set completo: sono quattro diversi candidati presenti (tutti o in parte) in quattro celle. Ad esempio:

r1c1 1234
r2c1 13
r3c1 123
r4c1 1234

Al “Set quasi completo” manca invece qualcosa, come in questo caso in cui vi sono quattro candidati in tre celle:

r1c1 1234
r2c1 134
r3c1 123

Come prendere in esame un Set quasi completo?

Guido ha coniato un eccellente termine: Terzina (o Quartina) “sporca”. Sporca appunto perché ha qualcosa in più (un candidato in più), ovvero perché (ed è la medesima cosa da un diverso punto di vista) ha qualcosa in meno (una cella). In sostanza si riferisce ad un “Set quasi completo”.

La forma più elementare del “Set quasi completo” è data dalla cella che contiene solo due candidati (Cella Bivalore).

Se la cella r1c1 può contenere solo i candidati 12, avremo due candidati e una sola cella. Ed è quindi un “Set quasi completo”. Per completarlo occorre una seconda cella che contenga esclusivamente i medesimi candidati:

r1c1 12
r1c2 12

è infatti un Set completo.

In realtà, magari senza grande consapevolezza, già prendiamo in considerazione “Set quasi completi” nello XY–Wing. Infatti, in uno schema di questo tipo:

r1c1: 12
r1c2: 13
r1c9: 23

si esaminano le coppie di celle con candidati 12-13 e 12-23, che altro non sono che due “Set quasi completi”, ciascuno dei quali è costituito da tre candidati in due celle.

Il discorso è simile per lo XYZ-Wing.

Altre importanti riflessioni sui "Set quasi completi" (in inglese ALS) non sono però “immediate” e fanno capo a Tecniche solutive c.d. estreme, la cui applicazione non è né usuale né semplice.

Guido ha quindi un bell’osso da spolpare. . .

Devo però dire che mediante i “Set quasi completi” si cancellano candidati che sono in celle diverse da quelle del Set, mentre mi sembra che, al contrario, Guido tenda a cancellare i candidati che sono in celle all’interno del Set. Quelli che lo sporcano, tanto per intenderci.

Potrebbe quindi non essere il medesimo punto di vista.

Vedremo. . .


Paolo

Devo però dire che mediante i “Set quasi completi” si cancellano candidati che sono in celle diverse da quelle del Set, mentre mi sembra che, al contrario, Guido tenda a cancellare i candidati che sono in celle all’interno del Set. Quelli che lo sporcano, tanto per intenderci.

Potrebbe quindi non essere il medesimo punto di vista.

Vedremo. . .

Non vorrei essere stato frainteso.
La tecnica ALS è un esempio di tecnica "certa" che esamina n+1 candidati in n celle.
L'ho citata appunto come esempio, per invitare a non essere troppo scettici di fronte ad approcci a prima vista "assurdi".
Il metodo di Guido non ha parentele con questa tecnica.
Non garantisce certamente conclusioni sicure e determinate.
Però una idea di novità forse la ispira (o forse non è una novità , ormai il sudoku è stato vivisezionato in ogni aspetto).
Secondo me l'approccio è un qualcosa che definirei "ipotesi dicotomica" , e provo a spiegare.
Per quanto riguarda il termine ipotesi credo che non ci sia niente da aggiungere , c'è chi lo chiama tentativo , chi nishio , chi in altro modo ma sempre di quello si tratta.
E' cioè una supposizione da verificare se è vera o falsa.
Nessuno dubita della validità della tecnica , spesso giudicata la più rapida, l'atteggiamento nei confronti della tecnica è più psicologico che logico , se notate gli interventi ,anche in questo forum, sono più per dire se piace o non piace.
La novità sta nel termine dicotomico , un metodo che ,se applicato, può velocizzare notevolmente la soluzione.
La ricerca dicotomica è molto usata informatica , è il metodo che permette di reperire rapidamente una informazione. Faccio il solito esempio dell'elenco telefonico, cioè di un elenco ordinato , in questo caso in ordine alfabetico.
Il metodo più rapido per cercare un nome è aprire l'elenco a metà , se il nome che cerco viene prima del nome che leggo apro l'elenco a metà della metà inferiore(iniziale) , se viene dopo apro l'elenco a metà della metà superiore(finale).
Ripetendo il procedimento arrivo in fretta al nome che cerco.
Se ai tempi in cui la Carrà faceva il giochino di indovinare il numero di fagioli nella bottiglia i concorrenti avessero applicato questo metodo partendo dalla risposta ricevuta (sono di più , sono di meno), avrebbero indovinato in poche telefonate.
Perchè non applicarlo al sudoku?.
Supponiamo che in una riga il numero 7 sia candidato in 6 celle.
Supponiamo che voglia usare le ipotesi.
Perchè provare ad una ad una le 6 ipotesi?.
Posso cancella tre dei sei numeri 7 (divido quindi a metà).
Ho probabilmente un velocizzazione nel valutarne gli sviluppi (cancello 3 numeri invece di 1). Se arrivo ad una contraddizione allora il 7 è tra quelli cancellati e posso cancellare gli altri 3 in una volta sola.
Ora se i 3 numeri 7 sono stati scelti a caso ho comunque un vantaggio rispetto al metodo semplice, ma se i 3 numeri 7 sono stati scelti perchè appartenenti ad una terzina o quartina sporca , (o altre considerazioni a questo punto) verosimilmente il vantaggio è maggiore sia che arrivi ad una conferma che ad una contraddizione.

Adolfo

non posso che ringraziare, ovviamente ..

ho trovato in giro qualcosa circa le tecniche ALS … ed in effetti sono “rigorose”.

come giustamente ha sottolineato Paolo-Arizona, ad esse sono riconducibili i XY e XYZ–wing …

oltre diventano soltanto un interessantissimo ( ma pesante ) esercizio di logica …

la signora Liù mi ha fornito un link http://www.scanraid.com/Almost_Locked_Sets

dove queste tecniche sono illustrate con dovizia di particolari …. ma …

Questo, ad esempio, dimostra come si può eliminare con certezza un candidato …

Il 7 in G7 ( o r7c7 per usare la notazione a noi più comune )

eppure ....

esaminando la riga 7 ( o G ) … si nota subito una “terzina sporca” … ( 6,7,8 ) in colonne 5 e 6 ed in colonna 9 [ dove sono presenti 7 e 8, “sporcati da un 2”, mentre manca il 6 perché Numero Dato in r8c8 ( stesso settore ) .. ].

Fissare questi tre candidati permette di eliminare subito almeno i due 7 di r7c7 e di r7c4 … ovviamente il 2 di r7c9 ( quello che sporca la terzina ) …






Non solo : la posizione di 4, 2, 9 nelle prime tre righe di colonna 9, permette di eliminare il 2 da r8c9, per cui il 2 è singolo in r7c7, il 5 è singolo in r7c4 …. e lo schema è saltato !!!!