jqPuzzle Solver

Dnes vám představuji svou první aplikaci v C#. Spíš jde o takovou blbůstku . Účastnil jsem se totiž jedné soutěže o UAX klíčenku, kterou jsem chtěl vyhrát. Úkolem bylo vyřešit 8-puzzle v co nejkratším čase a na co nejmíň tahů. Jelikož mi tohle nikdy nešlo, tak jsem se rozhodl napsat si solver. Moje současná bilance je docela dobrá orientace v C#, následující aplikace a dvě vyhrané klíčenky .

Popis rozhraní aplikace

Rozhraní programu je navrženo jako průvodce, takže vše probíhá v několika jednoduchých krocích.

1. výběr rozměrů puzzle

Zde je na výběr buď 3x3, neboli 8-puzzle, nebo 4x4, taktéž známo jako 15-puzzle. Možná v další verzi bude na výběr puzzle libovolných rozměrů, kdo ví

2. zadání předlohy

V tomto kroku musíte vybrat obrázek, který má vyřešené puzzle tvořit. Na výběr jsou 3 možnosti, a to z toho důvodu, že ne vždy je jqPuzzle nakonfigurován tak, aby bylo možné výsledný obrázek zobrazit. V tom případě je možné si obrázek stáhnout nebo zadat přímo webovou adresu, podobně jak je ukázáno v ukázkovém videu.

Důležité: jestliže zvolíte výběr regionu obrazovky, je potřeba obrázek obtáhnout, co nejpřesněji, viz video.

3. konfigurace herní desky

Teď uz stačí pouze zadat, jak jsou jednotlivé dlaždice poskládány. Zadání lze provést ručně, vstupem do textového pole, nebo výběrem regionu obrazovky, ve kterém se herní plocha nachází - výběr vůbec nemusí být přesný, lze vybrat klidně celou obrazovku a stejně to bude ve většině případů fungovat.

4. řešení

Po kliknutí na tlačítko "Solve & View results" se zobrazí zadaná konfigurace herní desky a seznam tahů, které jsou potřeba k úspěšnému vyřešení zadaného puzzle.

Jak to funguje?

Program se v podstatě skládá ze dvou částí. První z nich je rozpoznávání hrací plochy a druhou je solver, který hledá optimální řešení pro zadané puzzle.

Rozpoznávání hrací plochy

Algoritmus, který provádí rozpoznávání je velice jednoduchý a jde o nejprimitivnější možný způsob, a to brute-force pattern matching. V podstatě jednotlivé dlaždice posouvám po obrázku a hledám místo s nějvětší korelací mezi dlaždicí a částí obrázku, proti které dlaždici porovnávám. Takhle najdu maxima pro všechny dlaždice a potom podle jejich vzájemných pozic (jednoduché seřazení podle os Y a X) určím pozice dlaždic na herní desce - proto nezáleží na tom, jak přesně uživatel vybere oblast, kde se puzzle nachází.

Hledání optimálního řešení

Tohle je nejsofistikovanější část programu, protože zde mi hrubá síla nepomůže. Pro 8-puzzle ano, ale pro 15-puzzle už nikoli. První verze solveru používala algoritmus A* - ten výborně vyřešil 8-puzzle, ale po nasazení na 15-puzzle začalo jít do tuhého. Problém byl v tom, že A* si pamatuje všechny navštívené stavy, a tak mi program pokaždé vyběhl mimo paměť a spadnul (proč? protože 16! / 2 = 10.46e+12 a já bohužel 10TB RAMku nevlastním ).

Do akce tedy vstoupil algoritmus IDA*, který je v podstatě pouhým hybridem vzešlým z DFS. I tento algoritmus je heuristický, tudíž je potřeba nějaká funkce - například Manhattan nebo Manhattan s lineárními konflikty (pokud je např. dlaždice 2 na pozici 3 a dlaždice 3 na pozici 2, pak nejsou potřeba pouze 2 tahy, ale 4) - obě heuristiky problém vyřeší, ale na mém počítači to trvá asi 30s, takže nic moc. Proto jsem vyzkoušel heuristiku zvanou pattern database. Ta se používá například i pro řešení Rubikovi kostky a dalších podobných problémů. V podstatě to funguje tak, že se vyřeší pouze nějaká podoblast puzzle a v dalším kroku se vyřeší jiná podoblast. V databázi je pak uloženo, kolik tahů bylo na vyřešení potřeba, takže solver pak jen koukne do databáze a použije tento odhad. Tento postup lze ještě vylepšit použitím takzvané additive pattern database (někdy také nazývanou disjoint pattern database). Podrobné vysvětlování toho, jak obě tyto heuristiky fungují je nad rámec tohoto textu a bylo by to minimálně na další celý článek, takže to nebudu dál rozvádět. Zájemci mohou prostudovat odkazy.

V podstatě jde u všech heuristik o to, aby vrátily co nejvyšší hodnotu spodního odhadu při zachování vlastností přípustné heuristiky. Čím vyšší ten odhad je, tím mín iterací hlavní smyčky IDA* je potřeba. Ale nenechte se zmást - IDA* je oproti A* hloupý a jde o hrubou sílu - chytrost spočívá v tom, že hledá pouze cesty určitých délek - tudíž, čím vyšší je odhad, tím rychleji se řešení najde, protože neproběhne neúspěšné prohledání všech cest kratších délek.

Implementace

Aplikace je napsaná v C# jako WinForms aplikace a využívá knihovnu OpenCV, která pro použití v managed jazycích vyžaduje buď tzv. unsafe-code, nebo nějaký wrapper. Já použil wrapper EMGU CV.

Všechny zdrojové kódy, projektu pro Visual Studio, knihovny i starší verze projektu jsou k dispozici v repozitáři na webu projektu. Zároveň je tam k dispozici ke stažení binárka zkompilovaná pro 64b MS Windows.