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: 03 Apr 2006 13:53    Oggetto: Rispondi citando

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
Profilo Invia messaggio privato HomePage
Eureka
Mortale devoto
Mortale devoto


Registrato: 30/03/06 17:08
Messaggi: 19

MessaggioInviato: 04 Apr 2006 13:55    Oggetto: Rispondi citando

grazie Benny per l'aiuto Wink
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
Profilo Invia messaggio privato
den
Mortale adepto
Mortale adepto


Registrato: 28/09/06 13:38
Messaggi: 30
Residenza: BG provincia

MessaggioInviato: 09 Ott 2006 13:41    Oggetto: Rispondi citando

... torno un pò anch'io sui sudoku, vi fa niente Very Happy ?

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


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

MessaggioInviato: 10 Ott 2006 10:14    Oggetto: Rispondi citando

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


Registrato: 01/04/05 17:59
Messaggi: 18597
Residenza: Milano

MessaggioInviato: 10 Ott 2006 21:57    Oggetto: Rispondi citando

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
Profilo Invia messaggio privato
madvero
Amministratore
Amministratore


Registrato: 05/07/05 20:42
Messaggi: 19146
Residenza: Ero il maestro Zen. Scrivevo piccole poesie Haiku. Le mandavo a tutti via e-mail.

MessaggioInviato: 10 Ott 2006 22:23    Oggetto: Rispondi citando

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.

Twisted Evil Twisted Evil Twisted Evil

e fra me e il sudoku, fu un triste e cruento divorzio.
Top
Profilo Invia messaggio privato Invia e-mail HomePage
den
Mortale adepto
Mortale adepto


Registrato: 28/09/06 13:38
Messaggi: 30
Residenza: BG provincia

MessaggioInviato: 11 Ott 2006 10:27    Oggetto: Rispondi citando

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) Smile vuol dire che non son poi così malato Laughing

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 Smile

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 Rolling Eyes
Top
Profilo Invia messaggio privato
madvero
Amministratore
Amministratore


Registrato: 05/07/05 20:42
Messaggi: 19146
Residenza: Ero il maestro Zen. Scrivevo piccole poesie Haiku. Le mandavo a tutti via e-mail.

MessaggioInviato: 11 Ott 2006 11:05    Oggetto: Rispondi citando

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
Profilo Invia messaggio privato Invia e-mail HomePage
den
Mortale adepto
Mortale adepto


Registrato: 28/09/06 13:38
Messaggi: 30
Residenza: BG provincia

MessaggioInviato: 11 Ott 2006 11:21    Oggetto: Rispondi

io dicevo più per la memoria... a me bastano due numeri per dimenticarmi di quello prima...
Top
Profilo Invia messaggio privato
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
Pagina 4 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