|
|
|
|
Strumenti |
09-06-2009, 10:26 | #41 |
Senior Member
Iscritto dal: Feb 2006
Messaggi: 1304
|
E di che
Cmq io son riuscito a risolvere tutti gli schemi che ho trovato su internet in meno di 100 ms (intorno ai 40 ms in media) sul mio E6600 @2.4ghz. La cosa strana è che non riesco a risolvere SOLO quello nell'OP, perchè per qualche motivo non riesce a trovare alcuna soluzione soddisfacente... però credevo che "tirando ad indovinare" si dovrebbe arrivare sempre alla soluzione completa, se si provano tutte le possibilità. |
11-06-2009, 21:48 | #42 |
Senior Member
Iscritto dal: Feb 2007
Città: Verona
Messaggi: 1060
|
Che io sapessi il sudoku si risolve solo attraverso brute force, che sia backtracking o qualcos'altro di più stupido. La parte interessante del risolutore sta nel trovare le ottimizzazioni migliori per tagliare fuori la più grossa parte dei tentativi nel minor tempo possibile.
Mi sembrava di aver letto che il sudoku è un problema NP-completo. Proprio un questi giorni mi era venuto in mente di scrivere un risolutore, e poi mi trovo questo contest!!! Vedrò se al lavoro trovo il tempo
__________________
|
11-06-2009, 22:11 | #43 | |
Senior Member
Iscritto dal: Dec 2007
Messaggi: 1300
|
Quote:
Codice:
0,0,0 0,0,0 1,0,0 0,x,x 0,0,0 0,0,0 0,x,x 0,0,0 0,0,0 0,0,0 0,0,1 0,0,0 0,x,x 0,0,0 0,0,0 0,x,Y 0,0,0 0,0,0 0,0,0 0,0,0 0,0,0 0,0,0 0,0,0 0,0,0 0,0,0 0,0,0 0,0,0 o ho capito male? saresti obbligato, finita la parte di completamento o ad implementare un'IA che sappia fare questi passaggi o il brute force... risolto questo problema, penso che tu possa risolvere qualsiasi schema bio |
|
12-06-2009, 10:37 | #44 |
Senior Member
Iscritto dal: May 2008
Messaggi: 530
|
■
Ultima modifica di rеpne scasb : 18-06-2012 alle 15:36. |
12-06-2009, 10:39 | #45 |
Senior Member
Iscritto dal: May 2008
Messaggi: 530
|
■
Ultima modifica di rеpne scasb : 18-06-2012 alle 15:36. |
12-06-2009, 10:56 | #46 | |
Senior Member
Iscritto dal: May 2004
Città: Londra (Torino)
Messaggi: 3691
|
Quote:
1,2,3,4 2,x,x,3 3,x,x,2 4,3,2,1 Dove nelle x si possono mettere o 4 o 1 ma ci sono 2 schemi possibili entrambi validi. Tanto io parlo, ma non ho ancora scritto mezza riga (e chissa' quando lo faro'...) Immagino si possano costruire schemi in cui non siano implicate solo 4 celle, ma magari di piu', con piu' possibili schemi di risposta tutti validi.
__________________
Se pensi che il tuo codice sia troppo complesso da capire senza commenti, e' segno che molto probabilmente il tuo codice e' semplicemente mal scritto. E se pensi di avere bisogno di un nuovo commento, significa che ti manca almeno un test. |
|
12-06-2009, 11:18 | #47 | |
Bannato
Iscritto dal: Jan 2003
Città:
Messaggi: 4400
|
Quote:
...ciao Andrea... |
|
12-06-2009, 11:21 | #48 |
Member
Iscritto dal: Jul 2008
Messaggi: 237
|
Errore, supererrore. Se vedi il sudoku come una matrice puoi scrivere un sistema di equazioni e disequazioni da soddisfare. Detto questo qualunque schema di sudoku è risolvibile senza brute forcing, risolvendo il sistema. Naturalmente il sistema può non avere soluzioni e a quel punto il sudoku è impossibile e può essere dimostrato matematicamente, altrimenti il sistema può avere una soluzione o un numero n finito di soluzioni e per trovarle non è certamente necessario il brute force
|
12-06-2009, 11:23 | #49 | |
Bannato
Iscritto dal: Jan 2003
Città:
Messaggi: 4400
|
...infatti...
Quote:
|
|
12-06-2009, 11:59 | #50 |
Senior Member
Iscritto dal: May 2008
Messaggi: 530
|
■
Ultima modifica di rеpne scasb : 18-06-2012 alle 15:36. |
12-06-2009, 16:03 | #51 | |
Senior Member
Iscritto dal: Feb 2007
Città: Verona
Messaggi: 1060
|
Quote:
http://freeuser.org/2008/01/03/sudok...e-np-completo/ Quello che tu chiami sistema di equazioni è in realtà un SAT, problema NP-completo.
__________________
|
|
12-06-2009, 16:37 | #52 |
Senior Member
Iscritto dal: May 2008
Messaggi: 530
|
■
Ultima modifica di rеpne scasb : 18-06-2012 alle 15:36. |
12-06-2009, 17:47 | #53 | |
Senior Member
Iscritto dal: Jun 2002
Città: Dublin
Messaggi: 5964
|
Quote:
__________________
C'ho certi cazzi Mafa' che manco tu che sei pratica li hai visti mai! |
|
12-06-2009, 18:01 | #54 |
Senior Member
Iscritto dal: Oct 2001
Messaggi: 11471
|
Strano. Questo sulla mia soluzione in ruby ed è praticamente istantaneo a differenza di quello proposto da !k-0t1c! nel primo messaggio che impiega una vita.
|
12-06-2009, 18:09 | #55 |
Senior Member
Iscritto dal: Dec 2007
Messaggi: 1300
|
settimana enigmistica di questa settimana:
Codice:
0,0,7 0,0,8 0,0,0 0,1,0 0,0,0 3,0,0 0,0,0 4,0,0 0,0,9 0,8,0 0,9,0 0,0,6 0,2,0 0,0,0 0,7,0 5,0,0 0,3,0 0,4,0 9,0,0 0,0,6 0,0,0 0,0,4 0,0,0 0,1,0 0,0,0 2,0,0 8,0,0 Codice:
0,4,7 0,0,8 0,0,0 0,1,0 0,0,0 3,0,0 0,0,0 4,0,0 0,0,9 0,8,0 0,9,0 0,0,6 0,2,0 0,0,0 0,7,0 5,0,0 0,3,0 0,4,0 9,0,0 0,0,6 0,0,0 0,0,4 0,0,0 0,1,0 0,0,0 2,0,0 8,9,0 bio |
12-06-2009, 18:13 | #56 | ||
Member
Iscritto dal: Jul 2008
Messaggi: 237
|
@DanieleC88
Quote:
Vediamo un po' con cosa se ne esce repne Edit: per quanto riguarda quello di bio82 segue la soluzione, sempre grazie al solver usando 1po' di CP Quote:
Ultima modifica di !k-0t1c! : 12-06-2009 alle 18:16. |
||
12-06-2009, 18:19 | #57 |
Senior Member
Iscritto dal: May 2008
Messaggi: 530
|
■
Ultima modifica di rеpne scasb : 18-06-2012 alle 15:36. |
12-06-2009, 18:20 | #58 |
Senior Member
Iscritto dal: May 2008
Messaggi: 530
|
■
Ultima modifica di rеpne scasb : 18-06-2012 alle 15:37. |
12-06-2009, 19:32 | #59 |
Senior Member
Iscritto dal: May 2008
Messaggi: 530
|
■
Ultima modifica di rеpne scasb : 18-06-2012 alle 15:37. |
12-06-2009, 19:36 | #60 | |
Senior Member
Iscritto dal: Jun 2002
Città: Dublin
Messaggi: 5964
|
Quote:
ciao
__________________
C'ho certi cazzi Mafa' che manco tu che sei pratica li hai visti mai! |
|
Strumenti | |
|
|
Tutti gli orari sono GMT +1. Ora sono le: 17:01.