Indice del forum Olimpo Informatico
I Forum di Zeus News
Leggi la newsletter gratuita - Attiva il Menu compatto
 
 FAQFAQ   CercaCerca   Lista utentiLista utenti   GruppiGruppi   RegistratiRegistrati 
 ProfiloProfilo   Messaggi privatiMessaggi privati   Log inLog in 

    Newsletter RSS Facebook Twitter Contatti Ricerca
* Sudoku
Nuovo argomento   Rispondi    Indice del forum -> Enigmi e giochi matematici
Precedente :: Successivo  
Autore Messaggio
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 03 Set 2005 11:58    Oggetto: Rispondi citando

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
Profilo Invia messaggio privato HomePage
madvero
Amministratore
Amministratore


Registrato: 05/07/05 20:42
Messaggi: 19267
Residenza: Ero il maestro Zen. Scrivevo piccole poesie Haiku. Le mandavo a tutti via e-mail.

MessaggioInviato: 09 Dic 2005 00:09    Oggetto: Rispondi citando

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
Profilo Invia messaggio privato Invia e-mail HomePage
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 09 Dic 2005 00:23    Oggetto: Rispondi citando

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
Profilo Invia messaggio privato HomePage
madvero
Amministratore
Amministratore


Registrato: 05/07/05 20:42
Messaggi: 19267
Residenza: Ero il maestro Zen. Scrivevo piccole poesie Haiku. Le mandavo a tutti via e-mail.

MessaggioInviato: 09 Dic 2005 00:29    Oggetto: Rispondi citando

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
Profilo Invia messaggio privato Invia e-mail HomePage
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 09 Dic 2005 01:29    Oggetto: Rispondi citando

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. Rolling Eyes

E poichè la somma dei primi n interi è n(n+1)/2 ecco svelato il perchè del 45 ... Laughing
Top
Profilo Invia messaggio privato HomePage
madvero
Amministratore
Amministratore


Registrato: 05/07/05 20:42
Messaggi: 19267
Residenza: Ero il maestro Zen. Scrivevo piccole poesie Haiku. Le mandavo a tutti via e-mail.

MessaggioInviato: 09 Dic 2005 01:34    Oggetto: Rispondi citando

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
Profilo Invia messaggio privato Invia e-mail HomePage
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 06 Gen 2006 16:02    Oggetto: Rispondi citando

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
Profilo Invia messaggio privato HomePage
madvero
Amministratore
Amministratore


Registrato: 05/07/05 20:42
Messaggi: 19267
Residenza: Ero il maestro Zen. Scrivevo piccole poesie Haiku. Le mandavo a tutti via e-mail.

MessaggioInviato: 06 Gen 2006 18:37    Oggetto: Rispondi citando

gauss, è vero!!! d'oh!
grazie...
Top
Profilo Invia messaggio privato Invia e-mail HomePage
Eureka
Mortale devoto
Mortale devoto


Registrato: 30/03/06 17:08
Messaggi: 19

MessaggioInviato: 02 Apr 2006 13:37    Oggetto: Rispondi citando

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 Twisted Evil Twisted Evil
una volta scritto o copia-incollato il sudoku nella tavola basterà premere il pulsante "load" e poi il pulsante "risolutore".
Twisted Evil Twisted Evil Twisted Evil Twisted Evil

ops Rolling Eyes non so come permettervi di scaricare il file Sad qlc consiglio?
Top
Profilo Invia messaggio privato
Benny
Moderatore Hardware e Networking
Moderatore Hardware e Networking


Registrato: 28/01/06 14:35
Messaggi: 6382
Residenza: Non troppo vicino, mai troppo lontano

MessaggioInviato: 02 Apr 2006 14:02    Oggetto: Rispondi citando

Eureka ha scritto:
ops Rolling Eyes non so come permettervi di scaricare il file Sad qlc consiglio?

Controlla qui...
Ci sono diversi siti dove poter uploadare vari tipi di file... vedi quello che fa al caso tuo!
Ciao
Top
Profilo Invia messaggio privato
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 03 Apr 2006 13:53    Oggetto: Rispondi citando

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
Profilo Invia messaggio privato HomePage
Eureka
Mortale devoto
Mortale devoto


Registrato: 30/03/06 17:08
Messaggi: 19

MessaggioInviato: 04 Apr 2006 13:55    Oggetto: Rispondi citando

grazie Benny per l'aiuto Wink
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
Profilo Invia messaggio privato
den
Mortale adepto
Mortale adepto


Registrato: 28/09/06 13:38
Messaggi: 30
Residenza: BG provincia

MessaggioInviato: 09 Ott 2006 13:41    Oggetto: Rispondi citando

... torno un pò anch'io sui sudoku, vi fa niente Very Happy ?

è 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
Profilo Invia messaggio privato
ulisse
Dio maturo
Dio maturo


Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)

MessaggioInviato: 10 Ott 2006 10:14    Oggetto: Rispondi citando

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
Profilo Invia messaggio privato HomePage
chemicalbit
Dio maturo
Dio maturo


Registrato: 01/04/05 17:59
Messaggi: 18597
Residenza: Milano

MessaggioInviato: 10 Ott 2006 21:57    Oggetto: Rispondi citando

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
Profilo Invia messaggio privato
madvero
Amministratore
Amministratore


Registrato: 05/07/05 20:42
Messaggi: 19267
Residenza: Ero il maestro Zen. Scrivevo piccole poesie Haiku. Le mandavo a tutti via e-mail.

MessaggioInviato: 10 Ott 2006 22:23    Oggetto: Rispondi citando

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.

Twisted Evil Twisted Evil Twisted Evil

e fra me e il sudoku, fu un triste e cruento divorzio.
Top
Profilo Invia messaggio privato Invia e-mail HomePage
den
Mortale adepto
Mortale adepto


Registrato: 28/09/06 13:38
Messaggi: 30
Residenza: BG provincia

MessaggioInviato: 11 Ott 2006 10:27    Oggetto: Rispondi citando

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) Smile vuol dire che non son poi così malato Laughing

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 Smile

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 Rolling Eyes
Top
Profilo Invia messaggio privato
madvero
Amministratore
Amministratore


Registrato: 05/07/05 20:42
Messaggi: 19267
Residenza: Ero il maestro Zen. Scrivevo piccole poesie Haiku. Le mandavo a tutti via e-mail.

MessaggioInviato: 11 Ott 2006 11:05    Oggetto: Rispondi citando

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
Profilo Invia messaggio privato Invia e-mail HomePage
den
Mortale adepto
Mortale adepto


Registrato: 28/09/06 13:38
Messaggi: 30
Residenza: BG provincia

MessaggioInviato: 11 Ott 2006 11:21    Oggetto: Rispondi

io dicevo più per la memoria... a me bastano due numeri per dimenticarmi di quello prima...
Top
Profilo Invia messaggio privato
Mostra prima i messaggi di:   
Nuovo argomento   Rispondi    Indice del forum -> Enigmi e giochi matematici Tutti i fusi orari sono GMT + 1 ora
Vai a Precedente  1, 2
Pagina 2 di 2

 
Vai a:  
Non puoi inserire nuovi argomenti
Non puoi rispondere a nessun argomento
Non puoi modificare i tuoi messaggi
Non puoi cancellare i tuoi messaggi
Non puoi votare nei sondaggi