Sudoku - il rompicapo giapponese

Cinema, Peperoncini, Navi Spaziali, Barbecue, Fisica Quantistica… TUTTO!
User avatar
snuffz
Veteran
Veteran
Posts: 4380
Joined: Jan 2003
Location: Torino
Contact:

Post by snuffz » 29/09/2005 16:36

Ciao Lysor :flower:
Comprati LogicArt. Sodoku e molti altri giochi (tipo mosaio, MOLTO più complesso).
Io mi sono innamorato dei Pixelink
http://www.nonzero.it/gms_lap_01.php

User avatar
snuffz
Veteran
Veteran
Posts: 4380
Joined: Jan 2003
Location: Torino
Contact:

Post by snuffz » 29/12/2005 16:33

Il sudoku è già finito nel dimenticatoio... comunque per chi avesse voglia di provare un programmino a tema: eccolo qui!
http://oostyle.net/oouploader30/uploads ... _setup.zip

Molte le funzioni a disposizione, ad esempio la casella consigliata, il "risolvi la prossima mossa", e la possibilità di personalizzare colori, dimensioni e altro.
:xmas:

User avatar
Nyarlath
Fo.Orum PRO
Fo.Orum PRO
Posts: 589
Joined: Mar 2004

Post by Nyarlath » 11/01/2006 17:33

Scusa Snuffz era da una vita che non guardavo questa sezione...
Il tuo programma non esiste (collegamento mancante), ma immagino che faccia tutto e di piu' del mio. Se ti interessa te lo spedisco lo stesso (devo spedirtelo perche' 7ede la pass non me la vuole proprio far sapere...), ma penso che ti interessi di piu' sapere come funziona.

- Come risolve un sudoku:
Parte con una lista di 81 liste, dove ogni lista contiene i valori che la casella corrispondente puo' assumere (omg non capisco gia' piu' niente...).
Qui inizia il ciclo che continua fino alla risoluzione completa, ossia quando tutte le liste hanno lunghezza 1.
a) Se una casella puo' assumere un valore solo (ad es tutte le celle che hanno il valore dato dal problema iniziale), il suo valore viene tolto da tutte le caselle che fanno parte della sua riga, della sua colonna e del suo quadrato.
b) Se in un quadrato, in una riga o in una colonna c'e' solo una casella che puo' assumere un certo valore, tale valore le viene assegnato (e scatta automaticamente il punto a).
c) Se sia a) che b) non possono risolvere piu' niente, una (qualsiasi) delle caselle che puo' assumere meno valori li assume tutti, uno alla volta.
Si torna a provare a) e b), e se caso si fa ancora c) finche' non si puo' piu' fare niente: se si trova una soluzione la si scrive nello schema, se invece c'e' un conflitto (si trova una casella che non puo' assumere alcun valore), si torna indietro fino ad un punto c) e si prova con un altro valore per quella casella.
(Se sai cos'e la recursione e' semplice.)
Questo metodo si basa sul back-tracking, il pc prova tutte le strade finche' una non lo porta alla fine. Ci sarebbero anche ragionamenti piu' sofisticati da fare e aggiungere ad a) e b) prima di fare c) (tipo se ci sono due caselle nella stessa riga che solo loro possono assumere 2 valori, togliere tali valori come possibili per le altre caselle di quella riga), ma i test da fare sarebbero troppi rispetto al numero di possibilita' che vengono scartate.
Il mio programma assegna un livello di difficolta' ai sudoku, relativo al numero di recursioni che necessita per risolverlo.

Spero che si capisca altrimenti non esitate a chiedere!

