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
ioSOLOio
Amministratore
Amministratore


Registrato: 12/09/03 18:01
Messaggi: 16342
Residenza: in un sacco di...acqua

MessaggioInviato: 02 Set 2005 14:30    Oggetto: Rispondi citando

Ulisse ha scritto:

Tra l'altro mi ha fatto scoprire un paio di buchi nel mio set di regole... Evil or Very Mad


quindi presto rilascerai una patch ?
Laughing
Top
Profilo Invia messaggio privato
timendum
Mortale devoto
Mortale devoto


Registrato: 01/09/05 09:23
Messaggi: 11

MessaggioInviato: 02 Set 2005 15:07    Oggetto: Rispondi citando

Io ho trovato qualche informazione sul sudoku e un risolutore applet java su Base Cinque, che potrebbe avere anche una trattazione più matematica di altri.

Timendum che qualche settimana fa ha cercato per intaresse.
Top
Profilo Invia messaggio privato
ZapoTeX
Dio maturo
Dio maturo


Registrato: 04/06/04 16:18
Messaggi: 2624
Residenza: Universo conosciuto

MessaggioInviato: 02 Set 2005 16:03    Oggetto: Rispondi citando

Io come prima domanda mi ero chiesto: quanti sono i modi di risolvere un sodoku partendo da tutte le caselle vuote?

Ovviamente intendo modi non riconducibili uno all'altro tramite permutazione del significato delle cifre (ad es 1 -> 4, 4 -> 1 ma anche permutazioni più complicate che coinvolgano tutte e 9 le cifre)

Se il numero è ragionevole pensavo di far riconoscere al programma quale modo si applica, permutare opportunamente le cifre et voila la soluzione è pronta!

Hai proceduto così o diversamente? Io vinto dalla pigrizia mi sono arreso dopo 20 min, tempo entro il quale non sono riuscito a determinare il numero di modi, ma forse ci ho pensato in termini inadatti.

Ciao!
Top
Profilo Invia messaggio privato HomePage
ulisse
Dio maturo
Dio maturo


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

MessaggioInviato: 02 Set 2005 16:34    Oggetto: Rispondi citando

ioSOLOio ha scritto:
quindi presto rilascerai una patch ?
Laughing


Very Happy Very Happy
La tentazione di implementare la regola mancante è forte...
Devo vedere se posso intervenire senza stravolgere l'intero programma.

Il problema è che lo stimolo a procedere è smorzato dalla mancanza di un set completo di regole.

Ovvero esistono vari problemi che non possono essere risolti senza forza bruta (provare sistematicamente tutte le possibilità fino a che non si incappa in quella corretta).

Per essere precisi, nessuno sinora ha trovato un sistema completo di regole (magari esiste...)

Di più: nessuno sinora ha trovato un modo per verificare a priori l'esistenza e l'unicità della soluzione.
L'unico modo consiste nel contare tutte le soluzioni possibili (che, ovviamente, prima vanno ricavate).
Top
Profilo Invia messaggio privato HomePage
ulisse
Dio maturo
Dio maturo


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

MessaggioInviato: 02 Set 2005 16:42    Oggetto: Rispondi citando

timendum ha scritto:
Io ho trovato qualche informazione sul sudoku e un risolutore applet java su Base Cinque, che potrebbe avere anche una trattazione più matematica di altri.

Timendum che qualche settimana fa ha cercato per intaresse.


Grazie per il link. Base 5 mi era già noto ma in merito ai sudoku di matematico ha ben poco (contiene anche qualche errore grossolano).

La trattazione matematica più dettagliata l'ho trovata su questo forum.

Per ora, però, non ho trovato nessun modello matematico rigoroso.
Anzi, devo far mente locale perchè ricordo di aver letto un articolo (universitario) sulla matematica combinatoria applicata ai sudoku ma non ricordo più dove...
Top
Profilo Invia messaggio privato HomePage
ulisse
Dio maturo
Dio maturo


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

MessaggioInviato: 02 Set 2005 18:30    Oggetto: Rispondi citando

ZapoTex ha scritto:
Io come prima domanda mi ero chiesto: quanti sono i modi di risolvere un sodoku partendo da tutte le caselle vuote?


Le possibili configurazioni valide (ovvero le griglie 9x9 contenenti numeri da 1 a 9 che rispettano la regola dei sudoku) sono tante, mostruosamente tante.

Così tante che non mi risulta nessuno sia riuscito a contarle.

Il vero nodo è che nessuno (a mia conoscenza) ha ancora modellizzato il problema.
Non esistendo un modello matematico risulta anche difficile determinare la dimensione.

