www.argio-logic.net

Ciao a tutti,
Per tutti gli appassionati di sudoku, ho una buona notizia: anche se non riuscite a risolvere uno schema, NON VI PREOCCUPATE.
Non tutti gli schemi a soluzione unica sono risolubili con la LOGICA.
per LOGICA intendo qualsiasi tentativo basato sulle tecniche, anche le più astruse e complicate, fino ad oggi conosciute.

Un esempio di sudoku IMPOSSIBILE è il seguente:

Codice: Seleziona tutto

=========================
| 3 X X | X X X | X X 4 |
| X 8 X | 2 X X | X 7 X |
| X X 6 | X X X | 5 X X |
=========================
| X 1 X | 9 X 8 | X X X |
| X X X | X 6 X | X X X |
| X X X | X X 7 | X 2 X |
=========================
| X X 5 | X X X | 6 X X |
| X 9 X | X X 1 | X 8 X |
| 4 X X | X X X | X X 3 |
=========================

Qualcuno potrebbe obbiettare che non è perfettamente simmetrico, ma non stiamo a sottilizzare.
Perchè viene considerato difficile?
Naturalmente la forza bruta lo risove in frazioni di secondo, ma tentare di dare una qualsiasi spiegazione è un'altra cosa.
I vari programmi di risoluzione e generazione, come ultima risorsa, utilizzano la prova e verifica, per ogni cella insoluta si provano i vari candidati fino a trovarne uno che porta ad una contraddizione che quindi ti permette di eliminarlo.
In questo schema potete provare tutti i candidati: nessuno di essi vi porterà ad una contraddizione.
Qualcuno ha tentato di dare uno straccio di tentativo di soluzione ricorrendo a prove e verifiche inserite una dentro l'altra, impegnando il processore per diverse ore (che tradotto in tempi umani significa diversi giorni se non settimane).
Io non ho inserito le prove e verifiche ad incastro nel mio programma perchè già è difficile trovare qualcuno interessato a giocare col sudoku, figurarsi trovare uno che sia disposto a passare alcune ore di fronte al computer aspettando che questo si decida a dare una spiegazione che, se tutto va bene, impiegherà qualche giorno a decifrare.
Alla prossima.

.

Ho provato a “somministrare” questo schema a qualche Solver. Ne è venuto fuori uno scenario non completo, ma piuttosto significativo, che posso così riassumere.

Il solver si è bloccato ed ho dovuto spegnere tutto.
Il solver ha avviato un processo così lungo che mi ha spinto ad abbandonare dopo una impaziente attesa.
Il solver mi ha dato subito la soluzione, precisando però che lo schema non è risolvibile con le tecniche di soluzioni conosciute.
Il solver ha risolto istantaneamente, per tentativi ed errori e mi elencato i quasi mille passaggi necessari (ma nella circostanza è stato sfortunato, perché se invece di provare il candidato X avesse provato, nella stessa cella, il candidato Y ne sarebbero bastati meno della metà).

Credo di capire perché solver diversi diano risultati diversi. Il solver segue il procedimento impostato da chi lo ha progettato. E come avviene per certe credenze culinaria: “Quello che ci metti, ci trovi”. La resa del solver, insomma, rispecchia il gusto, le scelte e le ambizioni del suo autore.

Però mi piacerebbe saperne di più su certi aspetti della questione.

Primo.

La forza bruta, parola che affascina e intimorisce i non addetti ai lavori. risolve tutto in modo spicci e risoluti. Ma come fa? Non si perde nei pantani delle tecniche, d’accordo. Ma non viene frenata nemmeno nelle lungaggini dei tentativi nei tentativi?
E il solver che mi dà all’istante la soluzione con mille righe di tentativi nei tentavi usa la forza bruta o altro?

Secondo

E’ possibile avere qualche altro schema con queste caratteristiche? O cenni di bibliografia sull’argomento?
I normali solver (non parliamo dei capi “fatti a mano”) possono realizzarli?

La parola agli esperti.

Mille grazie.

Paolo

Grazie Paolo
per questo invito a nozze!
La risposta ai tuoi quesiti, per come la vedo io, richiede un pò di tempo, risponderò a puntate.
partiamo dalla forza bruta.

Ma non viene frenata nemmeno nelle lungaggini dei tentativi nei tentativi?

