|
Titlul: Sudoku Scris de: Andrei Misarca din Aprilie 15, 2008, 20:13:12 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
Titlul: Răspuns: Sudoku Scris de: Bogdan-Alexandru Stoica din Aprilie 15, 2008, 20:23:17 problema s-a dat la .campion. o gasesti aici (http://campion.edu.ro/problems.php?mode=view_round&group_number=2&year=2005&round_number=13#).
Titlul: Răspuns: Sudoku Scris de: Andrei Misarca din Aprilie 15, 2008, 20:42:23 Multzam fain =D>
Titlul: Răspuns: Sudoku Scris de: Cezar Mocan din Aprilie 16, 2008, 15:42:09 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).
Titlul: Răspuns: Sudoku Scris de: Cosmin Negruseri din Aprilie 16, 2008, 15:57:10 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. Titlul: Răspuns: Sudoku Scris de: Andrei Misarca din Aprilie 16, 2008, 16:15:43 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? Titlul: Răspuns: Sudoku Scris de: Cosmin Negruseri din Aprilie 16, 2008, 16:20:00 Google is your friend http://www.google.com/search?hl=en&q=dancing+links&btnG=Google+Search
Titlul: Răspuns: Sudoku Scris de: Cristian Strat din Aprilie 16, 2008, 23:30:22 Peter Norvig's "Solving Every Sudoku Puzzle":
http://norvig.com/sudoku.html |