Sudoku FlowKako računala rješavaju Sudoku
Ažurirano 2026-10-05
Pretraživanje s vraćanjem
Rješavač isprobava dopuštenu znamenku u praznoj ćeliji i nastavlja dalje. Ako nijedna znamenka ne vodi do rješenja, poništava neki raniji izbor i pokušava s drugim. Ako se najprije odabere ćelija s najmanje mogućih znamenki, pretraživanje je često znatno kraće.
Izvori: Wikipedia: Sudoku solving algorithms, Peter Norvig: Solving Every Sudoku Puzzle
Točno pokrivanje i Dancing Links
Sudoku se može preformulirati kao problem točnog pokrivanja (exact cover): treba odabrati položaje znamenki tako da svaka ćelija, kao i svaka znamenka u svakom retku, stupcu i kvadratu, bude pokrivena točno jednom. U radu iz studenoga 2000. Donald Knuth opisao je Dancing Links, učinkovit način izvođenja svojeg algoritma X koji se temelji na pretraživanju s vraćanjem; primijenjen na model Sudokua kao problema točnog pokrivanja, brzo pronalazi sva rješenja zagonetke.
Izvori: Wikipedia: Sudoku solving algorithms, Knuth, Dancing links (arXiv cs/0011047, 2000)
Nasumično pretraživanje
Neki programi nasumično popune mrežu, a zatim premeću brojeve kako bi smanjili broj sukoba, metodama kao što su simulirano kaljenje ili genetski algoritmi. Proučavani su kao alternativni pristupi; koliko su uspješni ovisi o programu i zagonetki.
Izvori: Wikipedia: Sudoku solving algorithms
Rješavači koji razmišljaju kao ljudi
Mehanizam za savjete ima drukčiji zadatak: ne samo pronaći odgovor nego pokazati sljedeći korak koji čovjek može pratiti. Mehanizam u našoj aplikaciji isprobava ljudske tehnike utvrđenim redoslijedom, od najlakših, poput skrivenog jedinca, do najtežih, poput lanaca i gotovo zaključanih skupova (almost locked sets), i koristi prvu koja dovodi do upisivanja znamenke; teže tehnike djeluju tako da najprije isključe kandidate. Najteža tehnika koju koristi na nekoj zagonetki određuje razinu te zagonetke u aplikaciji.
Izvori: Što od vas traži svaka razina težine u sudokuu