per risolvere uno schema a soluzione unica con la forza bruta bisogna fare solo qualche migliaio di tentativi, e, per un pc che riesce a fare 3 miliardi di cicli al secondo, è uno scherzo.
La prima versione del mio solutore risolveva questo schema impossibile, utilizzando la forza bruta, in meno di 2 secondi.
poi in rete ho trovato un codice affascinante che lavora in binario che riesce a risolverlo in 50 millisecondi.
non mi ricordo il nome del creatore, sicuramente un genio matematico!
io mi sono studiato il codice, sono riuscito a capirlo (non ci sarei mai arrivato da solo), l'ho adattato al mio solver e lo inserito nella versione attuale.

La forza bruta, parola che affascina e intimorisce i non addetti ai lavori. risolve tutto in modo spicci e risoluti. Ma come fa?

semplice, le prova tutte!
partiamo dal nostro schema di partenza:


la nostra forza bruta comincia a provare tutti i candidati:
il 2 in r1c2, l'1 in r1c3 e così via, ad ogni inserimento elimina il candidato dalla riga, colonna e settore



arrivato a r2c6 prova il primo candidato, il 3.
poi va sulla cella successiva, ma la trova vuota, per l'inserimento del 3 precedente.
a questo punto fa un passo indietro, il 3 non è possibile in r2c6, quindi proverà il nove.
ma anche il nove porterà in pochi passaggi alla creazione di una cella vuota,
quindi nuovo passaggio indietro: l'1 non è possibile in r2c5,
e proverà il 3 in r2c5.....e così via fino a provare tutte le combinazioni possibili,
quando avrà provato anche l'ultimo candidato della r1c2 ha finito il suo compito.
non ho fatte mai contare al programma il numero di tentativi, ma penso che non siano di più di qualche migliaio.
spero di essere stato chiaro, in caso contrario più che contento di approfondire

Grazie, Gabriele, per le tue spiegazioni, che mi interessano molto e mi affascinano.

Ti prego però di chiarirmi un punto.

gabriele ha scritto:Naturalmente la forza bruta lo risove in frazioni di secondo . . .

Qualcuno ha tentato di dare uno straccio di tentativo di soluzione ricorrendo a prove e verifiche inserite una dentro l'altra, impegnando il processore per diverse ore (che tradotto in tempi umani significa diversi giorni se non settimane).

Io non ho inserito le prove e verifiche ad incastro nel mio programma. . .

Ma forza bruta e prove e verifiche sono la stessa cosa o no?

Ti ringrazio per la pazienza.

Paolo

arizona1952 ha scritto:Grazie, Gabriele, per le tue spiegazioni, che mi interessano molto e mi affascinano.

Ti prego però di chiarirmi un punto.

gabriele ha scritto:Naturalmente la forza bruta lo risove in frazioni di secondo . . .

Qualcuno ha tentato di dare uno straccio di tentativo di soluzione ricorrendo a prove e verifiche inserite una dentro l'altra, impegnando il processore per diverse ore (che tradotto in tempi umani significa diversi giorni se non settimane).

Io non ho inserito le prove e verifiche ad incastro nel mio programma. . .

Ma forza bruta e prove e verifiche sono la stessa cosa o no?

Ti ringrazio per la pazienza.

Paolo

per quel poco che ne so, no ...

il "solver brutale" è una semplice velocissima interazione a catena ...

prove e verifiche implicano l'applicazione di logiche e tecniche di soluzione ...

confermo quanto detto da Guido,
la forza bruta prova il candidato disponibile e l'unica azione che fa è l'eliminazione del candidato dai gruppi coinvolti,
la prova e verifica, dopo l'inserimento del candidato, prova tutte le tecniche disponibili,
rapporto di velocità tra le due tecniche quasi tendente a zero (1 a 50.000).

I normali solver (non parliamo dei capi “fatti a mano”) possono realizzarli?

non penso che tali schemi possano essere fatti a mano.

tutti i solver che si rispettino hanno anche un generatore che ogni tanto (raramente al dire il vero) li generano.
come?
nella creazione dello schema si usa il brute force per abbreviare i tempi di generazione, per cui può succedere che si generi uno schema a soluzione unica non risolvibile dalle tecniche conosciute dal solver. Non ho statistiche, ad occhio e croce in base alla mia esperienza, questo capita una volta su 100 mila schemi generati. ma ci studierò per trovare dati più attendibili.

arizona1952 ha scritto:.
Il solver mi ha dato subito la soluzione, precisando però che lo schema non è risolvibile con le tecniche di soluzioni conosciute.
Il solver ha risolto istantaneamente, per tentativi ed errori e mi elencato i quasi mille passaggi necessari (ma nella circostanza è stato sfortunato, perché se invece di provare il candidato X avesse provato, nella stessa cella, il candidato Y ne sarebbero bastati meno della metà).

