[Vari] Contest 15

[Tommo]

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à.

[malocchio]

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

[bio82]

Originariamente inviato da rеpne scasb

Secondo me, se il Sudoku ha una soluzione "univoca" non serve alcun bruteforce (la dimostrazione del quale, mi sta impegnando piu' del previsto). A riprova, comunque, non sono riuscita a costruire un sudoku in grado di resistere alle due tecniche combinate sopracitate.

ci sono alcuni schemi che obbligano la persona a fare guessing:

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

metti il caso (non raro negli schemi difficili) che hai tutto fermo e l'unica mossa possibile sia quella di mettere 1 dove c'è la Y, il tuo sistema non può risolvere lo schema...

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

[rеpne scasb]

■

[rеpne scasb]

■

[gugoXX]

Originariamente inviato da rеpne scasb

Per poter capire mi serve un sudoku del tipo che hai in mente. Me ne fai un esempio completo?

Ho capito, uno che finisce p.es. con

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.

[ally]

Originariamente inviato da gugoXX

Ho capito, uno che finisce p.es. con

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.

...penso che la disposizione debba prevedere una sola soluzione...

...ciao Andrea...

[!k-0t1c!]

Originariamente inviato da malocchio

Che io sapessi il sudoku si risolve solo attraverso brute force, che sia backtracking o qualcos'altro di più stupido.

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

[ally]

...infatti...

Affinché una matrice incompleta sia considerata valida, ai fini del gioco, è necessario che la soluzione sia univoca, ovvero non devono sussistere due o più soluzioni differenti, nei quali casi il gioco viene considerato non valido. Nei casi di varianti di sudoku (p.es. killer, jigsaw, x, toroidale, ecc.) ulteriori condizioni devono essere verificate affinché la matrice risulti valida. La difficoltà di un sudoku non è data dalla quantità di numeri iniziali, bensì dalla loro disposizione.

...ciao Andrea...

[rеpne scasb]

■

[malocchio]

Originariamente inviato da !k-0t1c!

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

http://freeuser.org/2005/11/15/sudoku-np-completo/

http://freeuser.org/2008/01/03/sudok...e-np-completo/

Quello che tu chiami sistema di equazioni è in realtà un SAT, problema NP-completo.

[rеpne scasb]

■

[DanieleC88]

Originariamente inviato da rеpne scasb

Scusa se insisto: hai disponibili un sudoku a soluzione univoca, che sia risolvibile soltanto tramite brute-force?

Non ho verificato se ha effettivamente una soluzione univoca, ma questo mette in crisi il tuo algoritmo e quasi certamente richiede brute force con backtracking:

[VICIUS]

Originariamente inviato da DanieleC88

Non ho verificato se ha effettivamente una soluzione univoca, ma questo mette in crisi il tuo algoritmo e quasi certamente richiede brute force con backtracking:

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.

[bio82]

settimana enigmistica di questa settimana:

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

dove le uniche 2 mosse iniziali che ho trovato (2 minuti) valide entrambe a schema vuoto sono:

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

questo schema non dovrebbe avere soluzione senza bruteforce o uno schema di soluzione alternativo

bio

[!k-0t1c!]

@DanieleC88

9,5,7,1,8,4,3,6,2
2,8,1,9,6,3,4,7,5
6,4,3,7,2,5,1,9,8
4,9,6,3,5,7,8,2,1
8,7,5,4,1,2,9,3,6
3,1,2,8,9,6,5,4,7
7,2,9,5,4,8,6,1,3
5,3,4,6,7,1,2,8,9
1,6,8,2,3,9,7,5,4
Parsed and solved in 484ms

Con la mia implementazione il tempo sembra rimanere basso e tutto funziona
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

3,4,7,9,2,8,5,6,1
2,1,9,6,7,5,3,8,4
6,5,8,4,1,3,7,2,9
7,8,1,5,9,4,2,3,6
4,2,3,8,6,1,9,7,5
5,9,6,7,3,2,1,4,8
9,3,2,1,8,6,4,5,7
8,7,4,3,5,9,6,1,2
1,6,5,2,4,7,8,9,3
Parsed and solved in 490ms

il tempo sembra inchiodato li...

[rеpne scasb]

■

[rеpne scasb]

■

[rеpne scasb]

■

[DanieleC88]

Originariamente inviato da rеpne scasb

Studiato. Ha una soluzione univoca e il software che ho sviluppato non lo risolve. Sto apportando le relative modifiche affinche' sia risolvibile senza l'uso della forza bruta. Ti ringrazio.

Lyane.

Di niente, sono sempre interessato a studiare soluzioni così intelligenti, quindi se posso contribuire a migliorarle (per quel poco che posso fare...) lo faccio con piacere.

ciao