SUDOKU (Dove sta l’errore ?)

51 views
Skip to first unread message

Cid

unread,
May 6, 2009, 4:36:55 PM5/6/09
to CiVuDi
Anche a me, come a Rudy, piacciono poco i Sudoku; ho comunque
apprezzato i Sudoku di RM124 (specialmente quello in copertina, la
Sudoku Pizza). Ho gradito poco invece il fatto che nella soluzione
proposta del Sudoku “Shortz 301” sia presente un errore; infatti se
controllate a pagina 32 di RM124 vedrete che nella sesta colonna della
tabella si ripete due volte la cifra 8
Probabilmente Rudy ha sottovalutato l’avvertimento: “Beware! Very
Challenging!”, cosa abbastanza comprensibile considerato che i Sudoku
non l’appassionano, anch’io ne avrei sottovalutato la difficoltà.

Ora però la sfida la propongo a voi, dove sta l’errore:
Rudy ha sbagliato nell’applicare i Teoremi sugli Insiemi di Prelazione
o l’errore è dovuto ad altre cause, o forse l’ha fatto un errore di
proposito per vedere se stavamo attenti, questa ipotesi è plausibile
se si tiene conto della frase: “ ... Rudy potrebbe benissimo
introdurre qualche errore.” che si trova verso la fine di pagina 30 di
RM124.

Io ho qualche idea su quale possa essere l’origine dell’errore, ma
prima di dire la mia opinione gradirei conoscere la vostra.

Alessandro
(Cid)

gnugno

unread,
May 6, 2009, 6:21:45 PM5/6/09
to CiVuDi
Beh,
se non erro, scambiando i valori delle celle 5,5 e 5,6 tutto torna a
posto. Quanto all'origine dell'errore,
non ho nulla da dire, visto che: (a) non amo il sudoku; (b) risolvere
uno schema con tecniche del tipo descritto è come affrontare le parole
crociate con un dizionario elettronico che analizzi le coincidenze.
Ciao
Beppe

fabrizio

unread,
May 9, 2009, 5:13:25 AM5/9/09
to CiVuDi
Ciao Alessandro,
effettivamente come dice Beppe scambiando le celle C(5,5) e C(5,6)
tutto torna a posto. Il che tra l'altro vuol dire che vi era anche
un errore sulla colonna 5 in quanto anche il 2 era ripetuto due volte.
Credo che Rudy, per far capire agli altri quanto possa essere stato
noioso
per lui fare questo Sudoku, anche se compilato per il suo amato RM,
abbia
deliberatamente infarcito di typo lo schema a pag. 31.
Altri errori sono infatti in C(3,1) la segnatura (2,5,6,7,6) anzichè
(2,5,6,7,8) e in C(8,3) la segnatura (2,3,4,5) anzichè (2,3,4).
Per quanto riguarda l'origine dell'errore anch io non mi voglio
spingere
troppo in avanti nell'analisi. Noto però che fin dall'inizio la
segnatura
di C(5,6) dichiarata da Rudy (vedi sempre schema a pag. 31) è
(2,3,5,6,7)
e Rudy sa benissimo che in nessun caso una cella può essere occupata
da un
numero che non è nella sua segnatura. Se applicando un teorema per un
qualche
errore avesse ottenuto per C(5,6) 8 dovrebbe aver notato subito che 8
non è
nella segnatura e quindi avrebbe (sicuramente) corretto l'errore.
Comunque io verso i Sudoku sono abbastanza neutro, non li amo molto ma
penso
che in ogni cosa ci sia comunque del buono.
Può essere che, rigirando la frittata sia interessante , anzichè
risolverli,
provare ad inventarli ( e magari inventarne di difficili come il
Sudoku
Diabolico di Nepham). E comunque qualche problema si può sempre cavar
fuori
anche da questo argomento.
Ad esempio:
1) Qual'è il numero totale di schemi completi di Sudoku che possono
esistere?
Detta in altri termini, in quanti differenti modi è possibile
riempire interamente
tutte le celle di un Sudoku con numeri nell'insieme (1,..,9)
rispettando le regole
del gioco?
2) Rudy ci dice poi che il primo Sudoku di pagina 33 gode di una
strana caratteristica
ossia che ha (almeno) due soluzioni. Almeno? Quante sono in realtà?
(mi immagino che la colpa della non univocità sia dovuta alla
Condizione 1 che nel caso
specifico ammette per una qualche cella la scelta di (almeno) due
numeri
senza dare origine ad una violazione).
3) E allora subito sorge spontanea la domanda : sotto quali condizioni
la soluzione di
un Sudoku è unica?
A presto,
Fabrizio
> >Cid)

