Vlákno názorů ke článku Sudoku - řešení silou od xyz - Ahoj, myslim, ze ten algoritmus neni DFS, ale backtracking....

Ahoj,
myslim, ze ten algoritmus neni DFS, ale backtracking. DFS algoritmus prochazi graf nebo strom do hloubky a jeho slozitost je O(n), kde n je pocet vrcholu. Kdezto reseni sudoku ma exponencialni slozitost mam pocit.

DFS je v tomhle případě metoda, jak se prokousávat stromem rekurzivních volání.

"jeho slozitost je O(n), kde n je pocet vrcholu."

co je n?

"Kdezto reseni sudoku ma exponencialni slozitost mam pocit."

vrcholu stavoveho grafu je exponencialne mnoho v zavislosti na poctu policek sudoku