| Precedente :: Successivo |
| Autore |
Messaggio |
ioSOLOio
Amministratore
Registrato: 12/09/03 18:01
Messaggi: 16342
Residenza: in un sacco di...acqua
|
 Inviato: 02 Set 2005 14:30 Oggetto: |
 |
|
| Ulisse ha scritto: |
Tra l'altro mi ha fatto scoprire un paio di buchi nel mio set di regole...  |
quindi presto rilascerai una patch ?
 |
|
| Top |
|
 |
timendum
Mortale devoto
Registrato: 01/09/05 09:23
Messaggi: 11
|
| Inviato: 02 Set 2005 15:07 Oggetto: |
|
|
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 |
|
|
ZapoTeX
Dio maturo
Registrato: 04/06/04 16:18
Messaggi: 2627
Residenza: Universo conosciuto
|
| Inviato: 02 Set 2005 16:03 Oggetto: |
|
|
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 |
|
|
ulisse
Dio maturo
Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)
|
| Inviato: 02 Set 2005 16:34 Oggetto: |
|
|
| ioSOLOio ha scritto: | quindi presto rilascerai una patch ?
|
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 |
|
|
ulisse
Dio maturo
Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)
|
| Inviato: 02 Set 2005 16:42 Oggetto: |
|
|
| 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 |
|
|
ulisse
Dio maturo
Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)
|
| Inviato: 02 Set 2005 18:30 Oggetto: |
|
|
| 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... 
Il post sopra linkato risponde alle tue domande. |
|
| Top |
|
|
ulisse
Dio maturo
Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)
|
| Inviato: 02 Set 2005 19:19 Oggetto: |
|
|
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 |
|
|
ZapoTeX
Dio maturo
Registrato: 04/06/04 16:18
Messaggi: 2627
Residenza: Universo conosciuto
|
| Inviato: 02 Set 2005 19:50 Oggetto: |
|
|
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 |
|
|
Gateo
Dio maturo
Registrato: 17/11/03 18:16
Messaggi: 12379
|
| Inviato: 03 Set 2005 08:19 Oggetto: |
|
|
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 |
|
|
ulisse
Dio maturo
Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)
|
| Inviato: 03 Set 2005 11:39 Oggetto: |
|
|
| 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'... |
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 |
|
|
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 |
|
|
|
FAQ
Cerca
Lista utenti
Gruppi
Registrati
Profilo
Messaggi privati
Log in
