Sudoku

[•Mishu91]

Cum pot rezolva un sudoku? Am incercat un back, dar daca sunt 30 de spatii libere complexitatea e de O(9^30), si dureaza nuj cate ore pana gata asta de calculat

[•fireatmyself]

problema s-a dat la .campion. o gasesti aici.

[•Mishu91]

Multzam fain 

[•CezarMocan]

Eu am scris program care rezolva sudoku cu backtracking si le face in mai putin de 1 secunda chiar si pe alea evil  . Deci merge cu back (ma rog, sunt ceva optimizari care trebuie facute da te descurci).

[•Cosmin]

Implementarea de la campion e super naiva, pe cazuri grele sigur sta o gramada de timp.

O optimizare ar fi sa rezolvi casuta cu cat mai putine posibilitati la fiecare pas ca sa tii branching factor-ul cat mai mic, si alta ar fi sa folosesti Dancing Links in loc sa faci un for cand testezi ce posibilitati ai pentru o casuta.

[•Mishu91]

La implementarea initiala aveam un mic bug(din cauza caruia programu cicla la infinit), pe care l-am corectat dupa ce am vazut implementarea de la .campion si am bagat nijte teste de alea 'evil' de pe websudoku.com si le face aproape instantaneu.

Btw, ce sunt Dancing Links, ca am mai auzit de chestia asta?

[•Cosmin]

Google is your friend http://www.google.com/search?hl=en&q=dancing+links&btnG=Google+Search

[•wickedman]

Peter Norvig's "Solving Every Sudoku Puzzle":

http://norvig.com/sudoku.html