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: 2606
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: 2606
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 Precedente  1, 2, 3, 4  Successivo
Pagina 2 di 4

 
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