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: 01 Set 2005 10:23    Oggetto: * Sudoku Rispondi citando

Buongiorno a tutti! Very Happy

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 Very Happy ) ve lo propino...


L'ultima modifica di ulisse il 10 Dic 2005 18:09, modificato 2 volte
Top
Profilo Invia messaggio privato HomePage
holifay
Dio maturo
Dio maturo


Registrato: 08/03/05 09:48
Messaggi: 2912
Residenza: Milano

MessaggioInviato: 01 Set 2005 11:18    Oggetto: Rispondi citando

ma a me interessa: ne ho provato a fare uno (di quelli semplici) e ho rinunciato subito! Smile
Top
Profilo Invia messaggio privato
Gateo
Dio maturo
Dio maturo


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

MessaggioInviato: 01 Set 2005 11:20    Oggetto: Rispondi citando

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
Profilo Invia messaggio privato
horus
Macchinista
Macchinista


Registrato: 22/03/05 09:48
Messaggi: 2554
Residenza: Sirio e dintorni

MessaggioInviato: 01 Set 2005 12:36    Oggetto: Rispondi citando

Se vi interessa qui c'è un torneo di sudoku.

P.S.: se giocherete fatemi sapere se Lampa vi tratta bene Wink

Edit: Sull'olimpo ne avevamo già parlato qui.
Top
Profilo Invia messaggio privato
emilio.roda
Dio maturo
Dio maturo


Registrato: 03/05/05 09:49
Messaggi: 3028

MessaggioInviato: 01 Set 2005 13:00    Oggetto: Rispondi citando

horus ha scritto:
Se vi interessa qui c'è un torneo di sudoku.

P.S.: se giocherete fatemi sapere se Lampa vi tratta bene Wink

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


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

MessaggioInviato: 01 Set 2005 16:21    Oggetto: Su Doku solver Rispondi citando

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


Registrato: 08/03/05 09:48
Messaggi: 2912
Residenza: Milano

MessaggioInviato: 01 Set 2005 16:48    Oggetto: Rispondi citando

Grazie, filo subito a studiarmelo Smile

Non avrai protetto il codice con una password spero Rolling Eyes
Top
Profilo Invia messaggio privato
ulisse
Dio maturo
Dio maturo


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

MessaggioInviato: 01 Set 2005 17:15    Oggetto: Rispondi citando

holifay ha scritto:
Grazie, filo subito a studiarmelo Smile

Non avrai protetto il codice con una password spero Rolling Eyes


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 Laughing
Top
Profilo Invia messaggio privato HomePage
horus
Macchinista
Macchinista


Registrato: 22/03/05 09:48
Messaggi: 2554
Residenza: Sirio e dintorni

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

Ulisse ha scritto:
sarò ben contento di soddisfare ogni tuo desiderio... limitatamente al programma, intendo Laughing

d'oh! Sbonk
Top
Profilo Invia messaggio privato
ulisse
Dio maturo
Dio maturo


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

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

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... Evil or Very Mad
Top
Profilo Invia messaggio privato HomePage
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: 2627
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: 2627
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

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