Roberto Zanasi

unread,
May 9, 2009, 6:37:07 AM5/9/09
to CiV...@googlegroups.com
2009/5/9 fabrizio <fabrizio.b...@gmail.com>:

> 3) E allora subito sorge spontanea la domanda : sotto quali condizioni
> la soluzione di
>   un Sudoku è unica?

Ciao.

Ma la definizione di sudoku non prevede che la soluzione sia unica?

fabrizio

unread,
May 9, 2009, 8:51:28 AM5/9/09
to CiVuDi
Ciao Roberto,
come detto in realtà non sono molto esperto di Sudoku.
Ignoro il fatto se per ogni Sudoku pubblicato il suo ideatore
garantisca l'unicità della soluzione.
Tuttavia Rudy afferma che il Sudoku in alto a pagina 33, presentato
nientemeno
che al Campionato Mondiale di Praga 2007(cito sempre RM, ignoro se la
notizia
sia vera oppure no), ha almeno due soluzioni.
Anche in questo caso non ho verificato perchè la cosa comunque mi
sembra poco
interessante mentre più interessante è magari cercare di capire se
esista qualche
condizione che garantisca l'unicità della soluzione (ammetto che il
concetto di
interessante è vago e soggettivo, diciamo solo che , forse, è un
quesito più adatto
allo spirito di questo gruppo).
Supponi di essere un "ideatore" di Sudoku e di voler sapere se lo
schema
che hai appena creato abbia effettivamente un'unica soluzione (così
che secondo quanto
mi dici possa essere definito un Sudoku) oppure no. C'è qualche
criterio che ti permette
di verificarlo o di escluderlo?
Ammetterai che la domanda si può porre comunque e che a volte, anche
con un giochino
noioso, si può fare un po' di buona matematica.
Fabrizio


On 9 Mag, 12:37, Roberto Zanasi <roberto.zan...@gmail.com> wrote:
> 2009/5/9 fabrizio <fabrizio.bertucce...@gmail.com>:

Roberto Zanasi

unread,
May 9, 2009, 9:24:04 AM5/9/09
to CiV...@googlegroups.com
2009/5/9 fabrizio <fabrizio.b...@gmail.com>:

> Ammetterai che la domanda si può porre comunque e che a volte, anche
> con un giochino
> noioso, si può fare un po' di buona matematica.

