Precedente :: Successivo |
Autore |
Messaggio |
ulisse Dio maturo
Registrato: 02/03/05 01:09 Messaggi: 1531 Residenza: Bagnone (MS)
|
Inviato: 03 Set 2005 11:58 Oggetto: |
|
|
ZapoTex ha scritto: | Per la trasposizione: sicuro si ottenga roba non ottenibile altrimenti? |
Sicurissimo.
L'insieme delle trasformazioni dato dalle sole permutazioni di numeri, righe, colonne, linee di blocchi non è sufficiente per ottenere, ad esempio, la trasformazione che manda a_ij in a_ji (ovvero la trasposizione).
Però la trasposizione non è l'unico modo per completare l'insieme delle trasformazioni.
Al suo posto, ad esempio, puoi introdurre le rotazioni. La trasposizione la ricavi, quindi, componendo una rotazione (di 90 gradi) con un po' di permutazioni.
Per la verità, nel papiro pdf linkato sopra, ho letto che l'insieme delle trasformazioni comprende sia rotazioni che riflessioni ma ho qualche dubbio che le riflessioni siano effettivamente necessarie in quanto (se non ricordo male) le riflessioni sono ottenibili componendo permutazioni e rotazioni. Ma il papiro è scritto da un matematico che si occupa proprio di algebra geometrica quindi dubito che i miei dubbi siano attendibili... |
|
Top |
|
|
madvero Amministratore
Registrato: 05/07/05 20:42 Messaggi: 19480 Residenza: Ero il maestro Zen. Scrivevo piccole poesie Haiku. Le mandavo a tutti via e-mail.
|
Inviato: 09 Dic 2005 00:09 Oggetto: |
|
|
innanzitutto complimentoni per il nuovo forum. mi avete fatto felice.
poi vorrei una versione in italiano del pdf, se possibile.
infine mi interesserebbe la modellizzazione del problema.
(ci avevo provato quest'estate al mare, ma ad un certo punto mi ero arenata: se ritrovo gli appunti li scannerizzo e li posto)
chiedo troppo?
grazie. |
|
Top |
|
|
ulisse Dio maturo
Registrato: 02/03/05 01:09 Messaggi: 1531 Residenza: Bagnone (MS)
|
Inviato: 09 Dic 2005 00:23 Oggetto: |
|
|
madvero ha scritto: | innanzitutto complimentoni per il nuovo forum. mi avete fatto felice.
poi vorrei una versione in italiano del pdf, se possibile.
infine mi interesserebbe la modellizzazione del problema.
(ci avevo provato quest'estate al mare, ma ad un certo punto mi ero arenata: se ritrovo gli appunti li scannerizzo e li posto)
chiedo troppo?
grazie. |
Grazie per i complimentoni ma aspetta di vedere gli sviluppi!
Del pdf precedentemente linkato (immagino ti riferisca all'articolo sul conteggio delle possibili configurazioni valide di un sudoku) non conosco versioni in italiano e dubito fortemente ne esistano.
Altrettanto dicasi del modello matematico. Questo è almeno quanto ho concluso quest'estate dopo settimane di ricerca in internet (il che non esclude che qualche folle ricercatore possa aver raggiunto il risultato senza renderlo accessibile a tutti via internet). |
|
Top |
|
|
madvero Amministratore
Registrato: 05/07/05 20:42 Messaggi: 19480 Residenza: Ero il maestro Zen. Scrivevo piccole poesie Haiku. Le mandavo a tutti via e-mail.
|
Inviato: 09 Dic 2005 00:29 Oggetto: |
|
|
immagini bene.
se becco il folle ricercatore lo fucilo.
la mia idea, per quanto cretina, era di modellizzare le possibili configurazioni aggiungendo il fatto che la somma dei numeri di ogni riquadro tre per tre è 45, idem dicasi per la somma dei numeri presenti su ogni riga e quelli su ogni colonna.
facendo un po' di conti in spiaggia mi sono accorta che non funzionava, e ho mollato il colpo. |
|
Top |
|
|
ulisse Dio maturo
Registrato: 02/03/05 01:09 Messaggi: 1531 Residenza: Bagnone (MS)
|
Inviato: 09 Dic 2005 01:29 Oggetto: |
|
|
madvero ha scritto: | la somma dei numeri di ogni riquadro tre per tre è 45, idem dicasi per la somma dei numeri presenti su ogni riga e quelli su ogni colonna |
Ehm... che la somma dei numeri nei riquadri, nelle righe e nelle colonne sia costante è immediata conseguenza del fatto che in ognuno di essi trovano posto sempre gli stessi numeri. Permutati quanto vuoi ma sempre i primi 9 interi.
E poichè la somma dei primi n interi è n(n+1)/2 ecco svelato il perchè del 45 ... |
|
Top |
|
|
madvero Amministratore
Registrato: 05/07/05 20:42 Messaggi: 19480 Residenza: Ero il maestro Zen. Scrivevo piccole poesie Haiku. Le mandavo a tutti via e-mail.
|
Inviato: 09 Dic 2005 01:34 Oggetto: |
|
|
Ulisse ha scritto: | che la somma dei numeri nei riquadri, nelle righe e nelle colonne sia costante è immediata conseguenza del fatto che in ognuno di essi trovano posto sempre gli stessi numeri. Permutati quanto vuoi ma sempre i primi 9 interi. |
infatti avevo mollato il colpo perchè era la strada sbagliata
Ulisse ha scritto: | E poichè la somma dei primi n interi è n(n+1)/2 ecco svelato il perchè del 45 |
sì, infatti. a proposito, chi era quel genio storico che aveva intuito il risultato di quella sommatoria in prima elementare, quando la maestra gli aveva dato come compito di sommare tutti i numeri da uno a cento? |
|
Top |
|
|
ulisse Dio maturo
Registrato: 02/03/05 01:09 Messaggi: 1531 Residenza: Bagnone (MS)
|
Inviato: 06 Gen 2006 16:02 Oggetto: |
|
|
madvero ha scritto: | A proposito, chi era quel genio storico che aveva intuito il risultato di quella sommatoria in prima elementare, quando la maestra gli aveva dato come compito di sommare tutti i numeri da uno a cento? |
Un mio amico lettore di ZN e lurkatore non ancora iscritto ai forum mi ha fatto notare che avevo dimenticato di rispondere.
Mi ha anche suggerito la risposta: il matematico in questione è Gauss! |
|
Top |
|
|
madvero Amministratore
Registrato: 05/07/05 20:42 Messaggi: 19480 Residenza: Ero il maestro Zen. Scrivevo piccole poesie Haiku. Le mandavo a tutti via e-mail.
|
Inviato: 06 Gen 2006 18:37 Oggetto: |
|
|
gauss, è vero!!!
grazie... |
|
Top |
|
|
Eureka Mortale devoto
Registrato: 30/03/06 17:08 Messaggi: 19
|
Inviato: 02 Apr 2006 13:37 Oggetto: |
|
|
anche io tempo fà ho sviluppato un risolutore di sudoku in excel e VBA, risolve tutti i tipi di sudoku basta dargli tempo... in alto a destra c'è il tempo che ha richiesto la risoluzine mentre in foglio 2 ci sono alcuni sudoku da copia-incollare....il codice non è commentato ed è particolarmente difficile da capire
una volta scritto o copia-incollato il sudoku nella tavola basterà premere il pulsante "load" e poi il pulsante "risolutore".
ops non so come permettervi di scaricare il file qlc consiglio? |
|
Top |
|
|
Benny Moderatore Hardware e Networking
Registrato: 28/01/06 14:35 Messaggi: 6382 Residenza: Non troppo vicino, mai troppo lontano
|
Inviato: 02 Apr 2006 14:02 Oggetto: |
|
|
Eureka ha scritto: | ops non so come permettervi di scaricare il file qlc consiglio? |
Controlla qui...
Ci sono diversi siti dove poter uploadare vari tipi di file... vedi quello che fa al caso tuo!
|
|
Top |
|
|
ulisse Dio maturo
Registrato: 02/03/05 01:09 Messaggi: 1531 Residenza: Bagnone (MS)
|
Inviato: 03 Apr 2006 13:53 Oggetto: |
|
|
Eureka ha scritto: | anche io tempo fà ho sviluppato un risolutore di sudoku in excel e VBA, risolve tutti i tipi di sudoku basta dargli tempo... |
Che strategie hai adottato?
Solo forza bruta oppure hai implementato degli algoritmi che riconoscono particolari configurazioni e le trattano di conseguenza?
Se li risolve tutti certamente ti sei piegato alla forza bruta (ho dovuto adottarla anch'io perché ci sono problemi che non sono risolubili per altra via).
La parte più divertente per me è stata proprio la ricerca delle strategie risolutive... |
|
Top |
|
|
Eureka Mortale devoto
Registrato: 30/03/06 17:08 Messaggi: 19
|
Inviato: 04 Apr 2006 13:55 Oggetto: |
|
|
grazie Benny per l'aiuto
scusate il ritardo ma sono stato un pò impegnato....
@ulisse il programma risolve il problema attraverso una ricerca esaustiva della soluzione, almeno per i sudoku categorizzati difficili, mentre per quelli mediamente difficili la risoluzione segue un suo schema
il file:
|
|
Top |
|
|
den Mortale adepto
Registrato: 28/09/06 13:38 Messaggi: 30 Residenza: BG provincia
|
Inviato: 09 Ott 2006 13:41 Oggetto: |
|
|
... torno un pò anch'io sui sudoku, vi fa niente ?
è da quando c'è stato il boom dei sudoku più di un anno fa che mi son fatto questa domanda (io NON ho ancora la risposta, e a mio avviso è una domanda piuttosto difficile, probabilmente legata a ciò che è già stato detto in questo post sul numero di soluzioni possibili).
La domanda è:
Qual'è il numero MINIMO di numeri che possono essere presenti nella griglia di partenza affinchè garantiscano l'unicità della soluzione?
io ho visto ad esempio su qualche rivista sudoku di difficoltà "diabolica, per geni" o simili che contenevano meno di 20 numeri (non ricordo di preciso), ed in più si garantiva l'unicità della soluzione...
Il fatto che poi si riescano a risolvere solo con l'ausilio della logica o invece per tentativi è un altro discorso
Ps non penso sia di grande interesse considerare se i sudoku son perfetti o meno (cioè simmetrici rispetto al punto centrale, nel senso che se si trova un numero nella casella A2 se ne deve trovare uno anche in I8). |
|
Top |
|
|
ulisse Dio maturo
Registrato: 02/03/05 01:09 Messaggi: 1531 Residenza: Bagnone (MS)
|
Inviato: 10 Ott 2006 10:14 Oggetto: |
|
|
den ha scritto: | Qual'è il numero MINIMO di numeri che possono essere presenti nella griglia di partenza affinchè garantiscano l'unicità della soluzione? | Che io sappia non è stata trovata risposta definitiva.
Ricordo che qualcosa di rigoroso era stato scritto sull'argomento ma non esaustivo.
Ci sono in rete (in inglese) alcuni forum dedicati esclusivamente ai Sudoku (e nei post precedenti dovrebbero esserci i link. Se non li trovi chiedimi che io li ho memorizzati da qualche parte) che affrontano il gioco dal punto di vista matematico.
den ha scritto: | Il fatto che poi si riescano a risolvere solo con l'ausilio della logica o invece per tentativi è un altro discorso |
E' dimostrato che esistono problemi risolubili senza l'ausilio della forza bruta.
Di converso esistono problemi la cui risoluzione, almeno sinora, non può fare a meno della forza bruta (ovvero nessuno ha dimostrato che non si può fare diversamente ma nessuno ha trovato una strategia che funzioni anche in quei casi)
den ha scritto: | Ps non penso sia di grande interesse considerare se i sudoku son perfetti o meno (cioè simmetrici rispetto al punto centrale, nel senso che se si trova un numero nella casella A2 se ne deve trovare uno anche in I8 ). |
I Sudoku non sono simmetrici nel senso che se trovi un numero in A2 non é detto che lo stesso numero compaia in I8 ma, per definizione di sudoku (almeno secondo la definizione del suo inventore giapponese), la griglia di partenza deve essere simmetrica come posizione, non come contenuto ovvero se e' esposta la cella A2 deve esserlo anche I8 ma non necessariamente con lo stesso numero. |
|
Top |
|
|
chemicalbit Dio maturo
Registrato: 01/04/05 17:59 Messaggi: 18597 Residenza: Milano
|
Inviato: 10 Ott 2006 21:57 Oggetto: |
|
|
ulisse ha scritto: | la griglia di partenza deve essere simmetrica come posizione, non come contenuto ovvero se e' esposta la cella A2 deve esserlo anche I8 ma non necessariamente con lo stesso numero. | Uh ... non lo sapevo (forse c'avevo fato caso, ma non l'avevo ... memorizzato).
Della serie: non si finisce mai d'imparare. |
|
Top |
|
|
madvero Amministratore
Registrato: 05/07/05 20:42 Messaggi: 19480 Residenza: Ero il maestro Zen. Scrivevo piccole poesie Haiku. Le mandavo a tutti via e-mail.
|
Inviato: 10 Ott 2006 22:23 Oggetto: |
|
|
devo dedurne che nessuno si è allietato le vacanze estive con il libro dei sudoku proposti ai campionati mondiali di lucca.
lì di simmetrico c'erano solo le mie bestemmie nell'apprendere che dove io ho impiegato 45 minuti buoni, i campioni ne hanno sprecato sì e no 6.
e fra me e il sudoku, fu un triste e cruento divorzio. |
|
Top |
|
|
den Mortale adepto
Registrato: 28/09/06 13:38 Messaggi: 30 Residenza: BG provincia
|
Inviato: 11 Ott 2006 10:27 Oggetto: |
|
|
ulisse ha scritto: | den ha scritto: | Qual'è il numero MINIMO di numeri che possono essere presenti nella griglia di partenza affinchè garantiscano l'unicità della soluzione? | Che io sappia non è stata trovata risposta definitiva.
Ricordo che qualcosa di rigoroso era stato scritto sull'argomento ma non esaustivo.
Ci sono in rete (in inglese) alcuni forum dedicati esclusivamente ai Sudoku (e nei post precedenti dovrebbero esserci i link. Se non li trovi chiedimi che io li ho memorizzati da qualche parte) che affrontano il gioco dal punto di vista matematico. |
Già mi stupisco che anche altri si siano posti la mia stessa domanda sui Sudoku (tipò questa sul numero minimo per garantire l'unicità della soluzione) vuol dire che non son poi così malato
Riguardo ai link li ho trovati nelle pagine precedenti del forum. Qualche occhiata ce la sto dando e ce la darò (benchè io con l'inglese non vada troppo a braccetto, specie se così specifico, ma mi ci sto abituando visti i testi universitari che per certe materie sono solo in inglese). Grazie comunque per la disponibilità.
ulisse ha scritto: | den ha scritto: | Il fatto che poi si riescano a risolvere solo con l'ausilio della logica o invece per tentativi è un altro discorso |
E' dimostrato che esistono problemi risolubili senza l'ausilio della forza bruta.
Di converso esistono problemi la cui risoluzione, almeno sinora, non può fare a meno della forza bruta (ovvero nessuno ha dimostrato che non si può fare diversamente ma nessuno ha trovato una strategia che funzioni anche in quei casi) |
Beh per quel che riguarda i sudoku a mio avviso se garantiscono l'unicità della soluzione si risolvono solo per logica, in quanto è logica anche fare il ragionamento di provare un numero su una casella che ha più opzioni
(es. se va quel numero lì allora ci va questo là, e dopo 20 passaggi arrivi a vedere 2 numeri uguali sulla stessa riga --> scarto quel numero iniziale)
A mio avviso è logica anche questa, anche se io ragionamenti così lunghi e astrusi da fare solo a mente li definisco "per tentativi".
Ho però sentito di maestri giapponesi che guardano la griglia, si fanno la loro immagine mentale, se la risolvono tutta a mente e solo quando vedono la soluzione completa la scrivono... beh geni o allucinati è più o meno la stessa cosa
ulisse ha scritto: | den ha scritto: | Ps non penso sia di grande interesse considerare se i sudoku son perfetti o meno (cioè simmetrici rispetto al punto centrale, nel senso che se si trova un numero nella casella A2 se ne deve trovare uno anche in I8 ). |
I Sudoku non sono simmetrici nel senso che se trovi un numero in A2 non é detto che lo stesso numero compaia in I8 ma, per definizione di sudoku (almeno secondo la definizione del suo inventore giapponese), la griglia di partenza deve essere simmetrica come posizione, non come contenuto ovvero se e' esposta la cella A2 deve esserlo anche I8 ma non necessariamente con lo stesso numero. |
Sì, intendevo anch'io simmetrica la posizione, non il numero in sè. Comunque precisazione utile in quanto sono stato io un pò approssimativo con i termini, in effetti non sono molto chiaro |
|
Top |
|
|
madvero Amministratore
Registrato: 05/07/05 20:42 Messaggi: 19480 Residenza: Ero il maestro Zen. Scrivevo piccole poesie Haiku. Le mandavo a tutti via e-mail.
|
Inviato: 11 Ott 2006 11:05 Oggetto: |
|
|
den ha scritto: | Ho però sentito di maestri giapponesi che guardano la griglia, si fanno la loro immagine mentale, se la risolvono tutta a mente e solo quando vedono la soluzione completa la scrivono... beh geni o allucinati è più o meno la stessa cosa |
ma perchè, tu come li risolvi i sudoku? guardi la griglia finchè non "vedi" un tot di numeri sicuri, e poi li scrivi. la differenza sta nel fatto che il più abile li continua a tenere a mente finchè non ha finito... |
|
Top |
|
|
den Mortale adepto
Registrato: 28/09/06 13:38 Messaggi: 30 Residenza: BG provincia
|
Inviato: 11 Ott 2006 11:21 Oggetto: |
|
|
io dicevo più per la memoria... a me bastano due numeri per dimenticarmi di quello prima... |
|
Top |
|
|
|