non ci sono grosse differenze nei due procedimenti, nel secondo caso si contano e memorizzano i singoli tentativi, a scapito, un pò, della velocità.

arizona1952 ha scritto:.
ma nella circostanza è stato sfortunato, perché se invece di provare il candidato X avesse provato, nella stessa cella, il candidato Y ne sarebbero bastati meno della metà.

non concordo su questa asserzione che vale soltanto se si è sicuri che la soluzione è unica, un buon solutore deve controllare tutte le possibili combinazioni per assicurarsi che la soluzione è unica.

Sulla rete si trovano tanti schemi impossibili o quasi

alcuni link:
http://www.sudoku.com/boards/viewtopic.php?t=4212&postdays=0&postorder=asc&highlight=10000&start=0
http://www.setbb.com/phpbb/viewtopic.php?t=1437&highlight=10000&mforum=sudoku

ho provato il primo ( https://www.argio-logic.net/img/top1.swf ) dei top 10.000 proposti da ruud,
ma esiste una differenza sostanziale con lo schema impossibile del topic ( https://www.argio-logic.net/img/top1.swf )

mentre nell'impossibile nessun candidato porta alla contraddizione per cui bisogna ricorrere trial&error innestati uno dentro l'altro,
il primo dei top si risolve per contraddizioni semplici, il mio solver (che ho dovuto modificare all'uopo per aumentare la memoria) lo risolve impiegando diversi minuti con:
42 catene forzate (la più lunga delle quali comprende ben 24 nodi)
1 loop
2 xy-chain
5 colori

ora provo gli altri 9999 e fra qualche anno vi so dire.

gabriele ha scritto:[

arizona1952 ha scritto:.
ma nella circostanza è stato sfortunato, perché se invece di provare il candidato X avesse provato, nella stessa cella, il candidato Y ne sarebbero bastati meno della metà.

non concordo su questa asserzione che vale soltanto se si è sicuri che la soluzione è unica, un buon solutore deve controllare tutte le possibili combinazioni per assicurarsi che la soluzione è unica.

E' vero, non ci avevo pensato.

Segnalo che dal primo dei due siti che hai indicato ho tratto il seguente schema - molto gradevole sotto l'aspetto grafico -, che sembra proprio "Impossibile", in quanto non risolvibile con le tecniche di soluzione più avanzate:

7 . . . . . . . 3
. 9 . 4 . . . 8 .
. . 1 . . . 5 . .
. 8 . 9 . 5 . . .
. . . . 3 . . . .
. . . 2 . 8 . 6 .
. . 5 . . . 1 . .
. 6 . . . 9 . 4 .
3 . . . . . . . 7

https://www.argio-logic.net/img/arizona.swf

Paolo

Carissimo Paolo,

immagino che, in birreria, non sono riusciuto a spiegare "al meglio" una tecnica ( brrr .... che brutta parola, detta da me che di tecniche sono proprio a

digiuno !! ) che ho definito delle "terzine" ... solo per non creare confusione con la tecnica delle "triple" già codificata.

L'idea nasce ( tanto per cambiare !!! ) dall'uso del solver ( eccellente ) del grande Boss Gabriele, cui però manca "inevitabilmente" un tocco di "fantasia",

che non ti puoi aspettare da una macchina.


Spesso, risolti gli schemi alla mia maniera, uso il solver per vedere quali soluzioni adotta, quali tecniche etc ...

esaminando i candidati, io vedo spesso delle celle, che contengono alcuni candidati ( nella riga, colonna o settore ) che mi fanno "gridare" alla tripla, ma

se lo chiedo al solver ... mi ignora !!!

perchè non sono le canoniche triple ... ovvio !!

eppure con un po' di fantasia e sensibilità ... puoi semplificare uno schema anche molto tosto.

Perchè le terzine ?

beh, inizialmente io cercavo coppie nude, due coppie nude sono una grande tentazione di dare un calcio allo schema ...

ma, a griglia bianca, è molto difficile vederle ..

d'altra parte il gioco 9x9, in realtà è riducibile a 3x3 ... cioè un settore ...

da qui e dall'esperienza con il solver del Boss, mi è nata l'idea ... di cercare le "terzine"


Sono tuttavia lontano dal poterla considerare "una tecnica" .. o, magari, nella mia ignoranza, sto cercando di scoprire l'acqua calda ...

però mi sembra che funzioni, anche se a volte a scapito della velocità.

Sto anche cercando di applicarla al "diagonale" e vorrei provarla anche con la bestia ( > < ) ...va beh ...

un passo alla volta ...

stavo preparando degli schemi presi dall'archivio, quando mi sono imbattuto nel tuo ... e la tentazione è stata grande

Mi sono permesso di prendere lo schema e mi sono concentrato sulle prime colonne, e per comodità ho inserito i candidati ...

nella seconda colonna spicca una terzina ( 2,4,5 ) in r1, r5, r7 ...

veramente in r7 troviamo solo il 24 .. perchè il 5 è caduto con l'inserimento del 5 nel settore 7 ..

ma se preferisci possiamo aggiungere il 7 per la quartina ( "sporca" ) che si evidenzia in r1, r5, r6, r7

fissati questi "candidati" ... il 3 trova posto in r3 e l'1 in r9

mentre il 7 in r6 ...

in prima colonna ora abbiamo 28 in r7, 2489 in r6, 2468 in r3 che mi fanno pensare alla ( 2, 4, 8 ), scartando un 6 ed un 9 ...

mentre nel settore 7 la nostra ( 2,4,8 ) è obbligata in r7c1, r8c1 e r7c2 ( altrimenti in r7c2 non avremmo candidati del tutto ) che ci permette di fissare

il 9 in r9c3 e il 7 in r8c3 ... mentre l'8 è "unico" in r1c3;

mentre 26, 2(3)46, 246, mi fanno decidere per il 3 in r6c3.

A questo punto nel settore 4 si evidenziano 16, 1569, 159 in r4c1, r5c1, r6c1 e 245 in r5c2 con 246 in r4c3 e r4c4 ...

ammetto che qui le cose si complicano ... da una parte verrebbe voglia di tenere 24,246,246 ... e 1, 59, 59

dall'altra parte il 5 in r5c2, lascierebbe la terzina 16, 169, 169 e due coppie 24,24 ...

ci devo ancora lavorare ...

beh, va comunque detto che l'individuazione delle "terzine" funziona con molti candidati ... e mostra i limiti quando i candidati scarseggiano, ovviamente

ah sì, funziona nelle griglie del Boss ... più raramente sulle griglie caotiche di Ciunga ..


Ovviamente saranno gradite critiche, commenti e contributi

guidopatek ha scritto:

esaminando i candidati, io vedo spesso delle celle, che contengono alcuni candidati ( nella riga, colonna o settore ) che mi fanno "gridare" alla tripla, ma

se lo chiedo al solver ... mi ignora !!!

perchè non sono le canoniche triple ... ovvio !!

eppure con un po' di fantasia e sensibilità ... puoi semplificare uno schema anche molto tosto.

. . .

Sono tuttavia lontano dal poterla considerare "una tecnica" .. o, magari, nella mia ignoranza, sto cercando di scoprire l'acqua calda ...

però mi sembra che funzioni, anche se a volte a scapito della velocità.

Caro Guido ti ringrazio per l’estrema pazienza che hai avuto con me a Lucca, quando mi hai illustrato ripetutamente le tue idee sul modo di risolvere il Sudoku. Ti ho ascoltato con grandissimo interesse, sino al punto da voler conservare, in pizzeria, il tovagliolo di carta su cui avevo preso gli appunti.

E ti ringrazio per aver riproposto con dovizia di particolari la questione sul Forum, a beneficio mio e di tutti.

guidopatek ha scritto: mi sono concentrato sulle prime colonne, e per comodità ho inserito i candidati ...

nella seconda colonna spicca una terzina ( 2,4,5 ) in r1, r5, r7 ...

veramente in r7 troviamo solo il 24 .. perchè il 5 è caduto con l'inserimento del 5 nel settore 7 ..

guidopatek ha scritto:ma se preferisci possiamo aggiungere il 7 per la quartina ( "sporca" ) che si evidenzia in r1, r5, r6, r7

fissati questi "candidati" ... il 3 trova posto in r3 e l'1 in r9

mentre il 7 in r6 ...

Questa la mia analisi della tua prima mossa.

La Sezione presa in esame è una Colonna, la 2, in cui ci sono 3 Numeri Certi (Iniziali) e 6 celle vuote. Questi i relativi candidati:

Primo Gruppo:

Codice: Seleziona tutto

.   2   .   4   5   .   (riga 1)
1   2   .   4   5   7   (riga 5)
1   .   3   4   5   7   (riga 6)
.   2   .   4   .   7   (riga 7)

Secondo Gruppo:

Codice: Seleziona tutto

.   2   3   4         (riga 3)
1   2       4         (riga 9)

Se nelle quattro celle del Primo Gruppo si “fissano” quattro candidati:

2 – 4 – 5 – 7

si rileva che in tali celle vi sono due candidati “estranei”, l’1 (riga 5 e riga 6) e il 3 (riga 7).

Poiché tali candidati “estranei” 1 e 3 sono presenti nel Secondo Gruppo di celle, essi:

• vanno esclusi dalle celle del Primo Gruppo
• sono Numeri Certi delle celle del Secondo Gruppo. E precisamente 3 in riga 3 e 1 in riga 9.

Mi auguro di aver capito bene e ti prego di correggere eventuali svarioni.

Queste le mie osservazioni:

UNO - Quando in quattro celle sono presenti (tutti o alcuni) solo quattro diversi Numeri e nessun altro Numero è possibile eliminare quegli stessi Numeri dalle altre celle della medesima Sezione. E’ lo schema detto della Quartina Nuda, che però nel nostro caso non si verifica né considerando le celle del Primo Gruppo (dove ci sono quattro celle e sei numeri), né coinvolgendo anche altre celle del Secondo Gruppo. Un esempio di Quartina Nuda con numeri a caso (e quindi non riferiti al nostro schema) è questo:

2 4 5 7
2 5 7
4 5 7
2 5

in tal caso si possono eliminare i candidati 2 – 4 – 5 – 7 eventualmente presenti nelle altre celle della Sezione.

DUE - Quando quattro Numeri sono presenti (tutti o alcuni) solo in quattro celle, insieme ad “altri”, e non sono presenti nelle altre celle della Sezione, è possibile escludere dalle quattro celle gli “altri “Numeri”. E’ lo schema detto della Quartina Nascosta, che nel nostro caso non si verifica né considerando le celle del Primo Gruppo (in quanto i candidati 2 e 4 sono presenti anche in celle del Secondo Gruppo), né coinvolgendo anche altre celle del Secondo Gruppo. Un esempio di Quartina Nascosta con numeri a caso è questo:

2 5 8
2 4 5
2 4 5 7
4 5 7

in tal caso – sempre che i candidati 2 -4 – 5 – 7 non siano presenti nelle altre celle della Sezione – si può eliminare il candidato 8 dalla prima cella.

TRE – Il tuo ragionamento – come peraltro hai precisato anche tu – non rientra quindi nelle Tecniche canoniche. Però funziona. Ha funzionato in questo caso. Funziona quasi sempre, come è confermato dalla tua notoria capacità di sbloccare gli schemi in tempi molto rapidi. Perché funzioni, come funzioni, non lo so. Peraltro questa volta non ti sei misurato con gli schemi di Argio (di cui hai capito, credo, la struttura di fondo), ma con un Sudoku considerato “difficilissimo” dalla Comunità internazionale dei giocatori di Sudoku.

QUATTRO – Ho somministrato lo schema a tre dei più potenti Solver che conosco. Due specificano che “non vi sono Tecniche solutive conosciute per risolvere lo schema” e non riescono a fare nemmeno un passo verso la soluzione, e cioè ad eliminare nemmeno un candidato. Il terzo lo risolve solo mediante tentativi nei tentativi. Ed il primo tentativo lo fa già alla prima mossa.

CINQUE: "eppure con un po' di fantasia e sensibilità ... puoi semplificare uno schema anche molto tosto." Cosa dire di più? La parola agli esperti.

Un caro e riconoscente saluto.

Paolo

arizona1952 ha scritto:
QUATTRO – Ho somministrato lo schema a tre dei più potenti Solver che conosco. Due specificano che “non vi sono Tecniche solutive conosciute per risolvere lo schema” e non riescono a fare nemmeno un passo verso la soluzione, e cioè ad eliminare nemmeno un candidato. Il terzo lo risolve solo mediante tentativi nei tentativi. Ed il primo tentativo lo fa già alla prima mossa.

Un caro e riconoscente saluto.
Paolo

Caro Paolo,
mi spiace non averti potuto incontrare a Mantova ...

però non ho abbandonato i miei tentativi di dare "sostanza" alla "terzina sporca" ...

per quanto riguarda i solver, eseguono fedelmente ( e velocissimamente !!!) "solo" le istruzioni del programmatore ... oltre non vanno

mi piacerebbe "convertire" i ragionamenti e le intuizioni che passano per la mente e permettono di identificare "quella terzina" ... ( che chiamo "sporca", perchè non canonica ) e poi tentare di covincere il Boss ad implementarli nel suo solver ...

a presto ( spero )

guido