Ondra[sej] Blog

V minulém příspěvku o Sudoku solveru. -mt- v diskuzi pod příspěvkem namítal, že solver je podobně rychlý jako jeho naivní solver v C++. Že by chytré řešení v Javě bylo stejně rychlé jako naivní řešení v C++ zní trochu divně — ledaže by to s tou chytrostí nebylo tak horké…

Nebylo. Při kontrole korektnosti pozice se testovalo, zda v některé skupině (tj. řádku, sloupci nebo podčtverci) nejsou dvě stejné hodnoty a že pro každé pole zbývá alespoń jedna možná hodnota. Přidáním dalšího testu, který kontroluje, jestli do každé skupiny stále lze vložit (nebo už je vloženo) všech devět číslic. Na úloze z předchozího příspěvku klesl počet návratů při backtrackingu díky rychlejší detekci nekorektní pozice z 174844 na 35039.

Bez dalších technických optimalizací se čas nutný přo nalezení řešení výše zmíněné úlohy (na stejném stroji) snižil z průměrných 2940,3 ms na 392.16 (± 16) ms. Nová verze solveru včetně zdrojových kódů je ke stažení na stránce projektu. Několik nápadů na zrychlení ještě zbývá, ale to zas někdy příště…

Když jsem před časem programoval Sudoku solver v Javě, použil jsem jednoduchý, dalo by se říci až naivní, přístup k vytvoření zásobníku pro backtracking. Při řešení jednoduchých sudoku naivní implementace nevadí, protože k backtrackování dochází jen minimálně. Jak to je s (ne)efektivností tohoto řešení doopravdy se ukázalo až na opravdu těžkých zadáních z Minimum Sudoku.
(more…)