Certo, certo, la domanda si può porre comunque. Mi sembrava strano che
un sudoku presentato in una gara ufficiale avesse 2 soluzioni, perché
ero convinto che non fosse possibile (wikipedia conferma:
http://it.wikipedia.org/wiki/Sudoku).

Ora chiedo a un mio amico correttore di sudoku come fa a controllare
gli schemi...

gnugno

unread,
May 9, 2009, 9:53:26 AM5/9/09
to CiVuDi
Finalmente si gioca un po’!
Come sapete sono abituato a buttar giù le idee così come mi vengono,
tanto a correggerle c’è sempre tempo, almeno quando non si deve
competere con nessuno.
Non ho voglia di postare allegati e allora tento di formulare qualcosa
di comprensibile in modo testo.
Considero i quadrati 3x3 numerati da sinistra a destra e dall’alto in
basso.
1 2 3
4 5 6
7 8 9
Quadrato 1
Si può riempire in 9! Modi

Quadrato 2
Consideriamo la prima riga. Può essere costruita in 4 modi diversi
(a) usando i 3 numeri che nel Q1 erano nella seconda riga. In questo
modo nella seconda dovremo usare quelli della 3^ di Q1 e nella terza
quelli che erano in prima = 1 modo.
(b) usando 2 numeri della seconda riga di Q1 e 1 della terza. Questi
li posso scegliere in 3^2 modi.
La seconda riga dovrà, allora, contenere i due della 3^ di Q1 che non
ho usato e una della prima che posso scegliere in 3 modi. La terza
sarà obbligata = 3^3 modi.
(c) usando 1 numero della ex seconda e 2 della terza di Q1. Il
conteggio è identico a quello del punto (b) = 3^3 modi.
(d) usando i 3 numeri che in Q1 erano in terza riga. Conteggio come in
(a) = 1 modo.

In tutto abbiamo 56 modi diversi per formare le righe di Q2 e per
ognuna di queste, potremo disporre i numeri orizzontalmente come
vogliamo, quindi = 6^3 possibilità.
Q2 si può formare in 56*6^3 modi.

Quadrato 3
Le righe sono obbligate. Posso solo disporre a piacere orizzontalmente
dunque 6^3 modi.

Quadrato 4
Come il Q2. Basta ragionare sulle colonne, invece che sulle righe.
56*6^3 modi.

Quadrato 7
Come il Q3 6^3 modi

Fin qui tutto liscio, ma sento arrivare un forte puzzo di
complicazioni……
Quadrato 5
Ragionando sempre per righe tutto come al Q2. 56 modi diversi.
Però adesso non posso sistemare i numeri orizzontalmente come voglio.
Devo controllare la compatibilità con Q2! In una riga ho 3 numeri da
sistemare, questi abitano anche in Q2 e ho 3 possibilità:
(a) si trovano nella stessa colonna. Non riesco proprio a metterli 0
modi;
(b) 2 in una colonna e 1 in un’altra. Riesco a metterli in 2 modi;
(c) si trovano in 3 colonne diverse. Riesco a metterli in 2 modi;
Dunque 2 modi per ciascuna riga, a meno che almeno una riga coincida
con una colonna di Q2. In questo caso non posso sistemarli. 8 o 0, ma
quante volte 8 e quante volte 0?
Questo proprio non lo so e temo sia difficile da calcolare.
Diciamo che al massimo 56*8 modi

Quadrato 6
Come il Q3, ma con le stesse complicazioni di Q5 per la sistemazione
orizzontale.
Al massimo 8 modi

Quadrato 8
Come Q6. Al massimo 8 modi

Quadrato 9
Beh! Qui è un’autentica lotteria o, meglio, è una corsa al posto di
lavoro. Ogni numero ha una sola collocazione possibile e se hanno già
assunto un altro…. Tutti a casa!

Grande, in tutti i sensi, risultato: non esistono più di 9!
*56^3*6^12*8^3 sudoku diversi.
Beh! Bisogna pur cominciare da qualche laaaaaaaaaarga approssimazione.
Poi ci sarebbe anche da tener conto delle rotazioni, delle simmetrie,
delle permutazioni dei 9 simboli (Toh! Il 9! forse si può buttar via
(ci sarà un raduno di punti esclamativi?)).

Se non si fosse capito, la combinatoria, nel senso concreto del
disordinare le cose, mi piace. Forse, perché a scuola ho da sempre
steso l’orario delle lezioni.

Ciao
Beppe



On 9 Mag, 15:24, Roberto Zanasi <roberto.zan...@gmail.com> wrote:
> 2009/5/9 fabrizio <fabrizio.bertucce...@gmail.com>:
>
Message has been deleted

gnugno

unread,
May 10, 2009, 4:04:46 AM5/10/09
to CiVuDi
Complimenti Fabrizio,
il tuo problema è decisamente tosto, a naso direi come "trattasi di
decidere", con un piccolo vantaggio: essendo una situazione complicata
ma di grandezza finita, mal che vada si può ricorrere alla forza
bruta, magari dopo aver apportato tutte l semplificazioni possibili.
Largo agli informatici!
Su questa via sto lavorando cambiando leggermente l'approccio:
Quadrato 1, 2 e 3 come prima Totale [9! che si può togliere] 56*6^6
modi

Poi fissare solo le colonne
Quadrato 4
56 modi
Quadrato 7
1 modo

Qudrati 5 e 8, nonchè 6 e 9:
medesime procedure di 4 e 7: 56 modi per ogni coppia

A questo punto per un totale di 56^4*6^6 possibilità restano da
sistemare le righe dalla 4 alla 9 che formano due blocchi da 3 dove si
possono rimescolare verticalmente le colonnine.
Due procedure analoghe, ciscuna con 6^8, meno di 2 milioni, di
dispozioni da esaminare.
Penso che si possa fare molto meglio, ma almeno abbiamo una
limitazione inferiore:
i sudoku possibili sono più di [9!] * 56^4*6^8.senza tener conto di
possibili ripetizioni dovute simmetrie e rotazioni.

Ciao
Beppe

Cid

unread,
May 11, 2009, 5:17:58 AM5/11/09
to CiVuDi
Ciao a tutti,
non scrivo questo messaggio per mostrare una mia soluzione (per ora),
ma per chiarire alcune cose.
Mi è piaciuto molto il problema proposto da Fabrizio,
(quando ho creato questa discussione sul Sudoku,
contavo proprio sul fatto che qualcuno la trasformasse in un bel
problema)

Purtroppo però ho poco tempo da dedicarci;
in generale in questi giorni sto avendo poco tempo per la matematica,
ed il poco tempo che ho cerco di dedicarlo ai problemi del mese.
A dire il vero, non ho ancora cominciato a risolvere i problemi di
RM124 (... e Piotr aspetta le soluzioni)
Dopo aver trovato il tempo per i due problemi del mese, conto di
dedicarmi anche a questo problema

Nota Bene:
Scrivo queste cose perchè non mi riteniate assente ingiustificato,
non vorrei ricevere una nota dal maestro Beppe per troppe assenze.
Beppe è un bravissimo maestro, ma ogni tanto giustamente sgrida :-)