- Come generare un sudoku:
Parte dalla soluzione: crea un sudoku (risolto) il piu' possibile a caso. Ciclo fino a sudoku completo: prende una casella con valore non ancora assegnato qualsiasi e le assegna un valore qualsiasi tra quelli che puo' assumere (se il sudoku non puo' piu' essere risolto dopo l'assegnamento, un'altro valore viene testato).
Una volta che si ha il sudoku finito, si procede all'inverso.
Per ottantun volte si prende una casella (che non sia gia' stata scelta) a caso, le si toglie il valore fisso e si prova a risolvere il sudoku: se la soluzione e' ancora una sola, la casella viene sbiancata; se invece ci sono piu' soluzioni, quel numero e' indispensabile e viene riassegnato a quella casella, e si passa a testarne un'altra.
Le prime testate "perdono" praticamente sempre il loro valore, le ultime mai: per questo e' importante testarle in ordine casuale. Se si vuole un sudoku bizzarro, ad esempio con la prima riga completamente vuota, si possono testare le caselle seguendo il loro ordine "geografico".

Forse dovreste pagarmi per queste idee... :mrgreen:
Image
- Due lettere ripetute due volte @ Horror Gaming!

User avatar
Lysor_o.O
Veteran
Veteran
Posts: 2447
Joined: Dec 2002
Location: Milano

Post by Lysor_o.O » 11/01/2006 19:20

Ho letto e si capisce. Non ti pago :gnegne: ma mi stupisce che tu dica:
Ci sarebbero anche ragionamenti piu' sofisticati da fare e aggiungere ad a) e b) prima di fare c) (tipo se ci sono due caselle nella stessa riga che solo loro possono assumere 2 valori, togliere tali valori come possibili per le altre caselle di quella riga), ma i test da fare sarebbero troppi rispetto al numero di possibilita' che vengono scartate.
Pensavo che invece fossero cose necessarie, per poter garantire un po' di velocità. Il punto C è un approccio a forza bruta! Credevo che fosse una cosa micidiale da risolvere a forza bruta, usando solo i punti A e B. Boh... Evidentemente è solo un'impressione. Curioso, però!
Image
Tu vedi delle cose e chiedi: perché? Ma io sogno di cose che non ci sono mai state, e che forse non ci saranno mai, e dico: perché no?
--- Wolfgang Güllich

User avatar
phoenix
Veteran
Veteran
Posts: 457
Joined: Dec 2004
Location: Savvvona

Post by phoenix » 12/01/2006 18:31

bah io non ho ancor capito come si gioca al sudoku!
ma come si fa?
Mauro ma tu sei me? O io sono te? O siamo un'unico noi? per tutte queste domande c'è un'unica risposta
"sommo!"
Image

User avatar
Nyarlath
Fo.Orum PRO
Fo.Orum PRO
Posts: 589
Joined: Mar 2004

Post by Nyarlath » 12/01/2006 18:44

Creando 100 sudoku a caso penso (e' solo una stima mooolto approssimativa) che 50 si risolvano usando solo A e B, 20 usando un solo C, 10 con due C, 5 con tre, e solo per gli altri 15 dalle 4 in su.
Il massimo che ho trovato (su almeno 200 sudoku creati) e' stato di 7 recursioni.
Tante volte il B non e' evidente da vedere, e un sudoku che per noi e' difficilissimo il pc lo risolve senza neanche tirare a caso.
Contando che ogni volta che si tira a caso si ha a disposizione almeno una casella con due soli valori possibili, il numero massimo di operazioni necessarie per risolvere un sudoku e' proporzionale a 2 elevato al numero di volte che C viene sfruttato.
Quindi un sudoku difficilissimo richiede al massimo 2^7=128 volte di piu' di uno facile.
Non dico che non esista, ma io non ho trovato un metodo che necessiti "solo" 128 volte piu' operazioni che l'A o il B, e che abbia una frequenza di successo decente. Fissare un numero (C) al massimo ti raddoppia (se sei sfigato triplica) le operazioni da fare; controllare per ogni casella tutte le altre caselle per vedere se interferiscono richiede 81 volte piu' di A.
A e' dell'ordine di grandezza di 81 ed e' molto frequente, mentre B e' dell'ordine di grandezza di 3*81*9 (riga/colonna/cella*numero di caselle*numero di valori) ed e' gia' molto meno frequente.
Un altro test per essere efficace non deve quindi richiedere piu' 3*81*9 test se non riduce di oltre 1 il numero di C necessari.

Se avete delle idee saranno bene accette! :drago:
Image
- Due lettere ripetute due volte @ Horror Gaming!

User avatar
Lysor_o.O
Veteran
Veteran
Posts: 2447
Joined: Dec 2002
Location: Milano

Post by Lysor_o.O » 12/01/2006 20:02

Hai provato a testarlo con i Sudoku di livello "diabolico" del Corriere? Così, per curiosità... Vorrei sapere quanto li trova difficili il tuo programma!
Image
Tu vedi delle cose e chiedi: perché? Ma io sogno di cose che non ci sono mai state, e che forse non ci saranno mai, e dico: perché no?
--- Wolfgang Güllich

User avatar
Maloghigno
Administrator
Administrator
Posts: 4522
Joined: Dec 2002
Blizzard BattleTag: Maloghigno#2220
Contact:

Post by Maloghigno » 12/01/2006 22:59

(devo spedirtelo perche' 7ede la pass non me la vuole proprio far sapere...)
Ma figurati...
Mi hai mandato la mail di richiesta su admin@oostyle.net ? :tomato:
Image

User avatar
Nyarlath
Fo.Orum PRO
Fo.Orum PRO
Posts: 589
Joined: Mar 2004

Post by Nyarlath » 13/01/2006 10:32

Con quelli della regione non ho mai provato... questo postato da Snuffz me lo da di livello 6 (quindi già bello difficile), e con le sole regole A e B non trova nessun sicuro (quindi le recursioni iniziano subito e il problema si complica; se i bivi fossero alla fine sarebbe più veloce da risolvere).

------------------------------------------------------------

Nelle email mandate c'e' questa:
admin@oostyle.net oO uploader 3.0 Tue Sep 06, 2005 866b
Adesso te la rispedisco. :flower:
Image
- Due lettere ripetute due volte @ Horror Gaming!

User avatar
snuffz
Veteran
Veteran
Posts: 4380
Joined: Jan 2003
Location: Torino
Contact:

Post by snuffz » 13/04/2006 07:37

E mentre sulle riviste e i giornali di enigmistica cominciano ad apparire le prime versioni del Kakuro (http://www.corriere.it/kakuro), nuovo cervellotico rompicapo giapponese destinato a tenerci compagnia questa estate sotto l'ombrellone, si svolgono in Italia , precisamente a Lucca, i primi campionati del mondo di Sudoku :G:

Anche in questa manifestazione, come per i campionati italiani vinti da Giulia Franceschini, a conquistare la medaglia d'oro è una donna, la ceca Jana Tylora.


(cito dalla rivista LogicArt)
Al 1° campionato del mondo di Sudoku hanno partecipato 85 concorrenti provenienti da 22 nazioni. A farla da padrona è stata l'Europa con 16 rappresentanti, ma alcuni partecipanti si sono sobbarcati trasferte lunghissime dalle Filippine e dall'India, dal Venezuela e dal Giappone

Link

Campionato del mondo:
http://www.wsc2006.com
LogicArt
http://www.nonzero.it/

:pc:

Post Reply

Who is online

Users browsing this forum: Google [Bot] and 1 guest