Quello che è stato fatto è contare le possibili soluzioni ottenibili per trasformazione a partire da una soluzione valida.
Matematicamente parlando l'insieme delle soluzioni può essere suddiviso in classi di equivalenza.
Due soluzioni appartengono alla stessa classe se sono ottenibili l'una dall'altra attraverso una trasformazione (resta da definire il tipo di trasformazioni di cui stiamo parlando).

In maniera erronea su web si afferma che tutte e sole le trasformazioni che ti fanno passare da una soluzione ad un'altra equivalente sono:
1) permutazioni sui numeri; essendoci 9 numeri le permutazioni possibili e distinte tra loro sono 9!=362.880
2) permutazioni sulle righe di una stessa linea di blocchi (non si possono permutare due righe appartenenti a due blocchi distinti senza rischiare di scombinare irrimediabilmente i blocchi) che sono 3!=6 per linea di blocchi e quindi, in totale, sono 6^3
3) permutazioni sulle colonne di una stessa linea di blocchi; anche queste sono in numero di 6^3
4) permutazioni per riga delle linee di blocchi che sono sempre 3!
5) permutazioni per colonna delle linee di blocchi (ancora 3!)

per un totale di 9!*6^8=609.499.054.080 soluzioni equivalenti

Peccato che tutti abbiamo dimenticato la trasposizione (che consiste nello scambiare tra loro le righe con le colonne) e quindi abbiano trascurato un fattore 2.

Rettifico: qui hanno corretto i conti dopo la mia ultima visita. Mi pare vadano oltre le mie conoscenze. Vedrò di studiare il post per capirci qualcosa... Rolling Eyes

Il post sopra linkato risponde alle tue domande.
Top
Profilo Invia messaggio privato HomePage
ulisse
Dio maturo
Dio maturo


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

MessaggioInviato: 02 Set 2005 19:19    Oggetto: Rispondi citando

Aah... ho trovato!
Ecco un articolo che pone fine al quesito sul numero di configurazioni valide.

Ora me lo leggo!

Inoltre ho trovato un altro forum in cui trattano gli aspetti matematici del gioco.
Top
Profilo Invia messaggio privato HomePage
ZapoTeX
Dio maturo
Dio maturo


Registrato: 04/06/04 16:18
Messaggi: 2624
Residenza: Universo conosciuto

MessaggioInviato: 02 Set 2005 19:50    Oggetto: Rispondi citando

Io per fini implementativi davo molto rilievo alla suddivisione in classi di equivalenza rispetto alla permutazione delle cifre... Nei pochi minuti di riflessione (basata su un sudoku 4 x 4 diviso in quattro blocchi) mi ero reso conto che scambiando righe e colonne si ottengono cose non ottenibili per semplice permutazione delle cifre, dunque ero arrivato a dire che, per la mia suddivisione in classi, il numero di classi era maggiore di uno.

Per la trasposizione: sicuro si ottenga roba non ottenibile altrimenti?

Ciao!
Top
Profilo Invia messaggio privato HomePage
Gateo
Dio maturo
Dio maturo


Registrato: 17/11/03 18:16
Messaggi: 12379

MessaggioInviato: 03 Set 2005 08:19    Oggetto: Rispondi citando

Gia' che ci siete, riuscite ad implementare le regole per questa variante?
Perche' ci ho dato un'occhiata, ma l'ho trovato decisamente al di la' delle mie possibilita'...
Top
Profilo Invia messaggio privato
ulisse
Dio maturo
Dio maturo


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

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

Gateo ha scritto:
Gia' che ci siete, riuscite ad implementare le regole per questa variante?
Perche' ci ho dato un'occhiata, ma l'ho trovato decisamente al di la' delle mie possibilita'...


Very Happy Very Happy Very Happy e io che avevo già preso carta e penna ed ero pronto ad un pomeriggio di studio!!!

La variante da te indicata ha una sola regola, la stessa seguita dall'acqua nella determinazione del proprio percorso verso il mare: l'orografia del terreno determina, in congiunzione con la forza di gravità, un campo caratterizzato da un potenziale. L'acqua tende a dirigersi verso i punti di minimo del potenziale del campo.

I politici fanno altrettanto: il campo qui rappresenta la forza disponibile, il potenziale altro non è che il potere e l'orografia del terreno è la situazione sociale. Dunque, come l'acqua, i politici tendono a muoversi verso le concentrazioni di potere che le particolari congiunture socio-economico- politico creano...
Top
Profilo Invia messaggio privato HomePage
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

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
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 1, 2  Successivo
Pagina 1 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