Sudoku solver
Řešič pro sudoku velikosti 9x9 napsaný v Javě jako zkouška nakolik informovanost zlepšuje prohledávání stavového prostoru. A jako zkouška jak dobře se pracuje v Eclipse IDE.
Sudoku :: Úvod
Sudoku je zajímavý fenomén poslední doby. Jedná se o číselný hlavolam ve čtvercové mřížce 9x9. V zadání hlavolamu je vždy vyplněno jen několik čísel, cílem hry je doplnit čísla do ostatních políček mřížky tak, aby na každém řádku, v každém sloupci a ve všech 9 čtvercích 3x3 byla zastoupena všechna čísla 1-9, ale každé číslo v nich bylo zastoupeno nejvýše jednou.
Na obrázku vpravo je vidět jedno z možných zadání Sudoku. Jednotlivé čtverce 3x3, ve kterých se každé číslo musí vyskytovat každé číslo právě jednou.
Sudoku :: Motivace
Hříčka jménem Sudoku si mě získala snadno, tak jak si získává srdce ostatních luštitelů. Ukazuje se ale, že vyřešení průměrného zadání může zabrat i několik desítek minut - to už je dost dlouhá doba, aby se vyplatilo tuto činnost automatizovat...
Idea vytvořit program, který by Sudoku řešil, mě napadla hned při prvním setkání s hlavolamem. Protože ale času není nikdy nazbyt, nevěnoval jsem tomuto nápadu moc velkou pozornost. Inspirace k tvořbě přišla až při opakování prohledávacích algortimů na jednu přednášku. Napadlo mě, že by bylo dobré si zkusit, jak včasné osekání neperspektivních větví ovlivní efektivitu prohledávání na relativně jednoduchém problému. Během jednoho víkendového večera vznikl řešící systém, další večer o týden později jsem věnoval vytvoření jednoduchého uživatelského rozhraní.
Sudoku :: Řešení
Jak se tedy takové Sudoku řeší? Nejjednodušší postup je vyzkoušet všechny možnosti a pokud je zadání řešitelné, tak jednou na řešení určitě narazíme. Možných kombinací čísel je ale velké množství (více než 10^14). Jejich počtem sice nejde ohromovat posluchače tak, jak to dělají kryptografové u moderních šifer, ale i tak je jich víc, než dost.
Velmi důležité je tedy co možná nejdříve rozpoznat možné kolize a navést prohledávání jiným směrem. Nejhloupější možnou verzi backtrackingu jsem tedy ani nezkoušel (nechci znát výsledky), kolize od začátku hledám po každém umístěném čísle.
Pro programování řešiče jsem zvolil Javu, hlavně kvůli rychlému psaní kódu při zachování rozumného výkonu. Obvykle píšu kód pro nejnovější verze Javy, ani Sudoku nebyl důvod dělat výjimku - použita je proto Java 1.5.
Vzhledem k objektové povaze polí v Jave bylo nutné obstarat zásobník pozic pro backtracking obstarat ručně. Přitom jsem použil naivní postup a při každém kroku backtrackingu je alokováno nové pole na zásobníku a při vracení zpět je staré zahozeno (vzhledem k hloubce backtrackingu, která je pevně daná povahou hlavolamu by bylo možné tato pole předalokovat a při výpočtu recyklovat a tím výpočet zrychlit o alokaci pole v každém kroku).
První pokus byl pouze s prohledáváním (do hloubky). Většina zadání byla vyřešena v časech do 1s (na Intel Centrino 1.7Ghz, 768MB RAM), nejtěžší zadání program řešil 2.2s.
Takový výsledek lze se zcela klidným svědomím označit za neuspokojivý, proto jsem se v tomto bodě nezastavil a pokusil se o zlepšení. Do kódu jsem doplnil propagaci možných hodnot po herní ploše - každé políčko na herní ploše má přiřazený seznam (v mojí implementaci bitovou mapu) možných hodnot, ze kterých jsou vybírány hodnoty použité při backtrackingu. Po umístění čísla je toto číslo odebráno ze seznamu možných hodnot ve všech políčkách ve stejném řádku, sloupci a skupině a je tak možné předejít velkému množství konfliktních situací. Pokud na nějakém políčku zbyde jediná možná hodnota, je na něj dosazená a provede se pro ni proškrtání možných hodnot v okolních polích stejným způsobem.
Při prvním testování jsem zapomněl, že propagaci možných hodnot je potřeba provést také přes čísla přítomná v zadání. Vznikl tak zajímavý výsledek, že vyluštění nejtěžšího zadání se zkrátilo na 0.4s, tedy 4-5krát.
To se mi ale pořád přišlo jako příliš dlouhá doba, proto jsem program ještě jednou prošel a doplnil proškrtávání možných hodnot i pro čísla daná v zadání. Tím se rychlost výpočtu na všech zadáních dostala do kategorie <= 10ms, kde už nejsem schponý rozumně měřit čas (a ani se mi do toho nechce).
Myslím si, že další optimalizací by se dal výpočet ještě zrychlit, jednalo by se ale o technické triky, které se samotným prohledávacím algoritmem tolik nesouvisí a jejich vyzkoušení rád nechám někomu jinému.
Sudoku :: Závěr
Na závěr bych si dovolil poznamenat, že Sudoku mám rád i po dokončení tohoto programu a že během tvorby prostředí Eclipse nezklamalo a pro nejbližší dobu získalo u mě status Java IDE číslo 1.
Aktualizace 26. 1. 2007 - Blog :: Ještě jednou Sudoku