| Precedente :: Successivo |
| Autore |
Messaggio |
ulisse
Dio maturo
Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)
|
 Inviato: 03 Apr 2006 13:53 Oggetto: |
 |
|
| Eureka ha scritto: | | anche io tempo fà ho sviluppato un risolutore di sudoku in excel e VBA, risolve tutti i tipi di sudoku basta dargli tempo... |
Che strategie hai adottato?
Solo forza bruta oppure hai implementato degli algoritmi che riconoscono particolari configurazioni e le trattano di conseguenza?
Se li risolve tutti certamente ti sei piegato alla forza bruta (ho dovuto adottarla anch'io perché ci sono problemi che non sono risolubili per altra via).
La parte più divertente per me è stata proprio la ricerca delle strategie risolutive... |
|
| Top |
|
 |
Eureka
Mortale devoto
Registrato: 30/03/06 17:08
Messaggi: 19
|
| Inviato: 04 Apr 2006 13:55 Oggetto: |
|
|
grazie Benny per l'aiuto 
scusate il ritardo ma sono stato un pò impegnato....
@ulisse il programma risolve il problema attraverso una ricerca esaustiva della soluzione, almeno per i sudoku categorizzati difficili, mentre per quelli mediamente difficili la risoluzione segue un suo schema
il file:
 |
|
| Top |
|
|
den
Mortale adepto
Registrato: 28/09/06 13:38
Messaggi: 30
Residenza: BG provincia
|
| Inviato: 09 Ott 2006 13:41 Oggetto: |
|
|
... torno un pò anch'io sui sudoku, vi fa niente  ?
è da quando c'è stato il boom dei sudoku più di un anno fa che mi son fatto questa domanda (io NON ho ancora la risposta, e a mio avviso è una domanda piuttosto difficile, probabilmente legata a ciò che è già stato detto in questo post sul numero di soluzioni possibili).
La domanda è:
Qual'è il numero MINIMO di numeri che possono essere presenti nella griglia di partenza affinchè garantiscano l'unicità della soluzione?
io ho visto ad esempio su qualche rivista sudoku di difficoltà "diabolica, per geni" o simili che contenevano meno di 20 numeri (non ricordo di preciso), ed in più si garantiva l'unicità della soluzione...
Il fatto che poi si riescano a risolvere solo con l'ausilio della logica o invece per tentativi è un altro discorso
Ps non penso sia di grande interesse considerare se i sudoku son perfetti o meno (cioè simmetrici rispetto al punto centrale, nel senso che se si trova un numero nella casella A2 se ne deve trovare uno anche in I8). |
|
| Top |
|
|
ulisse
Dio maturo
Registrato: 02/03/05 01:09
Messaggi: 1531
Residenza: Bagnone (MS)
|
| Inviato: 10 Ott 2006 10:14 Oggetto: |
|
|
| den ha scritto: | | Qual'è il numero MINIMO di numeri che possono essere presenti nella griglia di partenza affinchè garantiscano l'unicità della soluzione? |
Che io sappia non è stata trovata risposta definitiva.
Ricordo che qualcosa di rigoroso era stato scritto sull'argomento ma non esaustivo.
Ci sono in rete (in inglese) alcuni forum dedicati esclusivamente ai Sudoku (e nei post precedenti dovrebbero esserci i link. Se non li trovi chiedimi che io li ho memorizzati da qualche parte) che affrontano il gioco dal punto di vista matematico.
| den ha scritto: | | Il fatto che poi si riescano a risolvere solo con l'ausilio della logica o invece per tentativi è un altro discorso |
E' dimostrato che esistono problemi risolubili senza l'ausilio della forza bruta.
Di converso esistono problemi la cui risoluzione, almeno sinora, non può fare a meno della forza bruta (ovvero nessuno ha dimostrato che non si può fare diversamente ma nessuno ha trovato una strategia che funzioni anche in quei casi)
| den ha scritto: | | Ps non penso sia di grande interesse considerare se i sudoku son perfetti o meno (cioè simmetrici rispetto al punto centrale, nel senso che se si trova un numero nella casella A2 se ne deve trovare uno anche in I8 ). |
I Sudoku non sono simmetrici nel senso che se trovi un numero in A2 non é detto che lo stesso numero compaia in I8 ma, per definizione di sudoku (almeno secondo la definizione del suo inventore giapponese), la griglia di partenza deve essere simmetrica come posizione, non come contenuto ovvero se e' esposta la cella A2 deve esserlo anche I8 ma non necessariamente con lo stesso numero. |
|
| Top |
|
|
chemicalbit
Dio maturo
Registrato: 01/04/05 17:59
Messaggi: 18597
Residenza: Milano
|
| Inviato: 10 Ott 2006 21:57 Oggetto: |
|
|
| ulisse ha scritto: | | la griglia di partenza deve essere simmetrica come posizione, non come contenuto ovvero se e' esposta la cella A2 deve esserlo anche I8 ma non necessariamente con lo stesso numero. |
Uh ... non lo sapevo (forse c'avevo fato caso, ma non l'avevo ... memorizzato).
Della serie: non si finisce mai d'imparare. |
|
| 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: 10 Ott 2006 22:23 Oggetto: |
|
|
devo dedurne che nessuno si è allietato le vacanze estive con il libro dei sudoku proposti ai campionati mondiali di lucca.
lì di simmetrico c'erano solo le mie bestemmie nell'apprendere che dove io ho impiegato 45 minuti buoni, i campioni ne hanno sprecato sì e no 6.
e fra me e il sudoku, fu un triste e cruento divorzio. |
|
| Top |
|
|
den
Mortale adepto
Registrato: 28/09/06 13:38
Messaggi: 30
Residenza: BG provincia
|
| Inviato: 11 Ott 2006 10:27 Oggetto: |
|
|
| ulisse ha scritto: | | den ha scritto: | | Qual'è il numero MINIMO di numeri che possono essere presenti nella griglia di partenza affinchè garantiscano l'unicità della soluzione? |
Che io sappia non è stata trovata risposta definitiva.
Ricordo che qualcosa di rigoroso era stato scritto sull'argomento ma non esaustivo.
Ci sono in rete (in inglese) alcuni forum dedicati esclusivamente ai Sudoku (e nei post precedenti dovrebbero esserci i link. Se non li trovi chiedimi che io li ho memorizzati da qualche parte) che affrontano il gioco dal punto di vista matematico. |
Già mi stupisco che anche altri si siano posti la mia stessa domanda sui Sudoku (tipò questa sul numero minimo per garantire l'unicità della soluzione)  vuol dire che non son poi così malato 
Riguardo ai link li ho trovati nelle pagine precedenti del forum. Qualche occhiata ce la sto dando e ce la darò (benchè io con l'inglese non vada troppo a braccetto, specie se così specifico, ma mi ci sto abituando visti i testi universitari che per certe materie sono solo in inglese). Grazie comunque per la disponibilità.
| ulisse ha scritto: | | den ha scritto: | | Il fatto che poi si riescano a risolvere solo con l'ausilio della logica o invece per tentativi è un altro discorso |
E' dimostrato che esistono problemi risolubili senza l'ausilio della forza bruta.
Di converso esistono problemi la cui risoluzione, almeno sinora, non può fare a meno della forza bruta (ovvero nessuno ha dimostrato che non si può fare diversamente ma nessuno ha trovato una strategia che funzioni anche in quei casi) |
Beh per quel che riguarda i sudoku a mio avviso se garantiscono l'unicità della soluzione si risolvono solo per logica, in quanto è logica anche fare il ragionamento di provare un numero su una casella che ha più opzioni
(es. se va quel numero lì allora ci va questo là, e dopo 20 passaggi arrivi a vedere 2 numeri uguali sulla stessa riga --> scarto quel numero iniziale)
A mio avviso è logica anche questa, anche se io ragionamenti così lunghi e astrusi da fare solo a mente li definisco "per tentativi".
Ho però sentito di maestri giapponesi che guardano la griglia, si fanno la loro immagine mentale, se la risolvono tutta a mente e solo quando vedono la soluzione completa la scrivono... beh geni o allucinati è più o meno la stessa cosa
| ulisse ha scritto: | | den ha scritto: | | Ps non penso sia di grande interesse considerare se i sudoku son perfetti o meno (cioè simmetrici rispetto al punto centrale, nel senso che se si trova un numero nella casella A2 se ne deve trovare uno anche in I8 ). |
I Sudoku non sono simmetrici nel senso che se trovi un numero in A2 non é detto che lo stesso numero compaia in I8 ma, per definizione di sudoku (almeno secondo la definizione del suo inventore giapponese), la griglia di partenza deve essere simmetrica come posizione, non come contenuto ovvero se e' esposta la cella A2 deve esserlo anche I8 ma non necessariamente con lo stesso numero. |
Sì, intendevo anch'io simmetrica la posizione, non il numero in sè. Comunque precisazione utile in quanto sono stato io un pò approssimativo con i termini, in effetti non sono molto chiaro  |
|
| 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: 11 Ott 2006 11:05 Oggetto: |
|
|
| den ha scritto: | | Ho però sentito di maestri giapponesi che guardano la griglia, si fanno la loro immagine mentale, se la risolvono tutta a mente e solo quando vedono la soluzione completa la scrivono... beh geni o allucinati è più o meno la stessa cosa |
ma perchè, tu come li risolvi i sudoku? guardi la griglia finchè non "vedi" un tot di numeri sicuri, e poi li scrivi. la differenza sta nel fatto che il più abile li continua a tenere a mente finchè non ha finito... |
|
| Top |
|
|
den
Mortale adepto
Registrato: 28/09/06 13:38
Messaggi: 30
Residenza: BG provincia
|
| Inviato: 11 Ott 2006 11:21 Oggetto: |
 |
|
| io dicevo più per la memoria... a me bastano due numeri per dimenticarmi di quello prima... |
|
| Top |
|
|
|
FAQ
Cerca
Lista utenti
Gruppi
Registrati
Profilo
Messaggi privati
Log in
