Precedente :: Successivo |
Autore |
Messaggio |
ulisse Dio maturo
Registrato: 02/03/05 01:09 Messaggi: 1531 Residenza: Bagnone (MS)
|
Inviato: 01 Set 2005 10:23 Oggetto: * Sudoku |
|
|
Buongiorno a tutti!
Tra una passeggiata e l'altra, mi sono dilettato col pc e ho sviluppato un programmino in VBA per Excel che risolve i Sudoku (il giochino che i giornali hanno deciso essere la nuova moda dell'estate).
Dite che può interessare a qualcuno?
Prima di linkarlo ho preferito chiedere onde evitare di combinare guai.
Se null'Aosta (ma che simpatico sono ) ve lo propino...
L'ultima modifica di ulisse il 10 Dic 2005 18:09, modificato 2 volte |
|
Top |
|
|
holifay Dio maturo
Registrato: 08/03/05 09:48 Messaggi: 2912 Residenza: Milano
|
Inviato: 01 Set 2005 11:18 Oggetto: |
|
|
ma a me interessa: ne ho provato a fare uno (di quelli semplici) e ho rinunciato subito! |
|
Top |
|
|
Gateo Dio maturo
Registrato: 17/11/03 18:16 Messaggi: 12379
|
Inviato: 01 Set 2005 11:20 Oggetto: |
|
|
Su doku? Ma che e', un gioco sardo?
Linka tranquillamente, basta che non sia un dialer va bene tutto...
Io proporro' invece un sito dove c'e' un sudoku in flash nuovo ogni giorno (a me pero' non funziona, pretende i cookies) |
|
Top |
|
|
horus Macchinista
Registrato: 22/03/05 09:48 Messaggi: 2554 Residenza: Sirio e dintorni
|
Inviato: 01 Set 2005 12:36 Oggetto: |
|
|
Se vi interessa qui c'è un torneo di sudoku.
P.S.: se giocherete fatemi sapere se Lampa vi tratta bene
Edit: Sull'olimpo ne avevamo già parlato qui. |
|
Top |
|
|
emilio.roda Dio maturo
Registrato: 03/05/05 09:49 Messaggi: 3028
|
Inviato: 01 Set 2005 13:00 Oggetto: |
|
|
horus ha scritto: | Se vi interessa qui c'è un torneo di sudoku.
P.S.: se giocherete fatemi sapere se Lampa vi tratta bene
Edit: Sull'olimpo ne avevamo già parlato qui. |
L'interfaccia dei Sudoku di Repubblica non e' affatto male... e ogni giorno ce ne sono due nuovi. |
|
Top |
|
|
ulisse Dio maturo
Registrato: 02/03/05 01:09 Messaggi: 1531 Residenza: Bagnone (MS)
|
Inviato: 01 Set 2005 16:21 Oggetto: Su Doku solver |
|
|
Ok. L'avete voluto voi!
Ecco qui l'archivio zip contenente il file Excel (richiede l'abilitazione delle macro VBA) e un manualetto di spiegazioni.
A disposizione per eventuali chiarimenti.
Sappiate che trovo il gioco in sè assai noioso (nulla è lasciato alla fantasia) mentre è assai più sfidante la formalizzazione matematica del problema (non mi risulta che il problema sia stato inquadrato in maniera esaustiva) e stimolante la sua implementazione informatica. |
|
Top |
|
|
holifay Dio maturo
Registrato: 08/03/05 09:48 Messaggi: 2912 Residenza: Milano
|
Inviato: 01 Set 2005 16:48 Oggetto: |
|
|
Grazie, filo subito a studiarmelo
Non avrai protetto il codice con una password spero |
|
Top |
|
|
ulisse Dio maturo
Registrato: 02/03/05 01:09 Messaggi: 1531 Residenza: Bagnone (MS)
|
Inviato: 01 Set 2005 17:15 Oggetto: |
|
|
holifay ha scritto: | Grazie, filo subito a studiarmelo
Non avrai protetto il codice con una password spero |
Ovviamente no!
Codice a disposizione di chiunque voglia studiarselo.
Dubito però che il codice possa servire se non come esempio di come non bisogna programmare.
In ogni caso il codice è abbondantemente commentato e io sarò ben contento di soddisfare ogni tuo desiderio... limitatamente al programma, intendo |
|
Top |
|
|
horus Macchinista
Registrato: 22/03/05 09:48 Messaggi: 2554 Residenza: Sirio e dintorni
|
Inviato: 02 Set 2005 07:20 Oggetto: |
|
|
Ulisse ha scritto: | sarò ben contento di soddisfare ogni tuo desiderio... limitatamente al programma, intendo |
|
|
Top |
|
|
ulisse Dio maturo
Registrato: 02/03/05 01:09 Messaggi: 1531 Residenza: Bagnone (MS)
|
Inviato: 02 Set 2005 14:29 Oggetto: |
|
|
Credo che questo sito sia quanto di meglio si possa desiderare sul gioco.
Vi trovate un generatore di problemi con relativo risolutore, il link al forum più completo sui sudoku, links ad altri siti di interesse e un manualetto che spiega le regole di cancellazione.
Tra l'altro mi ha fatto scoprire un paio di buchi nel mio set di regole... |
|
Top |
|
|
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 |
|
|
|