A presto,
Alessandro

fabrizio

unread,
May 11, 2009, 6:59:03 AM5/11/09
to CiVuDi
Ciao Alessandro,
confessione per confessione anche io non ho ancora avuto il tempo
di dare un'occhiata ai problemi di RM124.
Per quanto riguarda la partecipazione al gruppo, non credo che debba
essere intesa come un "lavoro forzato" con obbligo di frequenza.
Ognuno può parteciparvi quando preferisce, quando ne ha voglia o
quando ne ha il tempo. Per quanto mi riguarda ad esempio se da gioco
si tramutasse in impegno non mi divertirei più.
Per cui ben venga dedicarsi anche ad altro, il gruppo è qui e spero
vi rimarrà per molto sempre pronto a ricevere contributi di tutti
(specialmente poi se sono preziosi come i tuoi). E poi non è vero
che fai troppe assenze, l'argomento l'hai iniziato tu e l'ideare
nuovi
problemi o dare spunti di discussione è per un sito come questo un
buon modo per tenere desto l'interesse dei suoi membri.
A presto,
Fabrizio
> > > > gli schemi...- Nascondi testo citato
>
> - Mostra testo citato -

gnugno

unread,
May 11, 2009, 10:29:47 AM5/11/09
to CiVuDi
Faccio la voce grossa e, aiutato anche dalla mole (187,125), incuto
terrore. Però chi mi conosce o vede il sorriso negli occhi, finge solo
di spaventarsi.
Ti aspettiamo
Bebbe

On 11 Mag, 11:17, Cid <abever...@aetnagroup.com> wrote:

ginopieri

unread,
May 11, 2009, 12:25:26 PM5/11/09
to CiVuDi
187,125 cm o kg?
Saluti cari
Gino
> > > > > gli schemi...- Ocultar texto das mensagens anteriores -
>
> - Mostrar texto das mensagens anteriores -

gnugno

unread,
May 11, 2009, 9:43:07 PM5/11/09
to CiVuDi
Caro Gino,
quando l'ho scritto sottintendevo cm, ma adesso che mi hai fatto venir
voglia di misurarmi: 125 è una media fra cm e Kg. Qui l'inflazione
continua a viaggiare bene, nonostante la crisi. Eh! Ogni scusa è
buona. Pur di non contare la montagna di Sudoku che hai sul banco, fra
un po' mi chiederai quanti peli ha la mia barba.
Beppe
Reply all
Reply to author
Forward
0 new messages