SUDOKU C++

di
dave_the_function
il
22 risposte

22 Risposte - Pagina 2

  • D
    DashKappei
    Pochi posts
    Iscritto da
    gen, 2011
    Messaggi:
    7

    Re: SUDOKU C++

    Eccomi di nuovo con un altro problema... ho creato una funzione che risolve i sudoku tramite una tabella di deque, in cui inserisco i valori possibili in quella cella, e 3 stack che si riempono di pari passo con le coordinate e la rispettiva cardinalità della cella, che il solver ha toccato.

    Essa ha questa logica:
    - Cerca la casella con cardinalità minima (sono escluse le celle flaggate di indizio e quelle già riempite)
    ------ Se la cardinalità è 1 inserisci quell'unico valore nella tabella di gioco e cancella il deque.
    ------ Se la cardinalità è >1 inserisci nella tabella di gioco il valore in cima.
    ------ Se la cardinalità è 0 fai backtrack "poppando" fino a che non trovi un valore >1 nello stack adibito alla cardinalità. Ovviamente eliminando mano a mano le modifiche fatte nella tabella di gioco e ripristinando la cardinalità della colonna, della riga e del quadrato com'era prima.
    Quindi ritornato sulla prima cella con cardinalità >1 poppo il valore che vi avevo inserito prima e provo con quello che ora è in cima e memorizzo la nuova cardinalità.

    -----------Se non torva un valore >1 nello stack adibito a memorizzare la cardinalità originaria ritorna errore e il sudoku non è risolvibile.

    -Se riempe tutta la tabella di gioco cancella tutte le modifiche effetuate e ritorna WIN.

    L'ho testato con Sudoku presi dal giornale, che hanno sicuramente una soluzione e con quelli creati dal computer a random(nel senso che non seguivano alcuno schema come invece avviene nei normali sudoku). Nel primo caso funziona e abbastanza efficacemente, nel secondo ogni tanto ci mette un'eternità(soprattutto con le tabelle di dimensioni 16x16 e 25x25, ma è capitato anche con tabelle 9x9) ma ci arriva o qualche volta va in loop.
    Questo succede quasi sicuramente (anzi ne sono del tutto sicuro), per via del fatto che quando fa il backtrack possa accadere che ripristinando le cardinalità, come sopra, che mi reinserisca i valori che prima avevo eliminato... è giusto che lo faccia ma fino ad un certo punto... quindi che condizione gli posso imporre per evitare che si incanti su quella cella?
  • I
    ixamit
    Molto attivo
    Iscritto da
    ott, 2009
    Messaggi:
    1027

    Re: SUDOKU C++

    Penso ci sia un errore logico nel tuo algoritmo riferito alla cardinalità zero... almeno questo non ha senso a mio avviso. Il pop lo dovresti fare quando il sudoku è errato, cioè quando hai inserito un numero inesatto in base alle 3 regole.

    Quello che avevo proposto io è un semplice backtrace che, se ben fatto, non si fa attendere nel darti il risultato.

    Molte e riviste pubblicano giochi per esser risolti con tecniche più o meno conosciute ma semplicistiche che non necessitano il force-brute.

    In rete trovi diversi documenti riferiti ad algoritmi sicuramente più veloci del mio. knuth è un esempio...

    Saluti,
    Max
  • D
    DashKappei
    Pochi posts
    Iscritto da
    gen, 2011
    Messaggi:
    7

    Re: SUDOKU C++

    Per come ho costruito io la tabella di deque essa non metterà mai un numero che viola le regole. Se il sudoku diventa errato è perchè gli ho fatto inserire un numero che mi impedisce di metterlo in un altra cella che in quel momento aveva cardinalità 1 con solo quel numero possibile... e l'unico modo per correggerlo è tornare indietro fino a una cella con cardinalità >1 e mettere l'altro o gli altri valori possibili. Se provando tutte le combinazioni possibili arrivo sempre a una cella con cardinalità 0 allora il sudoku non ha soluzione... cmq mi rimetto sotto a fare debug, sperando di trovare l'inghippo...
  • I
    ixamit
    Molto attivo
    Iscritto da
    ott, 2009
    Messaggi:
    1027

    Re: SUDOKU C++

    Uhmm...

    Ho fatto delle prove:
    1) ho preso il peggior sudoku risolvibile dal brute-solver -http://en.wikipedia.org/wiki/File:Sudoku_puzzle_hard_for_brute_force.jpg-
    Ho compilato l'algoritmo Dancing Links di Donald Knuth -) trascritto da Xi Chen (Student, Computer Science and Engineering University of New South Wales Kensington -
    Ho eseguito 10K di eseguibile (stripped) su un x86_64 e ho misurato un tempo di 50 secondi circa.
    Ho eseguito il nomale backtrace su un eseguibile (stripped) da 142K in 40 secondi circa. 
    
max@studio:~> cat sudoku_puzzle_hard_for_brute_force
.........
.....3.85
..1.2....
...5.7...
..4...1..
.9.......
5......73
..2.1....
....4...9


max@studio:~> time ./a.out
----------- SOLUTION FOUND -----------
9 8 7|6 5 4|3 2 1|
2 4 6|1 7 3|9 8 5|
3 5 1|9 2 8|7 4 6|
------------------
1 2 8|5 3 7|6 9 4|
6 3 4|8 9 2|1 5 7|
7 9 5|4 6 1|8 3 2|
------------------
5 1 9|2 8 6|4 7 3|
4 7 2|3 1 9|5 6 8|
8 6 3|7 4 5|2 1 9|

real    0m48.100s
user    0m47.728s
sys     0m0.108s
max@studio:~>
    Per contraddizione questo è un sudoku semplicissimo da risolvere in modo logico.

    ~Max
  • D
    DashKappei
    Pochi posts
    Iscritto da
    gen, 2011
    Messaggi:
    7

    Re: SUDOKU C++

    Mi è sfuggito un particolare piuttosto importante riguardo al progetto del Sudoku...
    Devo creare una generatore di schemi che più che andare a caso deve craere un sudoku deterministico nel caso di gioco semplice e non ho assolutamente idea di come fare!!!!
    PS: lo schema semplice può anche non avere soluzione!!
  • I
    ixamit
    Molto attivo
    Iscritto da
    ott, 2009
    Messaggi:
    1027

    Re: SUDOKU C++

    Cioè devi trovare un modo per costruirlo usando la logica?
    PS: lo schema semplice può anche non avere soluzione!!
    Tutti hanno una o più soluzioni.
  • D
    DashKappei
    Pochi posts
    Iscritto da
    gen, 2011
    Messaggi:
    7

    Re: SUDOKU C++

    Cito dal testo:
    Il giocatore, prima di iniziare il gioco, deve anche poter scegliere il "livello di difficoltà" del gioco da giocare: per "gioco semplice" si intende quello che ha una sola oppure nessuna soluzione possibile, e che si può giocare in modo deterministico ad ogni passo senza necessità di fare "tentativi a caso"
  • I
    ixamit
    Molto attivo
    Iscritto da
    ott, 2009
    Messaggi:
    1027

    Re: SUDOKU C++

    Bhe... effettivamente è un particolare che cambia parecchio le cose.

    Si parte al contrario, dal sudoku finito ed in base alle regole si eliminano alcuni numeri dalla tabella sempre tenendo traccia dei candidati. Il numero di celle "Ripulite" è il tuo livello di difficoltà.

    Ora il punto è devi creare un template finito ogni volta che inizi oppure più semplicemente puoi avere dei cover già disponibili ?

    EDIT:
    Suppongo vogliano solo le regole di base... altrimenti guarda che sono veramente tanti metodi (intersections,nakeds, hiddens, wings.......ecc) e sono questi che determinano il livello
Devi accedere o registrarti per scrivere nel forum
22 risposte