MASARYKOVA UNIVERZITA, FAKULTA INFORMATIKY
GENERÁTOR ZADÁNÍ RÉBUSŮ SUDOKU A NURIKABE BAKALÁŘSKÁ PRÁCE
Petr Svirák 2011
Prohlašuji, že tato práce je mým původním autorským dílem, které jsem vypracoval samostatně. Všechny zdroje, prameny a literaturu, které jsem při vypracování používal nebo z nich čerpal, v práci řádně cituji s uvedením úplného odkazu na příslušný zdroj. V Brně, dne 4. 1. 2010
Rád bych poděkoval panu RNDr. Jaroslavu Pelikánovi, Ph.D. za odborné vedení bakalářské práce a poskytnutí cenný rad.
SHRNUTÍ Cílem této práce je popsat běžně používané heuristiky pro řešení rébusů Sudoku a Nurikabe a analyzovat teoretické i praktické možnosti generování uvedených rébusů. Součástí práce je také aplikace schopná rébusy jak řešit, tak generovat a nabízet je k řešení uživateli. První část práce se zabývá analýzou dostupných metod řešení, generováním obou rébusů a možnostmi jejich algoritmizace. Druhá část práce se věnuje implementaci některých metod a aplikaci samotné.
KLÍČOVÁ SLOVA Sudoku, Nurikabe, lidské heuristiky, řešící algoritmy, generující algoritmy, X-Wing, Swordfish, X-Y wing, Knuthův algoritmus X, rotace čtvercové sítě.
OBSAH 1 Úvod ...................................................................................................................................................................... 1 1.1 1.2
Nurikabe ................................................................................................................................................. 1 Sudoku..................................................................................................................................................... 2
2 Analýza lidských postupů a možností jejich algoritmizace ........................................................... 5 2.1
Nurikabe ................................................................................................................................................. 5 2.1.1 2.1.2
2.2
Vytvoření a úprava maximální cesty ........................................................................... 6 Řešení existující mřížky.................................................................................................... 9
Sudoku.................................................................................................................................................. 10 2.2.1 2.2.2 2.2.3
Generování z existujícího sudoku.............................................................................. 10 Generování z prázdné mřížky ..................................................................................... 11 Metody řešení .................................................................................................................... 12
3 Generátor Sudoku a Nurikabe ................................................................................................................ 17 3.1 3.2 3.3
Aplikace dostupné pro běžné uživatele .................................................................................. 17 Analýza požadavků a struktury aplikace ............................................................................... 17 Popis algoritmů generujících a řešících rébusy .................................................................. 19 3.3.1 3.3.2 3.3.3
3.4
Nurikabe .............................................................................................................................. 20 Sudoku .................................................................................................................................. 28 Interface a propojení vláken s uživatelským rozhraním ................................. 30
Uživatelské rozhraní....................................................................................................................... 32 3.4.1 3.4.2 3.4.3
Import, export.................................................................................................................... 33 Vkládání rébusů, ruční generování a úprava, řešitel ......................................... 34 Statistiky .............................................................................................................................. 35
4 Závěr .................................................................................................................................................................. 37 5 Literatura......................................................................................................................................................... 39
1
ÚVOD
Práce se zabývá dvěma rébusy. Rébus Sudoku je dnes velmi známý a koncem 20. století si získal velkou popularitu ve světovém měřítku. Druhým rébusem je Nurikabe, které je mladší a není tak známé, avšak z pohledu hráče je také zajímavé. Protože je Sudoku známější a bylo o něm napsáno nespočet matematicko-analytických i informatických prací, je práce zaměřena hlavně na rébus Nurikabe. U obou rébusů je hrací plochou čtvercová síť. Zatímco síť Sudoku je většinou čtvercových rozměrů o velikosti 9x9; u Nurikabe je teoreticky možné použít čtvercovou síť zcela libovolného tvaru. Pro každou síť však musí existovat způsob jak do ní vepsat čísla tak, aby byl výsledkem korektní rébus. Nejčastěji se Nurikabe vyskytuje v podobě sítě o čtvercových rozměrech od 5x5 do 20x20.
1.1
NURIKABE
Zadáním hry je prázdná čtvercová síť, do které jsou na některých místech vepsána čísla (Obrázek 1.1). Cílem hry Nurikabe je postavit v dané čtvercové síti jedinou souvislou cestu bez pokojů. Pokoj je tvořen buď čtyřmi buňkami cesty uspořádanými do tvaru čtverce 2x2 nebo větším množstvím buněk cest, které obsahují alespoň jeden takový čtverec. Za buňku Obrázek 1.1 zdi je považována každá buňka, která není cestou. Zdi jsou ve čtvercové síti tvořeny ze stranově sousedících buněk zdí. Každá zeď musí mít uvObrázek 1.2 nitř vepsané právě jedno číslo označující její plochu (za plochu je považován počet buněk, z nichž se zeď skládá) – jak ukazuje Obrázek 1.2. (1) Samotný rébus má několik jednoduchých pravidel, podle kterých hráč bludiště staví:
Zdi se smí dotýkat nejvýše rohy, nikoli hranami. Každá buňka, která není buňkou zdi je součást cesty bludištěm. Cesty nesmí tvořit pokoje. Každá hra musí mít právě jedno řešení.
Hrací plocha je na počátku celá vyzděná. Hráč v ní vyznačuje cesty a může si hvězdičkou označit zdi, o kterých si je jistý, že jsou součástí řešení. Neztratí tak přehled, kterými buňkami se již zabýval a kterými ještě ne. Zdi jsou většinou bílé (viz níže - zjevení ducha Nurikabe), cestám pak náleží černá barva. Ve většině případů se setkáme s čtvercovou síti velikosti 5x5, 7x7 nebo 10x10, avšak existují i obdélníkové varianty nebo varianty 12x12, 15x15 či 20x20.
1
Název hry Nurikabe má původ v japonských pověstech. Nurikabe (ぬりかべ) (2) (3) je yōkai, stvoření podobné duchovi ve smyslu tvora s kořenem v lidství a nadpřirozenými schopnostmi. Nurikabe se zjevoval jako neprostupná bílá zeď, která mátla a obtěžovala po nocích poutníky. Snaha zeď obejít byla marná, vždy se kousek prodlužila a byla schopná se prodlužovat do nekonečna. Otočil-li se poutník, viděl Nurikabe stále před sebou. Zeď měla ruce a nohy a neváhala je použít, nebylo ji tedy možné ani přelézt. Pokud však poutník poklepal holí na její spodní část, zeď zmizela a nechala jej projít. Poprvé byla hra popsána v 33. vydání japonského časopisu Nikoli (zabývajícího se rébusy) v březnu roku 1991. (1) Hra si téměř okamžitě získala popularitu a od 38. vydání je součástí každého čísla časopisu Nikoli.
1.2
SUDOKU
V rébusu Sudoku (Obrázek 1.3) musí hráč do čtvercové sítě, většinou o velikosti 9x9, umístit chybějící čísla, v tomto případě, od 1 do 9. Čísla musí být umístěna tak, aby se v každém řádku, sloupci a menším čtverci, zde o rozměrech 3x3, vyskytovalo každé číslo právě jednou. K vyřešení nejtěžších rébusů Sudoku je třeba použít i některých složitých logických úvah a postupů. Existují i rébusy Sudoku k jejichž vyřešení je třeba natolik komplexní logiky, že jí běžný lidský mozek není schopen. (4) Kořeny Sudoku (5) (6) sahají až do obObrázek 1.3 dobí přibližně před třemi tisíci lety. Z té doby existují první čínské záznamy (7) o tzv. magickém čtverci , který je do jisté míry prapředkem dnešního Sudoku. Jedná se o čtvercovou mřížku složenou z alespoň 9 buněk (Obrázek 1.4). Každé číslo se může ve čtverci vyskytnout nejvýše jednou a součet hlavní diagonály, vedlejší diagonály i všech vertikál a horizontál musí být vždy stejný. Číňané přikládali každému řešení mřížky zvláštní magickou moc a používali je při náboženských rituálech. Do Evropy byl magický čtverec přivezen kočovnými Araby přibližně v devátém století našeho letopočtu. Prvním prokazatelným magickým čtvercem v Evropě je dřevěná rytina Obrázek 1.4 Alberta Dürera nazvaná Melancholie z roku 1514, ale už každý renesanční filozof byl s magickými čtverci a technikou jejich tvorby obeznámen.
2
Ve druhé polovině 17. století se magickým čtvercem začal zabývat i švýcarský matematik a fyzik Leonhard Euler. (8) Tento matematik, který se věnoval hlavně matematické analýze a je považován za zakladatele teorie grafů, měl nejspíše magický čtverec pouze jako hobby. Euler se zamýšlel nad tím, co se stane, odebere-li z pravidel pro tvorbu magického čtverce pravidlo o součtu na hlavní a vedlejší diaObrázek 1.5 gonále. Výsledkem byl permutační rébus (Obrázek 1.5), který nazýval řecko-římské nebo také latinské čtverce (9). Na rozdíl od dnešního Sudoku, označoval Euler hodnoty v buňkách písmeny, nikoli čísly, avšak pravidlo výskytu každé hodnoty právě jednou v každém řádku a sloupci zůstává dodnes stejné. Poprvé představil Euler své latinské čtverce v roce 1783 jako „nový druh magických čtverců“. Ačkoli z Eulerova díla čerpalo mnoho matematiků, jeho latinské čtverce zůstávaly bez povšimnutí. Mezi roky 1890 a 1920 byly sice ve francouzských novinách La France uveřejněny rébusy (5), které vznikly nahrazením písmen čísly a následným odebráním některých čísel právě z Eulerova latinského čtverce, avšak jednalo se hlavně o aritmetický rébus a pozice čísel v něm nehrály žádnou roli. Po dalších zhruba šedesáti letech, v roce 1979, uveřejnil Howard Garns (5) v americkém časopise Dell Puzzle Magizine rébus složený z 9 latinských čtverců o rozměrech 3x3 buňky. Umožnil permutace uvnitř těchto menších čtverců a přidal je k permutacím řádků a sloupců v rámci herní sítě o rozměrech 9x9. Zachováním pravidla o stejném součtu každého řádku, sloupce a nově menšího čtverce tak vytvořil hru, později známou jako Sudoku. Howard Garnes původně svůj rébus pojmenoval „Number place“ (5) (volně přeloženo „místo pro číslo“). Z Ameriky se rébus dostal do Japonska. Ačkoli je častým omylem považovat Sudoku za japonskou hru, zasloužili se právě Japonci o celosvětové rozšíření tohoto rébusu. Původní název „Number place“ byl přeložen jako „číslo se musí objevit jen jednou“ (Sūji wa dokushin ni kagiru - 数字は独身に限る), který byl zkrácen na Su Doku - 数独 (Su znemená číslo a Doku jednotlivý – tedy jediné číslo). (5) Práce popisuje lidmi používané metody řešení a tvorby obou rébusů a možnosti jejich algoritmizace. Shrnuje dostupné informace o jednotlivých heuristikách a metodách tvorby a řešení obou rébusů. Součástí práce je aplikace, která umožní uživateli vygenerovat nové zadání rébusu, rébus vyřešit a řešení zkontrolovat.
3
2
ANALÝZA
LIDSKÝCH POSTUPŮ A MOŽNOSTÍ JEJICH
ALGORITMIZACE Oba rébusy mají několik společných vlastností, například zadání, které musí mít právě jedno řešení, nebo herní plochu – čtvercovou síť. Je proto vhodné využít k reprezentaci rébusů maticové uspořádání (například dvourozměrné pole). Zároveň ale algoritmy přistupují často k jednotlivým buňkám sítě, někdy i ke všem, lineárně; proto je naopak vhodné lineární uspořádání (například seznam). Nejvhodnější kombinací těchto dvou přístupů je objekt obsahující několik jednorozměrných polí. Některá pole v sobě nesou herní informace (číslo v buňce, typ buňky, …) a jiná obsahují čísla řádků, sloupců a případně index v rámci menšího čtverce Sudoku – tyto hodnoty mohou být spočteny pouze jednou při inicializaci hry. Tím je snížena dobu výpočtu ať už generujících nebo řešících metod. Ačkoli se rozměry jednotlivých her a zadání mohou vzájemně lišit, pro jednu konkrétní hru zůstávají vždy neměnné. Proto je vhodné použít dynamická pole namísto jiných struktur, například seznamů. U obou rébusů může docházet k větvení jak při řešení, tak při generování; je tedy vhodné použít vlákna. Počet vláken může růst velmi rychle a musí být stanoven maximální počet souběžně spuštěných vláken v závislosti na hardwarovém vybavení počítače. Jednotlivá vlákna často řeší diametrálně odlišné možnosti, proto nese každé nově vzniklé vlákno kopii celé instance rébusu, kterou má dále řešit nebo generovat. Protože se herní zadání ve většině případů pohybuje v rozměrech 16 – 400 buněk a vláken může vzniknout mnoho, je vhodné použít datové typy co nejmenší velikosti. Uživatelské rozhraní nemůže komunikovat přímo s jednotlivými vlákny, proto je nutné použití správce vláken, který vlákna spouští, ukončuje a pozastavuje. Správce vláken plní funkci rozhraní, které, z pohledu uživatelského rozhraní, sjednotí oba rébusy, tak aby nebylo nutné psát zvlášť například metodu pro zobrazení průběhu řešení Sudoku a zvlášť pro zobrazení průběhu řešení Nurikabe.
2.1
NURIKABE
Pro Nurikabe vzniká datový typ popisující obsah buněk (zda buňka obsahuje zeď, cestu anebo uživatelskou značku zdi - dále hvězdičku). Protože z povahy hry vyplývá, že je nutné používat prohledávání do hloubky (například hledání pokračování pro cestu uvnitř skupiny zdí nebo naopak pro nekompletní zeď uvnitř skupiny cest) i do šířky (například pro zjištění nedosažitelných buněk), je vhodné připravit datové struktury, pro tato hledání. Pro generování zadání rébusu slouží metody popsané v následující podkapitole.
5
2.1.1 VYTVOŘENÍ A ÚPRAVA MAXIMÁLNÍ CESTY
Obrázek 2.1
Protože stěžejním typem buněk jsou cesty, je vhodné nejprve sestavit maximální cestu. Druhým krokem je ohodnocení a zvětšení zdí kolem cesty tak, aby nebylo Nurikabe triviální a zároveň mělo právě jedno řešení. Mějme prázdnou čtvercovou síť. Algoritmus náhodně vybere buňku a označí ji za cestu. Z této buňky si vybere směr tak, aby nevznikl pokoj, a celý postup opakuje, dokud nenavštíví všechny buňky sítě a neoznačí je buď za cesty, nebo za zdi (za zeď označí každou buňku, která nemůže být cestou - Obrázek 2.1). Tento algoritmus lze aplikovat i z více míst, například rohů sítě, najednou. Bylo by však nutné ošetřit případné kolize vláken, a protože se algoritmus pouze vyhýbá pokojům na cestách, jeho efektivita by se přidáním vláken výrazně nezvýšila. (10)
Obrázek 2.2
Aby byl omezen počet symetrických konfigurací zdí, prozkoumá další metoda čtverce o velikosti 2x2 buňky v rozích čtvercové sítě a bude v nich hledat zdi o ploše 3. Obsahuje-li takový čtverec zeď o zmiňované ploše a odebráním jediné buňky cesty ze čtverce se nenaruší souvislost cesty, jsou kolem čtverce buňky cest umístěny tak, že pro každé umístění čísla uvnitř zdi o ploše 3 existují alespoň dvě možnosti její konfigurace (Obrázek 2.2). Jev je zapříčiněn metodou tvorby maximální cesty, která do mřížky zapisuje co nejvíce buněk cest. Z vyhovujících čtverců v rozích je odebrána zbývající buňka cesty a problém čtvercové rohové symetrie je tak odstraněn (Obrázek 2.3).
6
Obrázek 2.3
Po úspěšném vygenerování maximální cesty je nutné umístit číslo označující plochu zdi dovnitř každé zdi tak, aby po odebrání cest vzniklo zadání s jediným řešením (Obrázek 2.4). Algoritmus zkouší všechny kombinatorické možnosti umístění čísel do zdí pro danou maximální cestu. Máme-li tedy zdi Z1, Z2, … Zn, s plochami S1, S2, … Sn, je v nejhorším případě nutné vyzkoušet S1×S2×…×Sn možností. Tato hodnota roste jak s počtem zdí, tak s velikostí jejich ploch. Je proto vhodné zaměřit se hlavně na určité části zdí. Jednoznačnost tvaru zdi je sice úzce spjata s ostatními zdmi, respektive s jejich čísly, a okraji herní čtvercové sítě; avšak bez výrazné újmy na obecnosti lze tento problém zjednodušit Obrázek 2.4 na problém umístění čísla v rámci jeho zdi. Pokud algoritmus postupuje při umisťování čísel od okrajů zdi do jejího středu, nalezne dříve unikátní kombinaci umístění hodnoty Sx, protože při okrajích je u většiny tvarů zdí vyšší pravděpodobnost, že po odebrání cest bude možné zeď vytvořit pouze jediným způsobem. Pokud se takto podaří vytvořit maximální cestu a do vzniklého rébusu vepsat hodnoty zdí, může algoritmus začít zdi slučovat. Vybere všechny buňky cest, které sousedí s alespoň dvěma zdmi (Obrázek 2.5) a jejich odebráním nedojde k porušení herních pravidel (nevytvoří se dvě nespojené cesty, jak ukazuje Obrázek 2.6). Vyhovující buňky cest (Obrázek 2.7) ohodnotí součty ploch zdí a počtem slučovaných zdí (dvě nebo tři). Existuje-li více buněk cest se stejným ohodnocením, algoritmus náhodně vybere jednu z nich. Pokud by se
Obrázek 2.5
Obrázek 2.6
7
pokusil slučovat přes všechny výše popsané buňky, došlo by k výraznému zpomalení generování (čím větší plochy zdí jsou slučovány, tím více možných umístění hodnoty jejich plochy je nutno testovat a je také menší pravděpodobnost, že bude tvar zdi unikátní). V konečném důsledku by takto bylo vytvořeno triviální Nurikabe s jedinou velkou zdí. Aby hra zůstala zajímavou pro hráče, je nutné sloučit co nejvyšší počet zdí a zároveň netvořit zdi o příliš velké ploše. Jednou z charakteristik výše vygenerované maximální cesty je Obrázek 2.7 i velký počet zdí o ploše 1. Proto je vhodné slučovat zdi přes takové buňky cest, které mají nižší součet ploch přilehlých zdí a slučují jich více (Obrázek 2.8). Po každém sloučení zdí se algoritmus musí pokusit vepsat do nové zdi velikost její plochy. Modifikovaný algoritmus hledání unikátního umístění čísel v bludišti s maximální cestou, který umisťuje čísla pouze do prázdných zdí, je vhodný a účinný nástroj pro dotvoření Nurikabe se sloučenými zdmi (Obrázek 2.9).
Obrázek 2.8
Obrázek 2.9
Pro další ztížení hry může generující algoritmus nalézt takové buňky cesty, které sousedí pouze s jednou zdí nebo jsou součástí kružnice, jejímž porušením nedojde k rozpojení souvislé cesty (Obrázek 2.10). Takové buňky lze sloučit s přilehlými zdmi, pokud je použitím modifikovaného algoritmu pro umístění čísla uvnitř zdi ověřeno, že zůstalo zachováno pravidlo jediného řešení. Algoritmus natahování zdí lze, na rozdíl od algoritmu slučování zdí, aplikovat postupně na všechny přípustné kandidáty – nemůže při něm dojít ke zlehčení výsledné hry (Obrázek 2.11), naopak každou úspěšnou iterací dojde ke ztížení. Obrázek 2.10
8
Obrázek 2.11
2.1.2 ŘEŠENÍ EXISTUJÍCÍ MŘÍŽKY Podobně jako u rébusu Sudoku je teoreticky možné použít algoritmu využívajícího hrubou sílu (viz kapitola 2.2.3). Rychlost takového algoritmu by závisela nejen na velikosti čtvercové sítě, ale i na každé konkrétní hře. Modifikací tohoto algoritmu je metoda, která v případě nepoužitelnosti ostatních heuristik vybere náhodně jednu z možných pokračování cesty (zde dochází k větvení). U většiny zadání Nurikabe však není využití této metody nutné. Z lidmi používaných heuristik (10) (11) je většinou první Heuristika „sousedních“ čísel. Jsou-li ob jednu buňku vedle sebe (resp. dotýkají-li se rohy) dvě nebo více čísel, jistě mezi nimi bude buňka cesty (Obrázek 2.12 – tmavě šedě). Stejně tak, obsahuje-li Nurikabe číslo 1, budou těsně kolem něj čtyři cesty (dvě na vertikále a dvě na horizontále), protože se zdí může jiná zeď sousedit pouze rohem (Obrázek 2.12 – černě). Obecněji, existuje-li pouze jeden možný tvar zdi, musí jej po všech hranách (nikoli rozích) obklopit buňky cest (ObráObrázek 2.12 zek 2.12 – světle šedě). Existuje-li buňka cesty A, která ještě není na zbývající A buňky cest napojena a existuje-li pro takovou buňku pouze B jediná možná buňka B, kterou se může ke zbylým buňkám cest připojit, musí být nutně buňka B také cestou (Obrázek 2.13 – tmavě šedě). Analogicky lze pravidlo aplikovat u zdí: Máme-li nekompletní zeď Z obsahující své číslo (tj. Y například i jedinou buňku zdi obsahující právě své číslo, Z B A které je vyšší než 1) a existuje-li pro ni pouze jediná buňka Y, kterou je možno zeď dokončit nebo alespoň rozšířit, bude Obrázek 2.13 buňka Y jistě také zdí (Obrázek 2.13 – světle šedě). Objeví-li se v síti tři buňky cesty vedle sebe ve tvaru písmene L, čtvrtá buňka, která by s nimi vytvořila čtvercový pokoj, bude jistě zdí (Obrázek 2.14 – světle šedě). Takto může vzniknout buňka zdi, která je v dosahu jednoho či více čísel. Pokud je v dosahu právě jednoho čísla a pokud je možné postavit k tomuto číslu zeď právě jedním způsobem, jistě zde taková zeď bude. Existuje-li více takových způsobů, ale všechny prochází určitou skupinou buněk, budou buňky této skupiny jistě buňkami zdi. Obrázek 2.14
9
V situaci kdy jsou ve čtverci tvořeném 2x2 buňkami A čtvercové sítě dvě buňky jistě cestami a jedna ze zbývajících B dvou neznámých buněk musí být zdí, lze použít následující heuristiku: Pokud by jedna z neznámých buněk - A musela C být ke zdi (resp. buňce obsahující číslo) - Z napojena přes druhou neznámou buňku - B, bude jistě B součástí zdi Z. Obdobně lze tuto heuristiku použít pro určení polohy buňky cesty (Obrázek 2.15 – světle šedě). Pokud jsou ve čtverci dvě buňky jistě zdmi (hvězdička nebo číslo) a jedna ze zbývajíObrázek 2.15 cích buněk musí být cestou, je nutno zkoumat, zda je jednu ze zbývajících buněk (A) možno na cestu C napojit pouze přes druhou zatím neurčenou, buňku (B). Pokud ano, bude buňka B jistě cestou (Obrázek 2.15 – světle šedě s vykřičníkem). V případech, kdy nelze aplikovat žádnou výše uvedenou A heuristiku, lze hledat nedosažitelné buňky (Obrázek 2.16 – tmavě šedě). Buňka je nedosažitelná právě tehdy, když k ní C B nelze z žádného čísla postavit cestu, která by splňovala pravidla Nurikabe. Je-li konfigurace některé zdi známá až na polohu právě jedné buňky a tato buňka může být pouze na pozici A nebo B, použijeme následující heuristiku: Existuje-li mezi A a B právě jedna buňka C, která se A i B dotýká hranou, bude buňka C jistě cestou (Obrázek 2.16 – světle šedě). Obrázek 2.16 Kdykoli algoritmus zjistí, že se v jím řešené hře nachází rozpor s pravidly (pokoj tvořený cestami, buňka zdi, která nelze připojit k žádnému číslu nebo například dvě cesty, jež není možno propojit), danou větev řešení zamítá. Pokud je zamítaná větev kořenem, hra nemá řešení.
2.2
SUDOKU
Základem hry je čtvercová síť o ploše libovolné čtvrté mocniny přirozeného čísla (dále základní číslo). Uvnitř je síť rozdělena do menších čtverců o obsahu druhé mocniny základního čísla. Nejčastěji se Sudoku vyskytuje v rozměrech 9x9 (základní číslo 3). Pro každý řádek, sloupec a menší čtverec platí, že obsahuje každé číslo od jedničky do druhé mocniny základního čísla právě jednou – je tedy třeba vytvořit strukturu, která ponese informace o hodnotách, které je možné do prázdné buňky vložit v závislosti na hodnotách již vložených do ostatních buněk stejného řádku, sloupce a menšího čtverce.
2.2.1 GENEROVÁNÍ Z EXISTUJÍCÍHO SUDOKU Každé standardní Sudoku (u různých variant se možné operace liší) lze obměnit kombinací jedné či více následujících metod (12). Metoda přečíslování vymění všechna čísla za čísla jiná (v rámci množiny hodnot). Například všechny výskyty čísla 1 nahradíme čís-
10
lem 3, všechny původní výskyty čísla 3 nahradíme číslem 7, a tak dále. Pro Sudoku 9x9 existuje 9!, tedy 362 880 takových mutací. Pro popis dalších metod je nutné definovat pojmy patro a věž. Patrem pro Sudoku 9x9 je každá vodorovná trojice menších čtverců a věží každá svislá trojice menších čtverců. Metodou rotace řádků, resp. sloupců, lze v rámci libovolného patra nebo věže vybrat dva řádky nebo sloupce celého Sudoku a vzájemně je vyměnit. Počet sloupců v Sudoku 9x9 je devět, tedy tři věže, každá po třech sloupcích. Metoda vybírá z každé věže dvojici sloupců. Existuje tedy (2×3)3 možností pro sloupce a stejný počet pro řádky. Dohromady 66, tedy 46 656 mutací. Metoda rotace pater a věží umožňuje vyměnit tři sousedící řádky, resp. sloupce (patro nebo věž) za jiné. V Sudoku 9x9 jsou tři patra, z nich metoda vybírá dvě, která rotuje. Pro patra existuje 6 možností rotace a analogicky existuje 6 možností rotace i pro věže. Celkem tedy existuje 36 mutací. Poslední metodou je výměna řádků za sloupce – z řádků uděláme sloupce a ze sloupců řádky. Tím lze získat, s ohledem na disjunkci metod, další 2 mutace. Výsledkem je, že každou existující standardní variantu Sudoku je možno mutovat 362 880×46 656×36×2, tedy 1 218 998 108 160 způsoby. Z algoritmického pohledu je obtížnost všech těchto her stejná, protože jejich řešení se liší pouze v pořadí použitých pravidel. Jednotlivci se však mohou některé varianty zdát lehčí či těžší než jiné. (13)
2.2.2 GENEROVÁNÍ Z PRÁZDNÉ MŘÍŽKY Mějme prázdnou čtvercovou síť o ploše čtvrté mocniny libovolného daného základního čísla Z. Pro každou buňku této sítě mějme seznam hodnot, které lze do buňky vložit (na počátku lze do každé buňky vložit libovolné číslo od jedničky do druhé mocniny Z). Počínaje buňkou vlevo nahoře, je do každé buňky náhodně vloženo číslo (dále kandidát) z jejího seznamu možných čísel. Následně je ze seznamů možných čísel aktuální buňky a buněk ve stejném řádku, sloupci a menším čtverci kandidát odebrán. Pokud je buňka prázdná a nemá ve svém seznamu již žádnou hodnotu, vrací se algoritmus k předešlým buňkám tak dlouho, dokud nenalezne buňku s alespoň jednou hodnotou v seznamu možných buněk. Z této buňky odstraní stávající hodnotu, vybere nového kandidáta ze seznamu možných hodnot a opět pokračuje k následující buňce. (14) Z takto utvořené mřížky odebírá algoritmus čísla z buněk dle zvoleného klíče. Po odebrání vždy testuje, zda má nová mřížka právě jedno řešení. Pokud ne, číslo do buňky vrátí a pokusí se odebrat jiné. Existuje mnoho různých druhů klíčů, dle kterých je možno odebírat čísla z buněk Sudoku. Nejpoužívanějšími jsou symetrie, ačkoli vhodně zvolené asymetrické Sudoku může být větší výzvou, na člověka působí neesteticky. Často se také objevuje použití heuristik pozpátku – nejprve jsou vybrány heuristiky, které se mají použít. Poté jsou náhodně nebo symetricky vybrány buňky, na které má hráč aplikovat heuristiku, a průběh hry je de facto konstruován od konce k začátku. Touto technikou lze snadno stanovit obtížnost hry, avšak při nevhodném zvolení buněk pro aplikaci heuristik může snadno dojít buď k jednotvárnosti, nebo trivialitě her (hráč odhalí jakým způsobem je Sudoku
11
tvořeno a neřeší jej dále jako Sudoku, ale jako rekonstrukci průběhu vytvářejícího algoritmu). Způsob, jakým jsou čtverce odebrány, do značné míry určuje obtížnost hry. Nezanedbatelným faktorem je zde také hráč, který hru řeší a postupy, které musí použít k dosažení řešení. Opírá-li se řešení o metody založené na jediné možnosti (viz níže), jedná se o lehčí Sudoku. Pokud je k řešení potřeba navíc metody odhalených dvojčat (viz níže), jedná se o průměrné Sudoku. Vyžaduje-li řešení Sudoku použití metod X-Wing (viz níže), Swordfish (viz níže) nebo X-Y Wing (viz níže), jedná se o těžké sudoku (4). Obtížnost však také závisí na počtu nevypuštěných buněk. Lehká Sudoku zpravidla obsahují větší počet nevypuštěných buněk. Pro středně těžká Sudoku je počet nevypuštěných buněk nižší a při generování zadání jsou zakomponovány některé vazby mezi čísly tak, aby byla omezena triviální zadání. U těžkých Sudoku se dále snižuje počet nevypuštěných buněk a lze navíc ošetřit například četnost výskytu jednotlivých čísel nebo rovnoměrnou zaplněnost zadání.
2.2.3 METODY ŘEŠENÍ Řešení Sudoku je možné „vyšlechtit“ za použití genetických učících se algoritmů (15). Algoritmus může de facto hledat vlastní heuristiky za použití několika desítek či stovek tisíc generací. Pro genetické algoritmy jsou klíčové metody pro mutace, křížení a hodnocení zdraví vzorku. Algoritmus nejprve vyšlechtí možný výsledek a poté ohodnotí jak je zdravý. Čím více se vzorek odchyluje od ideálu (korektního řešení splňujícího pravidla) v řádcích, sloupcích a menších čtvercích, tím méně je zdravý – například obsahuje více duplicit, resp. prázdných buněk. Pokud je vzorek zcela zdravý, jedná se o řešení. Takový vzorek je zařazen do genofondu populace. Pokud vzorek zdravý není, vymírá. Postupně takto vzniká populace zdravých vzorků s geny pro řešení Sudoku (de facto jednotlivými heuristikami). Ze začátku je algoritmus velmi pomalý, ale se zvětšující se populací se zvyšuje i rychlost jakou algoritmus Sudoku řeší.
Algoritmus hrubé síly a heuristiky Alternativou ke genetickým algoritmům je algoritmus používající hrubé síly (tzv. brute force algorithm). (14) Pro řešitele rébusů je známý spíše jako metoda pokus-omyl. (4) Jedná se o implementačně jednoduchý algoritmus, který postupně vkládá čísla do dané mřížky (zadání). Nejprve se pokusí vložit do první volné buňky číslo 1. Zkontroluje, zda se jedná o číslo, které nekoliduje s pravidly. Pokud číslo nekoliduje, postoupí algoritmus do další buňky. Pokud číslo s pravidly koliduje, vyloučí jej z možných hodnot buňky a pokusí se stejným způsobem vložit číslo 2. Takto postupuje až k druhé mocnině základního čísla. Vyloučí-li algoritmus pro některou buňku všechny možnosti, vrací se do předešlých buněk a maže jejich obsah tak dlouho, než se mu v některé podaří nahradit dříve vybranou hodnotu za jinou a začne znovu postupovat kupředu. Ve chvíli, kdy vepíše číslo do poslední buňky, je Sudoku správně vyřešené. Vyčerpá-li algoritmus všechny hodnoty pro první volnou buňku zadání aniž by došel k výsledku, zamítá a daná hra nemá řešení. Algoritmus ve
12
většině případů vyřeší zadanou mřížku v rozumném čase, avšak ve srovnání s heuristikami je pomalejší.
Metody jedné možnosti Heuristiky (16) se většinou využívají právě v kombinaci s algoritmem hrubé síly. Snižují počet možností, ze kterých musí algoritmus vybírat za použití lidských metod řešení Sudoku. Pro člověka poněkud pracná, ale pro počítač velmi snadná heuristika spočívá ve zjištění hodnot, které je možné do každé jednotlivé buňky dosadit. Poté jsou vyplněny všechny buňky, které mají pouze jednu možnou hodnotu, a celá heuristika se opakuje (ObráObrázek 2.17 zek 2.17). Heuristiky jedné možnosti patří mezi nejlehčí. (17) Do dané buňky lez vepsat pouze jedinou hodnotu, protože řádek, sloupec či menšího čtverec ve kterém se buňka nachází je již, až na danou buňku, zcela zaplněn (Obrázek 2.18 – černě). Může se také jednat o, na první pohled ne zcela zřejmý řádek, sloupec či menší čtverec s několika možnostmi umístění chybějících čísel, kde jsou však pro jednu z buněk možné permutace zredukovány na jedinou, Obrázek 2.18 díky hodnotám v ostatních sloupcích, řádcích či menších čtvercích.
Metoda dvojčat Další heuristikou je metoda dvojčat (17). Metoda hledá každé dvě buňky A a B v řádku R, sloupci S nebo menším čtverci M takové, že do nich lze vložit právě dvě čísla X a Y a nelze určit, do které z buněk patří X a do které Y (Obrázek 2.19 – černě). Buňky A a B nazýváme dvojčata. Protože čísla X a Y jsou v buňkách A a B, pro ostatní buňky v R, S nebo M platí, že nemohou obsahovat ani Obrázek 2.19 X ani Y. Pokud jsou A a B zároveň například v jednom řádku a menším čtverci, jsou X a Y vyloučeny jak z řádku, tak z menšího čtverce. Tímto způsobem je zredukován počet možností pro ostatní buňky.
13
Metoda X-Wing Jednou z těžších metod je metoda X-Wing. (17) Metoda hledá číslo Z, které lze vložit do dvou buněk určitého řádku - R1. Tyto buňky leží ve sloupcích S1 a S2. Poté metoda hledá jiný řádek – R2, ve kterém je do buněk ve sloupcích S1 a S2 také možno vložit číslo Z. Vyhovující buňky v řádcích R1 a R2 (Obrázek 2.20 – světle šedě) tvoří pomyslný obdélník a nazývají se X-Wing, protože Z se vyskytuje v buňkách na jedné z úhlopříček tohoto obdélníku. Nalezne-li metoda řádky R1 a R2, resp. sloupce S1 a S2, odstraní číslo Z z možných hodnot ostatních buněk (Obrázek 2.20 – tmavě šedě) v R1, R2, S1 a S2. Metodu lze aplikovat, nenacházejíli se R1 a R2 ani S1 a S2 ve stejném menším čtverci. Číslo Z v metodě je možné obměnit za dvojčata s hodnotou X a Y. Pro dvojčata platí, že X se vyskytuje na jedné úhlopříčce obdélníku tvořeném buňkami X-Wing a Y na druhé (nebo obráceně). Z ostatních buněk v řádcích R1, R2, resp. sloupcích S1 a S2, lze odebrat jak hodnotu X, tak hodnotu Y. Obrázky 2.20
Metoda Swordfish Metoda Swordfish (13) (17) je modifikací metody X-Wing, ve které vystupuje jedno číslo Z a tři sloupce a řádky do kterých je možno Z umístit (Obrázek 2.21 – světle šedě). Výběr řádků a sloupců splňuje podobná kritéria jako u metody X-Wing. Rozdílem je, že jeden z rohů pomyslného obdélníku X-Wing zůstane prázdný (Obrázek 2.21 – buňka označená symbolem .) a je nahrazen útvarem složených ze zbylých tří buněk, který připomíná meč (odkud název heuristiky), ve skutečnosti se jedná o jiný X-Wing, kterému také chybí jeden roh. Výsledkem správné aplikace metody je odebrání čísla Z z buněk tří sloupců a tří řádků, které se do metody zapojují (Obrázek Obrázek 2.21 2.21 – tmavě šedě).
14
Metoda X-Y Wing Metoda X-Y Wing (18) (nebo také Hook, volně přeloženo „háček“) hledá tři buňky, z nichž dvě se nalézají ve stejném menším čtverci a dvě ve stejném řádku nebo sloupci (Obrázek 2.22 – světle šedě). Kromě pozice, je také důležité, aby každá z buněk měla pouze dva možné kandidáty. Pro každou jednu buňku musí dále platit, že obsahuje dvojče pro zbylé dvě buňky. Takovéto rozložení umožňuje pouze dvě alternativy (Obrázek 2.22 – druhé, resp. třetí patro) a čísla musí být rozložena právě v těchto buňkách. Metoda vyzkouší obě varianty a hledá každou buňku A (Obrázek 2.22 – černě), pro kterou je v obou variantách vyloučeno z možných hodnot alespoň jedno (stejné) číslo vybrané do X-Y Wing Z. Pro každou buňku A pak platí, že nemůže obsahovat číslo Z a počet Obrázek 2.22 možných hodnot buňky A je tedy snížen.
Knuthův algoritmus X K vyřešení Sudoku lze použít též algoritmus tančících odkazů (Dancing Links), který je implementací nedeterministického, rekursivního algoritmu prohledávání do hloubky se zpětným sledováním - Knuthova algoritmu X (20) (21). Algoritmus X hledá všechna řešení pro následující, maticí reprezentovaný problém. Mějme obor hodnot O = {1, 2, 3, 4, 5, 6, 7, 8, 9} a množinu jeho libovolných neprázdných podmnožin S = {A, B, C, D, E, F, G, H, I, J, K}. Knuthův algoritmus pak hledá množinu R tvořenou disjunktními prvky množiny S, jejíchž složením vznikne množina O. Matice na vstupu algoritmu pak obsahuje pouze 1 nebo 0 dle toho, zda se v dané podmnožině nalézaný daný prvek (řádky matice odpovídají prvkům z S, sloupce prvkům z O. Za hodnotu v matici Obrázek 2.23 je dosazena 0, pokud prvek v daném sloupci není prvkem podmnožiny v daném řádku a 1, pokud prvek v daném sloupci je prvkem podmnožiny v daném řádku). Obrázek 2.23 ukazuje příklad takového rozložení. (19)
15
Obrázek 2.26
Obrázek 2.27 Obrázek 2.25
Obrázek 2.24
Obrázek 2.28
Algoritmus nejprve testuje, zda je zadaná matice prázdná. Pokud ano, nalezl řešení a úspěšně končí. Pokud matice není prázdná, vybere sloupec s (na obrázcích 2.24 – 2.28 světle šedě) s nejnižším počtem 1 a poté pro všechny řádky r (na obrázcích 2.24 – 2.28 tmavě šedě), které ve sloupci s obsahují také 1, jednotlivě provede následující kroky (zde dochází k větvení):
zahrne r do možného řešení (množiny R). Pro každý sloupec v daném řádku r, který obsahuje 1, nalezne mezi zbylými řádky ty, které také obsahují 1 (kolize jsou na obrázcích 2.24 – 2.28 značeny černě) a řádky odstraní. Odstraní řádek r
Poté se celý algoritmus znovu iteruje (obrázky 2.24 – 2.28 znázorňují průběh algoritmu, vybere-li si vždy správnou větev řešení). Pokud by byl nejnižší počet 1 v dané iteraci roven 0 a zároveň by vstupní matice byla neprázdná, algoritmus skončí v této větvi neúspěšně. Jedná-li se o kořen, problém nemá řešení. Protože Sudoku klade na čísla čtyři hlavní omezení (každá buňka je obsazena právě jedním číslem, jeden řádek, sloupec a menší čtverec obsahuje každé číslo právě jednou), je oborem hodnot O Sudoku množina všech možností pro všechna pole ve všech omezeních – tedy 4×základní číslo umocněné na čtvrtou (pro Sudoku 9x9 je to 324 možných hodnot a tedy i sloupců matice). Podmnožinou S jsou pak všechny možnosti umístění jednotlivých kandidátů (pro Sudoku 9x9 čísla 1…9). Každá množina z S tedy obsahuje čtyři 1, dle toho kde je daný kandidát umístěn vůči řádku, sloupci, menšímu čtverci a jakou má hodnotu. Těchto kandidátů je šestá mocnina základního čísla (pro Sudoku 9x9 je to 729 kandidátů a tedy i řádků matice). Ve výsledku algoritmu pak musí být obsaženy předvyplněné buňky rébusu (zadání).
16
3
GENERÁTOR SUDOKU A NURIKABE
3.1
APLIKACE DOSTUPNÉ PRO BĚŽNÉ UŽIVATELE
Hráč Sudoku nalezne na Internetu širokou škálu aplikací. Internetové aplikace poskytují nejvíce různých použití řešících technik a různých zadání i forem Sudoku. Mezi nejznámější Internetové aplikace patří www.puzzle-sudoku.net, server je jedním ze skupiny podobně zaměřených serverů poskytujících zadání i nástroje k řešení různých rébusů. Existují i freewarové aplikace, například SuDoku solver (22) od společnosti Gwerdy Software. Ačkoli SuDoku solver negeneruje vlastní Sudoku, vysvětluje jednotlivé kroky a heuristiky potřebné k vyřešení zadaného rébusu. Jednou z komerčních aplikací je Sudoku Dragon (23) – aplikace je velmi propracovaná a komplexní, webová prezentace je částečně věnována samotné aplikaci a částečně hře Sudoku. Díky svému úzkému zaměření implementuje několik technik ulehčujících řešení rébusů (například umožňuje uživateli obarvit libovolná pole šesti různými barvami, zapisovat do jednotlivých buněk možné kandidáty a podobně). Aplikace umí vygenerovat nové zadání i pomoci uživateli s řešením. Díky své popularitě si Sudoku získalo velké množství implementací a uživatelských řešení. Naopak hrou Nurikabe se tolik aplikací nezabývá. Nejvíce Nurikabe lze získat online – například server www.puzzle-nurikabe.com (stránky jsou i v češtině), který nabízí velmi kvalitní aplikaci a velkou databázi zadání rébusů. Počet zadání se den ode dne, u větších Nurikabe týden od týdne, zvyšuje. Jednou z mála freewarových aplikací je ruské Nurikabe (24) z roku 2003. Na mnoha internetových stránkách, ačkoli se jedná o pouhý zlomek ve srovnání se stránkami věnovanými Sudoku, jsou popisovány heuristiky používané k řešení Nurikabe. Většina z nich je v anglickém či jiném jazyce – české servery se Nurikabe věnují spíše okrajově, většinou lze nalézt pouze zevrubný popis pravidel hry s jednou, ojediněle několika ukázkami.
3.2
ANALÝZA POŽADAVKŮ A STRUKTURY APLIKACE
Aplikace vygeneruje uživateli nové zadání z prázdné mřížky v rozumném čase, aby mohl uživatel začít hrát krátce po jejím spuštění. Vzhledem k dostatečnému množství zadání vyskytujících se na Internetu i v tištěné podobě je vhodné umožnit uživateli importovat zadání nebo je vpisovat přímo do aplikace. Pro další zpracování vygenerovaného zadání je umožněn i export. Ačkoli se jedná o hru pro jednoho hráče, je aplikace schopna uchovávat výsledky her více různých hráčů a porovnávat je. Volba obtížností nemusí být zcela striktní. Volnější volbou obtížnosti hry získá soutěžení více hráčů určitou míru náhody a podpoří jejich soutěživost. Prioritním ukazatelem úrovně hráče obou rébusů je průměrný čas, který hráč potřebuje k vyřešení rébusu určitých rozměrů a obtížnosti. Pro hráče, kteří dávají přednost nejtěžším variantám her a dlouhým chvílím stráveným přemýšlením nad dalším logickým krokem, musí aplikace nabídnout možnost návratu ke konfiguraci před uskutečněním kroku. Pro začínající hráče nabízí program možnost
17
napovědět další krok řešení, který se hráči nedaří odhalit. Je vhodné, aby byla aplikace alespoň barevně přizpůsobitelná – uživatel by měl mít možnost přetvořit „obyčejnou staženou“ aplikaci, na aplikaci, kterou bude považovat za jedinečnou, vlastní. Aplikace musí být snadno ovladatelná jak pouze klávesnicí, tak pouze myší. Aplikace nemá instalátor a je přenosná, nevyužívá k uložení vlastních dat registry ani složky systému, všechna data aplikace jsou uložena v adresáři se spouštěcím souborem – uživatel ji tak může nahrát například na Flash disk a spustit na libovolném stroji. Nutností je, vzhledem k povaze rébusů, využití vláken. Protože vlákna mohou využít značnou část výkonu stroje, na kterém je aplikace spuštěna a doba nutná pro generování nebo řešení rébusu nemusí být vždy triviální, musí mít uživatel kontrolu nad činností aplikace, resp. jí spuštěných vláken. Cílová skupina aplikace zahrnuje hráče s omezeným přístupem na Internet (například lidé, kteří často cestují prostředky hromadné dopravy na delší vzdálenosti) nebo skupiny, které chtějí porovnávat své výsledky. Lidé s přístupem k Internetu budou často raději volit některou z online alternativ, neboť předgenerovaná zadání rébusů jsou k dispozici ihned. Internetové aplikace však většinou nenabízí možnost soutěže. Generované hry nemusí vykazovat vyšší stupeň obtížnosti, než jakého lze dosáhnout bez výrazného prodloužení času nutného k vytvoření hry. Jednotlivé rébusy jsou uloženy v samostatných jednotkách aplikace. Aby bylo možné aplikaci eventuálně modifikovat či rozšířit, musí existovat jednotka obsahující základní, často používané datové typy a metody a interface společný pro oba rébusy – tím je také usnadněna implementace grafického uživatelského rozhraní. Z analýzy metod řešení a generování obou rébusů vyplývá, že budou často vznikat kopie existujících sítí her – každá třída musí obsahovat klonovací metodu. Pro zvýšení efektivity je vhodné použít základních systémových struktur, které umožňují využití nízkoúrovňových systémových metod (například kopírování dynamických polí apod.). Protože aplikace umožňuje jazykové mutace, musí mít uživatel možnost nastavit velikost u co nejvíce ovládacích prvků tak, aby bylo možno jejich názvy zobrazit celé. Aplikace si rozměry musí pamatovat i při dalším spuštění. Při odhadu velikosti generovaných zadání je třeba vycházet ze dvou předpokladů. Vzhledem k široké nabídce různých zdarma dostupných aplikací a téměř nekonečnému počtu variant zveřejněných zadání se aplikace zaměřuje na soutěžení a umožňuje import a export zadání. Velikost mřížky Sudoku překračující 9x9 buněk není nutná, neboť většina hráčů větší Sudoku neřeší. Nurikabe je většinou dostupné pouze předgenerované. Některé servery sice nabízí generování Nurikabe 5x5 v reálném čase, ale u větších rozměrů je nové Nurikabe vytvořeno přibližně 1 krát denně. Aplikace tedy generuje hry s rozměry mezi 5x5 až 12x12 buněk, avšak podporuje i jiné formáty mřížek než sama vytváří.
18
3.3
POPIS ALGORITMŮ GENERUJÍCÍCH A ŘEŠÍCÍCH RÉBUSY
Z pohledu rébusů obsahuje aplikace společnou jednotku (CommonUnit), ve které se nachází základní třídy a datové typy společné pro oba rébusy. Jsou zde procedury a funkce pro práci s dynamickými poli, manažer vláken nebo třída definující rozhraní obou rébusů (TGame). Jedou z nejdůležitějších datových tříd je třída TSquares, která kromě uskladnění hodnot jednotlivých buněk sítě umožňuje převod z lineárního indexu na číslo řádku a sloupce buňky v rébusu a jejímiž potomky jsou TSudokuSquares a TNurikabeSquares (viz podkapitoly 3.3.1 a 3.3.2). Při vytváření třídy TSquares je zadán počet prvků a počet sloupců. Následně jsou vnitřní dynamická pole pro hodnotu, číslo řádku a číslo sloupce nastavena na zadaný počet prvků a konstruktor spočítá čísla řádků a sloupců pro všechny buňky rébusu. Protože se jedná o dynamické pole, indexem buňky v levém horním rohu je nula, stejně tak index jejího řádku a sloupce je roven nule. Aby byla zachována konformita, čísla ukládaná do pole jako hodnoty buněk jsou rovněž snížena o 1 (je-li reálná hodnota buňky v rébusu rovna 5, bude v poli hodnot uvnitř TSquares uložena jako 4), nemá-li buňka žádnou hodnotu, je číslo obsažené v poli hodnot uvnitř TSquares rovno SQ_NIL (jednotkou CommonUnit definovaná konstanta, jež slouží jako číselný ekvivalentem ukazatele NIL). Další důležitou třídou je třída TGame. Tato třída vytváří rozhraní pro komunikaci mezi uživatelským rozhraním a algoritmy rébusů, které jsou potomky této třídy (TSudoku a TNurikabe). Každé hře lze zadat parametry jako velikost čtvercové sítě, obtížnost, počet hledaných řešení, apod. Každá hra má také příkaz pro vygenerování nového zadání, restartování hry, automatické vyřešení a ověření, zda je zadáno korektní řešení. Potomci třídy TGame také obsahují množinu nalezených řešení, metody pro základní práci s grafikou a hodnotami buněk. Každou hru je možné naklonovat metodou clone. Úzce spjaty s generováním a řešením rébusů, a tedy i třídou TGame, jsou třídy vláken. TGamePositionThread, obsahuje pozici pro indikátor průběhu a aktuálně řešený index ve čtvercové síti. Tato třída slouží jako základ pro vlákna zabývající se generováním rébusů. Potomkem třídy TGamePositionThread je třída TGameThread, která navíc obsahuje některé řídící prvky důležité pro generování rébusů (například instanci rébusu TGame nebo proměnnou pContiue, jejíž hodnota rozhoduje, zda pokračovat v řešení daného vlákna daného rébusu apod.). Pro ovládání vláken jsou nezbytné třídy TThreadController a její potomek TGameThreadController. První zmiňovaná třída se stará o vlákna typu TGamePossitionThread, druhá o vlákna typu TGameThread – spouští je, pozastavuje a vkládá nová. Manažerům vláken lze nastavit nejvyšší počet vláken, která mohou být spuštěna současně a metody, které se mají provést, pokud vlákno skončí úspěšně či neúspěšně. Součástí každého manažeru je také metoda prováděná při iteraci cyklů uvnitř vláken, která je zodpovědná za jejich případné přerušení na pokyn uživatele a přes kterou každé vlákno sděluje informace o svém aktuálním stavu, aby mohly být zobrazeny uživateli.
19
Pokud je volána metoda pro řešení nebo generování rébusu, je v obou hrách vytvořeno kořenové vlákno, které je umístěno do příslušného manažeru vláken. Následuje nekonečná smyčka, kterou ukončuje buď manažer vláken (pokud jsou všechna v něm obsažená vlákna ukončena) nebo uživatel ukončením aplikace. Pokud chce uživatel přerušit proces, jsou vlákna informována přes metodu OnInterate, vlákna se následně ukončí a poté příslušný manažer vláken ukončí nekonečnou smyčku. Při budování jednotky hry je nejprve nutné vybudovat potomka třídy TGame. Protože ověření korektnosti je v porovnání s generováním nebo řešením snadné, je toto ověření zabudováno přímo do třídy TSudoku i TNurikabe. Poté je třeba vytvořit řešící algoritmus, schopný nejen vyřešit dané zadání, ale i nalézt ostatní možná řešení nebo vyloučit jejich existenci. Čím lépe jsou implementovány heuristiky, tím více je omezeno použití náhody a tedy i větvení; čím méně větví algoritmy řeší, tím rychleji vyloučí existenci ostatních řešení.
3.3.1 NURIKABE Lidé nejčastěji používají řešící heuristiky v nativním pořadí. Toto pořadí se u jednotlivců většinou liší a často lidé používají metodu „podívám se a vidím“ k tomu, aby podvědomě nalezli vhodnou heuristiku pro danou skupinu buněk, která upoutala jejich pozornost. S ohledem na počítačové zpracování jsou heuristiky uspořádány tak, jak je uvedeno níže. Následuje základní charakteristika implementace jednotky rébusu Nurikabe. Třída TNurikabeSquares je potomkem třídy TSquares. Navíc oproti TSquares uchovává o každé buňce v síti její typ - zeď, cesta, uživatelem označená zeď (dále hvězdička).
Řešící algoritmy Důležitá část algoritmů spjatých s řešením rébusu Nurikabe je obsažena ve třídě vláken TNurikabeSolveThread. Tato třída je potomkem TGameThread a obsahuje navíc proměnnou valid typu boolean a blacksInfos typu TBlackPathsArray (jedná se o pole záznamů TBlackPath). Obě proměnné jsou používány hlavně uvnitř metody execute. Proměnná valid značí, zda je řešící větev korektním Nurikabe nebo došlo použitím heuristik ke sporu. Záznam TBlackPath popisuje cesty uvnitř Nurikabe. Každá buňka ve čtvercové síti má svůj záznam tohoto typu. Je-li buňka cestou, obsahuje záznam počet z ní přístupných buněk (tedy, těch, kde ještě není jistá ani cesta ani zeď) – rank (Obrázek 3.1 – malá šedá čísla); hodnotu groupRankOrLink, určující buď součet přístupných buněk za celou skupinu cest (označme jako skupinu každou cestu složenou z alespoň jedné buňky cesty; Obrázek 3.1 – bílá čísla) nebo index jiného záznamu TBlackPath (odkaz; Obrázek 3.1 – šedé křivky); a booleanový přepínač isGroupRank, který určuje, jestli je hodnota groupRankOrLink odkazem či hodnotou. Každá skupina obsahuje právě jednu buňku, která nese hodnocení celé skupiny (její isGroupRank je nastaveno na hodnotu True), tuto buňku nazývejme hlavní buňka dané cesty.
20
Obrázek 3.1
Pokud je někde utvořena buňka cesty, její rank je nastaven na hodnotu odpovídající počtu okolních přístupných buněk. Stane-li se nová cesta součástí již existující skupiny, je její isGroupRank nastaven na hodnotu False a do groupRankOrLink je uložen index hlavní buňky již existující skupiny. Pokud nově přidávaná buňka cesty slučuje více již existujících skupin, je vybrána jedna, hlavní, skupina. U zbylých, vedlejších, skupin, je nalezena hlavní buňka. Hodnoty obsažené v groupRankOrLink hlavních buněk vedlejších skupin jsou přičteny k hodnotě groupRankOrLink hlavní buňky hlavní skupiny. Vedlejší skupiny jsou napojeny na hlavní tak, že hodnota jejich hlavní buňky (Obrázek 3.1 – symbol .) isGroupRank je nastavena na False a groupRankOrLink na index hlavní buňky hlavní skupiny. Neníli nová cesta součástí již existující skupiny ani neslučuje více již existujících skupin, je hodnota groupRankOrLink nastavena na stejnou hodnotu jako proměnná rank a isGroupRank je nastavena na hodnotu True. Původně se o plnění struktury starala samostatná metoda, avšak při optimalizaci došlo k začlenění této funkcionality do metody changedHeuristicUsed, která je volána po každé změně typu buňky heuristikou a jejíž původní funkcí bylo pouze zjistit, zda ke změně danou heuristikou opravdu došlo nebo bylo aktuální hodnoty dosaženo z více heuristik najednou. Takto vzniká struktura, umožňuje kontrolovat souvislost cesty. Kontrolní mechanismus zkoumá, kolik obsahuje Nurikabe uzavřených (bez možnosti dalšího napojení nebo prodloužení) a kolik otevřených (s alespoň jednou možností dalšího napojení nebo prodloužení) skupin buněk cest. Validní Nurikabe může obsahovat libovolný počet otevřených skupin cest nebo právě jednu uzavřenou skupinu. Ze struktury také vychází heuristika sledování jediné možnosti dalšího vývoje skupiny – pokud není Nurikabe kompletní, a okolní konfigurace zdí umožňuje určité skupině buněk cest pouze jedinou možnost kudy se vydat, využije ji: Pokud nalezne skupinu, která má groupRankOrLink hlavní buňky rovno právě jedné, nalezne heuristika buňku cesty, která má rank roven jedné a je součástí této skupiny cest (její groupRankOrLink odkazuje na hlavní buňku skupiny s groupRankOrLink rovným jedné) a spustí funkci blackRunner (viz níže). Dále struktura TBlackPathsArray ovlivňuje výběr náhodné buňky. Pokud se řešícímu algoritmu nepodaří použít žádnou z heuristik, vybere určitou skupinu konfigurací zdí (viz níže), pokud neexistuje žádná skupina konfigurací zdí, vybírá algoritmus náhodně jednu buňku s nejnižším ohodnocením (rank). Nejprve algoritmus nalezne všechny skupiny cest, které mají nejnižší groupRan-
21
kOrLink hlavní buňky a všechny buňky těchto skupin vloží do vzestupně seřazeného pole. Z tohoto pole vybere jednu náhodnou buňku z buněk s nejnižším rank a z přístupných buněk v jejím okolí opět náhodně jednu náhodně vybere (dále náhodná buňka). Zde se řešící algoritmus větví – v jedné větvi náhodná buňka reprezentuje cestu, v druhé zeď. Uvnitř metody execute se nachází některé důležité proměnné použité pro řešení rébusu. První z nich je reachables pole Bytů s jedním negativním prvkem (-1…254). Do pole reachables zapisuje heuristika dosažitelných buněk hodnoty odpovídající vzdálenosti dané buňky od poslední zkoumané buňky obsahující číslo (Obrázek 3.2). Pokud je některá buňka mimo dosah všech čísel, je její hodnota v poli reachables rovna mínus jedné. Hodnoty jsou do pole zapisovány s ohledem na aktuální konfiguraci Nurikabe - to znamená, že pokud je Obrázek 3.2 někde buňka zdi A jistě patřící k některému číslu, N, a jsou zkoumány buňky dosažitelné z jiného daného čísla M, nebudou za (z M) dosažitelné považovány takové buňky, ke kterým se lze dostat pouze přes buňku A, ani buňky hranově sousedící s A. Podobně je postupováno i u buněk s čísly – buňka hranově sousedící s buňkou s číslem nebude dosažitelná z žádného jiného čísla. Heuristika tvoří zdi, pokud existuje pouze jediná možnost jak do prostoru kolem libovolného čísla zeď postavit. Při procházení okolí čísla algoritmem procházení do šířky jsou jednotlivá pole ukládána do záznamu typu TWhitePath, který obsahuje hlavně informaci o indexu buňky s číslem – ownerIndex a pole indexů buněk zdi - path. Pokud je po ukončení algoritmu procházení do šířky plocha zdi zaznamenané v poli path rovna hodnotě čísla zdi, je zeď postavena a z buněk hranově sousedících s buňkami nové zdi jsou vytvořeny buňky cest (Obrázek 3.3 – buňky označené písmenem X). Je-li plocha zaznamenané zdi o jedna nižší než je hodnota čísla zdi, je cesta uložena do TWhiteInfos (viz níže). Tato heuristika je implementována cyklem procházejícím všechna čísla v Nurikabe od levého horního k pravému dolnímu rohu. Díky tomu, že tato heuristika vytváří nové buňky jak cest, tak zdí, je třeba ji zopakovat alespoň dvakrát po sobě. Zároveň se jedná o zcela první heuristiku aplikovanou na rébus. Druhou důležitou proměnnou metody execute je unreachable – pole indexů pro každou buňku. Toto pole je také úzce spjato s výše popsanou heuristikou dosažitelných buněk. Pokud při použití ostatních heuristik dojde k omezení dosahu některého čísla (například heuristika „prodeje hvězdiček“ (viz níže) často přiřadí číslu bezprostředně nesousedící hvězdičku H, a ačkoli neexistuje pouze jediný způsob, kterým je možno zeď mezi hvězdičkou H a číslem postavit, toto přiřazení značně omezí možnosti, kterými může být zeď postavena v jiném směru, než jakým leží hvězdička H od svého čísla. Třetí důležitou proměnnou metody execute je pole indexů markOwners. Každá buňka může být teoreticky hvězdičkou. Obrázek 3.3
22
Pokud hvězdičkou je, má v tomto poli uložen index čísla zdi, ke kterému náleží (nebo hodnotu SQ_NIL, nenáleží-li zatím k žádnému číslu). Buňky obsahující čísla mají v tomto poli pro snazší orientaci algoritmů, které proměnnou markOwners využívají, uložen index sebe sama. Heuristika „prodeje hvězdiček“ následuje po heuristice dosažitelných buněk. Nalezne všechny takové hvězdičky v Nurikabe vytvořené jinými heuristikami, které ještě nemají vlastníka uloženého v poli markOwners (hodnota těchto buněk v markOwners je SQ_NIL). Pro každou hvězdičku (H) spočítá za použití metriky newyorského taxikáře (25) nejvyšší číslo, jehož zdi může být hvězdička součástí (Obrázek 3.4 a Obrázek 3.5 – čárkovaně), označme toto číslo V. V této části se heuristika nezabývala skutečnou konfigurací čtvercové sítě hry. Obrázek 3.4 Algoritmem prohledávání grafu do šířky (omezeným co do vzdálenosti od středu hledání, tedy hvězdičky H, hodnotou V) nalezne heuristika všechna čísla, která mohou utvořit zeď s H a zároveň všechny tvary takových zdí (Obrázek 3.4 a Obrázek 3.5 – plnou čarou). Neexistuje-li pro danou hvězdičku H žádný potenciální vlastník, větev řešícího algoritmu končí neúspěchem. Existuje-li více potenciálních vlastníků (Obrázek 3.5), jsou všechny připustitelné konfigurace zdí zařazeny do sktruktury TWhiteInfos (viz níže). Nalezne-li heuristika právě jednoho vlastníka P (buňku s číslem) pro hvězdičku H (viz Obrázek 3.4), jsou všechny nalezené konfigurace otestovány na vzájemný průnik. Obsahuje-li takový průnik více buněk než jen H a P, jsou zbylé buňky průniku označeny hvězdičkou a získají vlastníka P (Obrázek 3.4 – znak !). Existuje-li pouze jediná konfigurace Obrázek 3.5 zdi mezi H a P, je tato zeď postavena a obklopena buňkami cesty dle pravidel Nurikabe. Další použitou heuristikou je křížová heuristika. Tato heuristika je postupně aplikována na každou buňku Nurikabe. Heuristika zanalyzuje nejbližší okolí zadané buňky B na horizontále a vertikále – spočítá buňky existující v okolí (triviálně má každá buňka čtyři sousedy, avšak v rozích čtvercové sítě jsou sousedé pouze dva a na hranách tři) - validNeighboursCounter, kolik ze sousedů je buňkou cesty (processedPathCounter), kolik je tvořeno zdmi (processedBlockCounter), kolik čísel obsahují sousedé (numbersAroundCounter) a jak jsou rozmístěny ještě neurčené buňky (freeIndexSum). Hodnota freeIndexSum je určována jako součet pozic okolních buněk buňky B, kde levý soused má pozici Obrázek 3.6 0, horní soused 1, spodní 2 a pravý 3. Je-li buňka B zdí o ploše
23
1, jsou její sousední buňky nastaveny na cestu (pokud jsou již však nastaveny na zeď nebo číslo, algoritmus končí větev řešení neúspěchem). Pokud je processedBlocksCounter roven validNeighbourCounter, musí být B zdí (Obrázek 3.6 – světle šedě) nebo zatím neurčenou buňkou (pak je B označena za zeď), není-li tomu tak, větev končí neúspěchem. Stejně tak postupuje algoritmus u cest: Pokud je processedBlocksCounter roven validNeighbourCounter, musí být B cestou (Obrázek 3.6 – tmavě šedě) nebo zatím neurčenou buňkou (pak je B označena za cestu). Obsahuje-li buňka B číslo nebo vlastněnou hvězdičku a existují-li právě dva zatím neurčení sousedé buňky B, zkontroluje heuristika, zda mají právě jednu společnou buňku A (Obrázek 3.7 – tmavě šedě), se kterou jsou spojeni hranou (pokud je freeIndexSum (Obrázek 3.7 – malá černá čísla) roven 1, jedná so u buňku vpravo nahoře od B, pokud je freeIndexSum roven 2, jedná se o buňku vpravo dole, je-li roven 4, buňka A je vlevo nahoře, je-li roven 5, buňka A je vlevo dole od buňky B a je-li freeIndexSum roven 3, jsou volné buňky Obrázek 3.7 vlevo a vpravo, resp. nahoře a dole od buňky B – pro takové nemá tato část křížové heuristiky smysl a buňka A se neurčuje). Určí-li heuristika buňku A a je-li v B číslo 2 nebo je proměnná reachables pro B rovna 1 nebo se kolem buňky A vyskytuje alespoň jedno číslo (krom případné buňky B) a zároveň není A ani číslem, ani vlastněnou hvězdičkou, je buňka A změněna na cestu. Křížová heuristika také testuje, zda nenastala situace, ve které je buňka B cestou a všichni její sousedé až na jednoho jsou zdmi (Obrázek 3.8 – malá bílá čísla na černím pozadí) nebo naopak, je buňka B zdí a všichni její sousedé až na jednoho jsou cestami (Obrázek 3.8 – malá černá čísla na bílém pozadí). V prvním případě, je z buňky B spuštěna metoda BlackRunner, která postupuje po zatím neurčených buňkách a staví na nich cesty do té doby, než narazí na takovou zatím neurčenou buňku, z níž existují alespoň dvě možnosti, kteObrázek 3.8 rými by se mohla metoda vydat dále (Obrázek 3.8 – malá bílá čísla na tmavě šedém pozadí). Tuto buňku změní BlackRunner na cestu, avšak nepokračuje dál. Ve druhém případě je na buňku B (pokud není vlastněna nebo je číslem, kolem kterého není ještě vystavěna kompletní zeď) aplikována metoda WhiteRunner (Obrázek 3.8 – malá černá čísla na světle šedém pozadí). Metoda postupuje velmi podobně jako BlackRunner, s tím rozdílem, že buduje zdi (nikoli cesty) a že ukládá buňky, po kterých se pohybuje do záznamu typu TWhitePath. Obsahuje-li zeď, kterou metoda buduje číslo a je-li plocha zdi rovna hodnotě onoho čísla snížené o jedna, jsou spočteny alternativní zakončení zdi a všechna jsou zařazena do jedné skupiny v TWhiteInfos (viz níže).
24
Po křížové heuristice následuje heuristika čtvercová. Tato heuristika je aplikována na každou buňku Nurikabe. Mějme buňku B1, která je levým horním rohem čtverce B1, B2, B3, B4 o hraně dva (Obrázek 3.9). Heuristika napřed zjistí, jestli se všechny buňky čtverce (B1...B4) nalézají uvnitř čtvercové sítě Nurikabe. Pokud ano, spočte, kolik z nich jsou cesty (processedPaths) a pamatuje si poslední index zatím neurčeného pole (lastFreeIndex – Obrázek 3.9 – světle šedě). Pokud je processedPaths alespoň 3, znamená to, že cesty tvoří tvar L Obrázek 3.9 a aby nebyla porušena pravidla rébusu, musí být lastFreeIndex buď již roven, nebo nastaven na hvězdičku. Vlastník hvězdičky zde zůstává neurčen (sousedí-li hvězdička hranově s číslem, bude k němu připojena v heuristice dosažitelných polí a nesousedí-li s žádným číslem hranově, bude „dražena“ v heuristice „prodeje hvězdiček“. Není-li lastFreeIndex určen, znamená to, že musí být processedPaths roven 4, v cestě vznikl nepovolený pokoj a heuristika ukončí větev řešícího algoritmu neúspěchem. Nyní je zařazena shora popsaná heuristika souvislosti cesty. Pokud byla během iterace hlavního cyklu uvnitř vlákna použita alespoň jedna z výše uvedených heuristik (krom výběru náhodné buňky), cyklus se opakuje a znovu v uvedeném pořadí aplikuje jednotlivé uvedené heuristiky. Nedojde-li však na žádnou takovou heuristiku a hra stále není vyřešena, dochází k větvení. Prvním případem je, že ve struktuře TWhiteInfos se nachází alespoň jedna skupina konfigurací zdí. Typ TWhiteInfos je pole záznamů TWhiteGroup, které obsahují pole záznamů zdí typu TWhitePath (popsané výše), počítadlo konfigurací zdí – counter a průměrnou plochu zdí averageLength. Několik výše popsaných heuristik zaplní, za určitých okolností, toto pole skupinami konfigurací zdí. Konfigurace se v rámci jedné skupiny navzájem vylučují a právě jedna z nich je součástí korektního řešení zadaného Nurikabe. Heuristika nejdříve vybere jednu skupinu konfigurací zdí. Je-li skupina konfigurací právě jedna, je problém triviální. Není-li v poli žádná skupina konfigurací, heuristika dále nepokračuje a je nutné náhodně vybrat buňku cesty, jak je popsáno výše. Při vyšším počtu skupin je vybrána skupina s největší průměrnou plochou zdí a nejmenším počtem konfigurací. První konfigurace je vyhrazena pro stávající větev hry, ostatní konfigurace z vybrané skupiny se větvením oddělí a řeší je nové instance vlákna TNurikabeSolveThread.
Generující algoritmy Při generování nového zadání nejprve metoda execute vlákna TNurikabeGenerateThread vymaže čtvercovou síť a náhodně vybere počáteční buňku. Tuto buňku změní na cestu. Z okolních buněk, do kterých je možno zapsat cestu, si jednu vybere a cestu zapíše. Takto zapíše 3 až 5 buněk cest (o počtu buněk rozhoduje náhoda), poté z buněk, které nemusí obsahovat zeď a neobsahují cestu, vybere náhodně další buňku a opět zapíše 3-5 buněk cest. Tento postup opakuje, dokud nenavštíví všechny buňky Nurikabe a ty nejsou
25
označeny za cestu nebo zeď. Tímto postupem je dosaženo větší rozmanitosti maximálních cest v rámci dané čtvercové sítě. Při testování buněk, respektive jejich změně na cesty, se aplikuje pouze metoda odhalující pokoje velikosti 2x2. Po dokončení maximální cesty jsou metodou solveThreeInCorners eliminovány případné výskyty čtvercové rohové symetrie. Metoda nejprve spočítá indexy buněk rohů, pro tyto buňky stanoví indexy rohového čtverce metodou třídy TNurikabe resolveRightBottomSquare (metoda vrací postupně indexy pravé, spodní a pravé-spodní buňky sousedící se zadanou buňkou). Ve čtvercích obsahujících pouze jednu buňku cesty (Obrázky 3.10 a 3.11 – buňka se symbolem !) ověří metodou blackSkipper zda je možné cestu bezpečně odeObrázek 3.10 brat a pokud ano, nahradí buňku cesty buňkou zdi. Metoda blackSkipper je aplikací procházení grafu do hloubky, nejprve je prohledávání spuštěno na prvního hranového souseda zadané vstupní buňky obsahujícího cestu (Obrázky 3.10 a 3.11 – tmavě šedě). Každé navštívené buňce cesty je nastavena pravdivostní hodnota True. Po skončení prohledávání do hloubky jsou testováni zbylí hranoví sousedé vstupní buňky obsahující cestu (Obrázky 3.10 a 3.11 – světle šedě), zda byli navštíveni. Pokud ne (Obrázek 3.11), odebráním zadané buňky by v Nurikabe vznikly dvě nepropojené cesty a metoda vrací hodnotu False, v opačném případě (Obrázek 3.10) je možné vstupní buňku cesty „přeObrázek 3.11 skočit“ aniž by byla porušena herní pravidla a metoda vrací True. Do takto vygenerovaného Nurikabe se metoda tryFillNumbers pokusí vepsat čísla. Pro práci s jednotlivými uspořádáními čísel ve zdech, zavádí metoda strukturu whiteBlocks, jedná se o pole záznamů typu TWhiteBlock. Záznam se skládá z proměnné possition (určující pro každou zeď buňku, ve které má být umístěna velikost plochy zdi), plochy zdi – length a vždy seřazeného dynamického pole indexů buněk blockSquares typu TRandomArray. Každému indexu v poli TRandomArray je přiřazena hodnota – rank, která jej zařazuje v rámci vzestupně seřazeného pole výše či níže. Toto pole je totožné s polem používaným při výběru náhodné buňky při řešení Nurikabe, zde však slouží k upřednostnění určitých buněk zdí před jinými. Do struktury whiteBlocks nejprve metoda tryFillNumbers uloží všechny zdi. Každý záznam typu TWhiteBlock nese informace o jedné zdi a v něm uložené pole blockSquares seřazené indexy buněk zdi. Buňky dostanou rank dle toho, jaký mají poměr sousedních zdí a sousedních cest (čím více cest, tím blíže k okraji zdi buňka leží, resp. tím spíše je v některém výčnělku zdi – tato umístění mají nevyšší pravděpodobnost na splnění podmínek unikátnosti, je-li do nich vloženo číslo označující plochu zdi). Do struktury jsou zahrnuty pouze ty zdi, které nemají v žádné své buňce číslo (tato modifi-
26
kace je nutná pro použití v dalších částech algoritmu generování Nurikabe) a mají plochu větší než jedna (buňky zdí plochy jedna bez čísla, jsou během ukládání ostatních zdí do struktury whiteBlocks triviálně doplněny hodnotou 0). Metoda dále uloží aktuální stav Nurikabe. Poté vloží číslo zdi do buňky označené proměnnou position v záznamu blockSquares v každém záznamu whiteBlocks, odstraní cesty a pokusí se pomocí výše popsaného řešícího vlákna nalézt 2 řešení. Nalezne-li metoda tryFillNumbers právě jedno řešení, dále nepokračuje a vrací True. Pokud nalezne řešení 2, zvýší parametr possition prvního nenulového záznamu whiteBlock o jedna (v modulo počtu buněk dané zdi), vrátí se k dříve uloženému stavu Nurikabe a opakuje umístění čísel do zdí. Projde-li metoda tryFillNumbers všechny možnosti, aniž by nalezla jediné možné umístění chybějících čísel takové, že po odstranění cest vznikne rébus s jedinečným řešením, vrátí False. Uspěje-li (v téměř všech případech je metoda tryFillNumbers aplikovaná na nově vygenerovanou maximální cestu, resp. její zdi, úspěšná již v první iteraci cyklu a to díky velkému počtu zdí o ploše 1 nebo absenci zdí o ploše větší), začne algoritmus slučovat jednotlivé zdi. Nejprve určí počet zdí v Nurikabe – to provede zjištěním počtu buněk obsahujících číslo – a stanoví proměnnou numbersCounter, která určuje, kolikrát se sloučení zdí provede. Zdí, které sloučí, nesmí být příliš mnoho ani příliš málo z důvodů uvedených v kapitole 2.1.1. Minimem je jedno sloučení pro Nurikabe, které má méně než 4 zdi nebo třetina počtu zdí pro Nurikabe s více než 3 zdmi. Maximum je stanoveno jako polovina počtu existujících zdí – při vyšší hodnotě je generování nového Nurikabe pomalejší a jeho obtížnost se nezvyšuje. Při nižší horní hranici vznikají triviální Nurikabe. Metoda náhodně vybere počet sloučení z výše uvedeného rozmezí. Poté provádí cyklus, ve kterém nejprve stanoví všechny buňky spojení (viz níže), odebere nevyhovující buňky (viz níže) a ze zbylých náhodně vybere spojení zdí, které uskuteční. Metodou tryFillNumbers se do nové zdi pokusí vepsat její plochu (neuspěje-li, náhodně vybírá jiné spojení). Tento cyklus opakuje právě numbersCounter-krát. Pro nalezení vazeb mezi zdmi je nejprve lineárně procházena síť Nurikabe, dokud metoda nalezne první buňku cesty, z ní prochází zbylé buňky cest metodou procházení do hloubky. Každá buňka je testována na sousední zdi. Pokud spojuje více zdí, je uložena do stále seřazené struktury blackConnections typu TConnections. Existuje-li již v blackConnections spojení mezi zdmi sousedícími s aktuálně vyhodnocovanou buňkou cesty, je tato buňka přidána do pole connectors (viz níže); v opačném případě je vytvořen nový záznam typu TConnection v poli blackConnections. Každý takový záznam obsahuje dynamické pole vlastníků - owners (tedy indexů buněk obsahujících číslo potenciálně spojovaných zdí), dynamické pole spojovacích článků - connectors (tedy indexů buněk cest ležících mezi potenciálně spojovanými zdmi) a dvě proměnné popisující počet vlastníků (ownersLength) a celkovou plochu potenciální zdi, vzniklé spojením zdí přes libovolnou buňku z pole connectors. Jakmile metoda prozkoumá všechny buňky cest a nalezne všechna možná spojení, jsou z jednotlivých polí connectors všech záznamů v blackConnections odstraněny všechny párové buňky (dvě či více buněk cest, které se vždy alespoň jedna
27
s druhou navzájem dotýkají hranami a spojují dvě zdi – byly-li by zdi spojeny přes jednu z takových buněk, existovaly by alespoň dvě symetrické konfigurace nově vzniklé, sjednocené, zdi) a buňky, jejichž odebráním by v Nurikabe vznikly dvě nespojitelné cesty (metoda blackSkipper). Jsou-li z některého záznamu v blackConnections odebrány všechny indexy z pole connectors, tento záznam zaniká. Po této úpravě jsou mezi záznamy blackConnections vybrány ty s nejmenším počtem slučovaných zní a nejmenší plochou nové potenciální zdi, které jsou náhodným výběrem jeden po druhém testovány tak dlouho, než se metodě tryFillNumbers podaří do nově vytvořené zdi (přes jedno z možných spojení daného blackConnection) umístit její plochu. Taková nově vznikla zeď je zařazena (pomocí indexu jejího čísla) do pole forbiddenIndexes a již nebude použita ke slučování. Pokud by byla nová zeď použita pro další slučování, hrozilo by, že se metoda pokusí vytvořit jedinou velkou zeď mezi několika zdmi plochy 1. Těmito omezeními vznikají, za předpokladu použití i následující metody, zdi plochy 2 – 9, které jsou pro aplikací generované rozměry rébusu Nurikabe ideální. Pro dokončení Nurikabe je vhodné použít metodu, nazvanou „natahování konečků“. Cílem metody je nalezení všech buněk cest, které sousedí právě s jednou zdí a zkusit z takových cest udělat výklenky této zdi. Většina potenciálních výklenků se nachází na krajích čtvercové sítě a rozpojují kružnici na cestě. Všechny potenciální buňky jsou postupně připojeny jako výklenek nejbližší zdi a testovány metodou tryFillNumbers. Je-li testování úspěšné, výklenek zůstává; v opačném případě se stává opět cestou.
3.3.2 SUDOKU Třída TSudokuSquare je potomkem třídy TSquares obsahujícím navíc index polohy v rámci menšího čtverce. Tento index je pro každou buňku spočítán spolu s jejím řádkem a sloupcem (index menšího čtverce pro danou buňku je číslo jejího řádku celočíselně vydělené a poté opět vynásobené základním číslem, zvětšené o celočíselný dělenec sloupce buňky). Pro algoritmy jednotky Sudoku je důležitá třída TAvailables. Třída obsahuje dynamické pole pravdivostních hodnot zadaného rozsahu. Hlavními metodami pracujícími se třídou TAvailables jsou countAvailables (vrací počet hodnot pole nastavených na True), getRandomFromAvailables (vrací index náhodného prvku pole, uvnitř instance třídy TAvailable, jehož hodnota je True), makeAllAvailable a makeAllUnavailable (nastavení všechny hodnoty v poli na True, resp. False). Nejčastěji je v Sudoku třída použita jako paměť pro hodnoty buňky, které je do ní možno vepsat. O řešení Sudoku se stará následník TGameThread, třída TSudokuSolveThread, která obsahuje v metodě execute dvě důležité proměnné – anyCeiling, pravdivostní hodnotu, vyjadřující existenci nějakého stropu možností (viz níže) a ceiling, celočíselnou hodnotu, vyjadřující aktuální strop možností. Hodnota ceiling odpovídá nejnižšímu nenulovému počtu dostupných hodnot mezi všemi buňkami sítě. Je-li hodnota stropu rovna 1 a anyCeiling má
28
hodnotu True, pak musí v Sudoku existovat alespoň jedna prázdná buňka, která má v poli možných hodnot TAvailables právě jednoho číslo. Řešící algoritmus nejprve nastaví hodnotu anyCeiling na False a ceiling na 1. Následně prohledá všechny buňky Sudoku, aby zjistil, zda mezi nimi existuje buňka, do které lze doplnit právě jedno číslo. Pokud ano, nastaví hodnotu anyCeiling na True, doplní číslo do buňky, přepočítá availables pro řádek, sloupec a menší čtverec ve kterém se buňka nachází a postup opakuje. Pokud nenalezne žádnou, resp. žádnou další, buňku s jedinou možností doplnění a sudoku není stále vyřešené, zvýší hodnotu proměnné ceiling o jedna. Nalezne-li buňku s více než jednou možností doplnění, dochází k větvení algoritmu. Do jednotlivých nových vláken je zkopírován současný stav čtvercové sítě doplněný o druhou, resp. každou další možnost pro buňku s počtem Availables větším než 1. První hodnota je použita v aktuální větvi. Objeví-li se buňka, jež je prázdná a zároveň neobsahuje žádné možnosti doplnění, větev končí neúspěchem. Pokud je hodnota anyCeiling false a bylo dosaženo nejvyššího čísla ve hře (druhé mocniny základního čísla), větev končí neúspěchem. Neobsahuje-li hra žádné volné pole, je zkontrolována na korektnost. Pokud se jedná o korektní Sudoku, větev končí úspěšně. Ačkoli se jedná o velmi jednoduchou heuristiku řešení Sudoku, je efektivní. Pro člověka by takovéto řešení bylo příliš zdlouhavé, dnešní počítače však díky možnostem paralelního zpracování vyřeší většinu Sudoku v řádu sekund. Proto bylo od implementace pokročilejších heuristik upuštěno. Třída generujících vláken TSudokuGenerateThread je potomkem TGamePossitionThread. Její nejdůležitější proměnnou je RemovedItems typu TRemovedItems a s ní související metody pStepForward a pStepBackward (viz níže). Metoda execute nejprve vygeneruje kompletní mřížku: Všechny hodnoty čtvercové sítě nastaví na SQ_NIL. Poté postupuje od levého horního rohu. Metoda vybere náhodně jeden prvek z TAvailables a nastavením jeho hodnoty na False jej odstraní z možných hodnot pro první buňku. V každé následující buňce navíc testuje, zda vložením čísla nedošlo k porušení některého z pravidel Sudoku, pokud ano je kandidát vyřazen z možných hodnot buňky a metoda vkládá jinou možnou hodnotu. Neexistuje-li další možná hodnota pro prázdnou buňku, jsou všechny hodnoty v proměnné Availables této buňkou nastaveny na True. Algoritmus se vrátí o buňku zpět, v její proměnné Availables je aktuální kandidát nastaven na False a z možných hodnot buňky je vybrán kandidát jiný a metoda opět postupuje na další buňku. Pokud pro buňku neexistují žádné možné hodnoty, algoritmus se vrátí o další buňku zpět. Tato metoda je efektivní pro generování čtvercové sítě do velikosti 9x9. U větších sítí by tento algoritmus strávil generováním příliš mnoho času. Čtvercová síť vygenerovaná výše popsaným postupem je vyřešené Sudoku. Z ní generující algoritmus odstraní některá pole tak, aby bylo Sudoku netriviální, ale mělo stále právě jedno řešení. Zatímco v předešlé části algoritmu měla struktura TAvailables roli úložiště možných kandidátů v rámci jednotlivých buněk, nyní se její úloha mění a každá její hodnota odpovídá jedné buňce čtvercové sítě. Je-li ve struktuře pro některou buňku uložena hodnota True, může se algoritmus pokusit buňku odebrat; je-li False, buňku odebrat nelze.
29
Otázka počtu odebíraných buněk je řešena parametrem Level (zděděným od TGame) v každé instanci TSudoku. Metoda odstraňuje středově souměrné páry buněk tak dlouho, než dosáhne počet odstraněných buněk hodnoty Level nebo než označí všechny neodstraněné hodnoty za neodstranitelné. Level tedy tvoří horní mez počtu odebraných buněk. Obecně se dá říci, že metoda generuje lehčí varianty Sudoku. K odstranění buněk a eventuálnímu zpětnému sledování kroků algoritmu slouží třída TRemovedIndexes. Třída obsahuje pole o velikosti poloviny hodnoty Level generované hry, která nesou indexy a hodnoty odebíraných polí. O kroky zpět se stará procedura pStepBackward vlákna TSudokuGenerateThread, kroky vpřed realizuje metoda pStepForward. Metoda pStepForward nejprve zkontroluje, zda lze ještě nějaké buňky odebrat, není-li to možné, dělá kroky zpět (pStepBackwards), dokud se čtvercová síť nenachází ve stavu, z něhož je možné odebírat další buňky. Jakmile existují odebratelné buňky, je nalezen menší čtverec s co nejvyšším počtem ještě neodebraných buněk. Pokud nejsou v takovém čtverci žádné odebratelné buňky, vybere metoda náhodně jednu buňku ze všech, jejichž hodnota v TAvailables je True – jsou tedy odebratelné. K takto vybrané buňce je spočten její středově souměrný obraz a obě buňky jsou označeny za kandidáty. Kandidáti i jejich hodnoty jsou uloženy uvnitř struktury TRemovedIndexes a odebrány z čtvercové sítě Sudoku. Následuje test na unikátnost, jehož výsledek vede buď k návratu kandidátů do Sudoku nebo ke kroku metody odstraňování čtverců vpřed.
3.3.3 INTERFACE A PROPOJENÍ VLÁKEN S UŽIVATELSKÝM ROZHRANÍM Pro generující vlákno je typické, že se vyskytuje pouze v jediné instanci, proto pracuje přímo s instancí následníka TGame. Způsob implementace metody GenerateNew je obdobný jako u metody Solve (viz níže). Řešících vláken je většinou více, neboť všechny metody řešení umožňují větvení. Každé řešící vlákno si proto nese kopie, resp. klon, instance následníka TGame. Metoda Solve sestává z inicializační části, ve které jsou smazána všechna dříve nalezená řešení a je vytvořen potomek třídy TThreadController s prvním řešícím vláknem (každé vlákno má pro událost OnSuccess a OnFailure nastaveny vnitřní metody potomka třídy TGame, které se starají o uložení zjištěných řešení do pole Solutions a pro událost OnIteration vnější metodu přiřazenou uživatelským rozhraním při inicializaci potomka třídy TGame). Poté je spuštěna nekonečná smyčka, kterou ve většině případů ukončuje manažer vláken (instance třídy TGameThreadController). Následuje zkoumání nalezených řešení. Pokud je vlastnost hry SolveOneStepOnly nastavena na True, může se v poli Solutions vyskytnout i hra, která neporušuje pravidla rébusu, ale není zcela vyřešena. Podle počtu nalezených řešení metoda Solve vrací hodnotu typu TSolutionID (sidNone nenalezla-li žádné řešení, sidOne existuje-li právě jedno řešení a sidMore, pokud nalezla více řešení – ta jsou v uživatelském rozhraní dostupná přes parametr Solutions hry). Jako potomek třídy TGamePossitionThread obsahují jak řešící tak generující vlákno událost OnIteration s parametry Sender typu TObject, vstupně-výstupní pravdivostní hodnotou contiue, messageID typu TMessageID (TMessageID nabývá hodnot msPreparing pro
30
zobrazení zprávy o inicializaci operace, msGenerating pro zobrazení zprávy o generování rébusu, msSolving pro řešení rébusu a msCanceling pro rušení probíhající úlohy) a pravdivostní hodnotou gridChanged informující o nutnosti překreslit uživateli zobrazovanou čtvercovou síť. V metodě execute vlákna je OnIteration voláno v každé iteraci cyklu, která má vliv na stav herní sítě nebo v místě, kde může dojít k více cyklům, které by uživatel mohl vnímat jako zamrznutí aplikace. Je-li hodnota continue nastavena na False, jsou všechny cykly, v heuristikách nebo přímo v těle hlavního cyklu metody execute, přerušeny a vlákno se ukončuje. Protože doIterate volají všechna vlákna, musí být hodnota continue stanovena nezávisle na čase, ve kterém k ní jednotlivá vlákna přistupují. O událost OnIterate jednotlivých vláken se v uživatelském rozhraní starají metody GameSolveIteration a GameGenerateIteration. Uživatelské přerušení je v obou metodách řešeno obdobně: Je-li hodnota modalResult dialogu jednotky ProgressWindow rovna mrCancel (hodnotu nastaví uživatel kliknutím na tlačítko Zrušit nebo stiskem klávesy Escape), continue je v iterační metodě nastaveno na False, mřížka se neobnovuje a hodnota continue je tudíž okamžitě předána zpět vláknu, aby se mohlo ukončit. Metody také překládají parametr události messageID na text a tento zobrazují ve výše zmíněném ProgressWindow uživateli. Úkolem metod je starat se o interakci uživatele a vláken, řeší tedy i pozastavení algoritmů. Klikne-li uživatel na tlačítko Pozastavit nebo stiskne klávesu Enter, první vlákno, ve kterém nastane událost OnIterate (a tedy je spuštěna metoda GameSolveIteration nebo GameGenerateIteration) volá metodu suspend svého správce vláken. Ten volá metodu suspend na všech vláknech, jichž je správce. Dále je v události OnIterate spuštěna nekonečná smyčka, jež čeká na další interakci uživatele. Jak mile uživatel klikne na tlačítko Pokračovat nebo opět stiskne klávesu Enter, je smyčka ukončena, správce vláken přes metodu resume obnovuje činnost jednotlivých spravovaných vláken (v závislosti na počtu jader procesoru obnoví posledních n vláken, kde n je počet jader procesoru) a metoda vyvolaná událostí OnIterate vlákna je dokončena. Nemůže dojít ke kolizi, protože před pozastavením bylo spuštěno pouze n vláken, z nich jedno nepochybně vyvolalo událost suspend pro všechna ostatní vlákna. Během čekání na uživatele se pořadí ani počet uspaných vláken nemohl změnit a tudíž i vlákno, které ostatní uspalo, bude po probuzení aktivní (resp. bude mezi probuzenými vlákny). Díky parametru Solutions následníka třídy TGame pro každý rébus, má uživatelské rozhraní přístup ke všem nalezeným řešením a snadnou výměnou obsahu proměnné theGame (typu TGame) v jednotce MainWindow může uživateli zprostředkovat všechna řešení, která algoritmy nalezly. Jedná-li se o výběr z možností při nápovědě, nestačí však pouze tato struktura. Všechna vlákna mají parametr Indexes, který obsahuje index právě zpracovávané buňky či buněk. Za normálních okolností vkládají řešící algoritmy do tohoto parametru zpracovávané buňky. Mají-li vyřešit pouze jeden krok hry, ve kterém je více možností, musí nějakým způsobem odlišit indexy buněk jednoho možného postupu od ostatních. Pokud se nejedná o stav nápovědy, vypadá parametr Indexes, jako běžné dynamické pole obsahující alespoň jeden index (případně hodnotu SQ_NIL při inicializaci nebo ukončení
31
vlákna). Ve stavu nápovědy však musí mít pole definovaný formát, aby z něj bylo možné přečíst jednotlivé varianty dalšího postupu. V takovém Obrázek 3.12 případě je první, třetí a poslední prvek pole indexes vždy nastaven na hodnotu SQ_NIL. Druhý prvek může nabývat libovolných hodnot od 0 do SQ_NIL (standardně je SQ_NIL rovno poslední celočíselné hodnotě Word, tedy 65535 (FFFF)). Hodnota SQ_NIL také slouží jako oddělovač mezi jednotlivými možnostmi. Pro Nurikabe je ve druhém prvku pole indexes buď hodnota SQ_NIL značící, že jednotlivé dále uvedené možnosti jsou konfigurace cest (Obrázek 3.12 – nahoře), nebo 0 značící, že se jedná o jednotlivé konfigurace zdí (Obrázek 3.12 - dole). Pro Sudoku má druhý prvek pole indexes jiný význam: Je-li roven SQ_NIL jsou v poli uvedeny dvojice index buňky, hodnota buňky. Dvojice jsou navzájem odděleny opět SQ_NIL (Obrázek 3.13 – nahoře). Pokud je druhý prvek pole indexes různý od SQ_NIL, jedná se o index buňky. Sekvence čísel mezi třetím a posledním prvkem v poli (oba zmiňované prvky mají hodnotu SQ_NIL) jsou čísla, kterých může buňka definovaná indexem v druhém prvku pole indexes nabývat (Obrázek 3.13 – dole). Informace z pole jsou Obrázek 3.13 převedeny do jednotky PossibilitiesWindow, která je uživateli prezentována formou dialogu, v němž může jednotlivé možnosti zobrazit a jednu z nich vybrat.
3.4
UŽIVATELSKÉ ROZHRANÍ
Cílem je vytvořit ze standardních komponent prostředí, které by si uživatel mohl maximálně přizpůsobit a které by funkčně vyhovovalo účelu, za kterým je vytvořeno. Uživatelé oceňují globální funkce programu pouze v základních rysech. Pokud například používají textový editor, považují za samozřejmé, že do něj lze psát a že umí formátovat písmo. Nezakládají si ani tak na počtu základních funkcí, jako spíše na drobnostech a jejich realizaci. Všechny základní funkce jsou uživateli poskytnuty co nejpřístupnější formou a zároveň zachovávají ovladatelnost aplikace jak myší, tak klávesnicí. Uživatel by měl aplikaci považovat za intuitivní a zároveň by měl na první pohled najít každou funkci, na kterou si vzpomene. Neměl by však být zahlcen funkcemi. Uživatel má v hracím módu po pravé straně dostupná tlačítka základních funkcí – restartovat hru, vyřešit hru, napovědět a exportovat hru. Také vidí svůj čas, časy ostatních hráčů a her – mezi nimi je pozice současné hry zvýrazněna. V editačním módu obsahuje pravý panel tlačítka pro importování, vymazání, restartování, vyřešení a exportování. Potřebuje-li uživatel využít dalších funkcí, vybere je z hlavního menu. Aplikace neobsahuje nástrojovou lištu, neboť jejím vložením by došlo ke zmenšení prostoru pro čtvercovou hrací síť i ovládací prvky obou módů, zároveň
32
by lišta obsahovala tlačítka funkcí, které se buď vyskytují v hlavním menu přímo nad lištou, nebo v pravém panelu. Hlavní menu je rozděleno do čtyř částí: Hra, Aktuální hra, Nástroje a Nápověda. Menu Hra obsahuje funkce pro práci s Nurikabe a Sudoku, nezávislé na aktuální hře (vygenerování nového zadání, import, atd.). Aby nemusel uživatel vždy zadávat parametry nové hry, obsahuje menu i funkce Rychlé Sudoku a Rychlé Nurikabe, které vygenerují novou hru dle posledních zadaných parametrů. Menu Aktuální hra obsahuje funkce související s právě hranou hrou – jako Vyřešit celou hru, Pauza, Nápověda (ve smyslu dalšího kroku řešení), Vidlička nebo Export. Menu Nástroje obsahuje přepínače, které uživatel může při běžném používání aplikace potřebovat, dialog jednotky StatisticsWindow zobrazující statistické informace o hráčích a hrách a dialog jednotky OptionsWindow sloužící k podrobnému nastavení uživatelského rozhraní včetně lokace souborů nastavení, barev, písem, časovačů blikání napovězené buňky (resp. buněk) apod. Každá z herních funkcí má přiřazenu klávesovou zkratku tak, aby bylo možné hru ovládat bez použití myši – při řešení rébusu na čas, je myš výrazně pomalejším nástrojem než klávesnice. Způsob ovládání mřížky (TGraphicGrid – čtvercové sítě) vychází z ovládání programů běžně dostupných uživateli. Pro Nurikabe je typ buňky změněn na cestu kliknutím na levé tlačítko myši nebo scrollováním nahoru. Dvojklikem, pravým kliknutím nebo scrollováním dolů se typ buňky změní na hvězdičku. Na klávesnici se stiskem mezerníku nebo klávesy W změní buňka na zeď, stiskem SHIFT + mezerník nebo klávesy S se změní na hvězdičku. Pro Sudoku lze čísla měnit scrollováním nahoru a dolů nebo je lze zadat na numerické či alfanumerické klávesnici, respektive je vybrat klávesami W a S (zadáním čísla 0 odstraní uživatel hodnotu z buňky). Daní za počítání chyb je nutnost potvrdit hodnotu, resp. typ, buňky. K potvrzení dojde stiskem klávesy ENTER nebo stiskem klávesy pro přechod do jiné buňky. Je-li k řešení Nurikabe použita myš, každá změna typu buňky je zároveň považována za potvrzení. Nutnost potvrzovat vychází z předpokladu, že dokud je kurzor na jedné konkrétní buňce, může hráč vybírat hodnotu nebo typ buňky pomyslným rotováním možností, aniž by chtěl zadat nesprávnou hodnotu či typ – takový postup by neměl být považován za chybu, proto výběr hodnoty nebo typu buňky končí až opuštěním buňky nebo stiskem klávesy Enter. Jediný rozdíl, plynoucí z toho přístupu pro uživatele, je v konečném důsledku ten, že na konci hry – po vyplnění posledního čísla Sudoku nebo poslední buňky cesty Nurikabe, musí stisknout Enter nebo přejít do jiné buňky.
3.4.1 IMPORT, EXPORT Aplikace podporuje import a export do a ze souborů csv (comma-separated values – hodnoty oddělené čárkami (pro kompatibilitu s kancelářskými aplikacemi MS Office Excel a OpenOffice Calc je jako při oddělovač při exportu použit místo čárky středník)). K odlišení her je použito dvou odlišných zápisů. Každá hra je v souboru reprezentována dvojnásobným počtem sloupců, než kolik jich je v její čtvercové síti. Každému sloupci herní sítě tedy odpovídá dvojice sloupců v souboru. Jeden ze sloupců obsahuje typ buňky a dru-
33
hý její hodnotu. Hodnoty jsou reprezentovány čísly většími než 0, buňka bez hodnoty je prezentování buď absencí znaku, nebo 0. Pro Sudoku je hodnota uložena v prvním sloupci a typ buňky ve druhém. Typy buněk Sudoku jsou značeny písmeny O (originální hodnota, součást zadání) a U (uživatelská hodnota, původně volné pole zadání). Nurikabe má naopak v prvním sloupci typ buňky a ve druhém její hodnotu. Typy buněk Nurikabe jsou označeny písmeny B (block - zeď), P (path - cesta) a M (mark – hvězdička). Aby bylo pořadí uvnitř dvojice sloupců intuitivní, je zvoleno dle důležitosti v jednotlivých rébusech – pro Sudoku jsou hlavní čísla, pro Nurikabe typy buněk. Snahou je usnadnit tímto uživateli tvorbu souborů csv. Na základě formátu importovaného souboru se aplikace rozhodne, o který rébus se jedná. Při importu kontroluje, zda je soubor kompletní a korektně vytvořený. Pokud ne, není soubor importován. Následujícím krokem je kontrola importované hry – není-li hra vyřešená, může uživatel přímo pokračovat v jejím řešení, v opačném případě jej aplikace o importování vyřešené hry informuje. Importní funkci nalezne uživatel v menu Hra, importováním hry je aktuální hra přepsána (běží-li časomíra, je uživatel nejprve dotázán na přerušení hry). Exportní funkce je v menu Aktuální hra a lze použít pouze na aktivní hru. Uživatel si tak může rozřešený rébus uložit a znovu načíst. Neobnovuje se však časomíra, protože čas potřebný na vyřešení hry by měl být spojitý.
3.4.2 VKLÁDÁNÍ RÉBUSŮ, RUČNÍ GENEROVÁNÍ A ÚPRAVA, ŘEŠITEL Menu Hra obsahuje funkce Vložit Sudoku a Vložit Nurikabe. Po zvolení jedné z těchto funkcí, se aplikace dotáže na velikost mřížky, kterou následně nabídne uživateli k vyplnění v editačním módu. Uživatel může opsat zadání například z Internetového serveru nebo knihy a uložit si jej na později, otestovat jednoznačnost řešení zadání nebo nechat aplikaci aby mu s řešením pomohla. Mód úprav neslouží jen k zadávání existujících zadání. Uživatel má možnost vytvořit si za asistence počítače zadání vlastní. Při generování nového rébusu zvolí místo obtížnosti úplnou cestu (pro Nurikabe), resp. úplnou mřížku (pro Sudoku) a zatrhne políčko ponechat vyřešené. Aplikace vygeneruje novou čtvercovou síť, avšak neaplikuje na ni žádné heuristiky. Vstoupí-li uživatel do editačního módu, má možnost ručně postavit zdi Nurikabe a vytvořit mezi nimi cestu nebo vybrat buňky Sudoku, které mají být skryty. Průběžně může uživatel testovat, zda je jeho rébus jedinečný za využití výpočetních možností počítače. Editační mód hledá, na rozdíl od herního, všechna řešení pro zadanou mřížku a uživatel jimi může procházet a na základě rozdílů či schod upravovat zadání tak, aby měl jeho rébus pouze jedno řešení. Níže popsaná funkce Vidlička je uživateli dostupná i v editačním módu a může se tedy vrátit k libovolné, jím uložené, konfiguraci čtvercové sítě. Pro usnadnění řešení nabízí aplikace funkce řešitele. Jednou jeho částí je funkce Vidlička. Kdykoli může uživatel uložit aktuální stav čtvercové sítě a například metodou pokus omyl zvolit směr řešení, kterým si není jistý. Pokud se směr ukáže jako špatný, může
34
se uživatel vrátit zpět k bodu, ve kterém se rozhodl a vydat se jiným směrem. Vidliček si může uživatel k jedné hře vytvořit až sto. Pokud dosáhne tohoto počtu vidliček, bude zachována první vidlička a vidličky nejmladší. Druhou částí řešitele je funkce nápověda. Aplikace provede jeden krok řešícího algoritmu a zvýrazní uživateli, jaké změny provedla. Pokud je hra vyřešitelná pouze základními heuristikami, lze nápovědami vytvořit ze zadání řešení. Hry vyžadující za normálních okolností větvení nabídnou uživateli všechny větve a ten si musí jednu vybrat. Aplikace zde automaticky vytvoří vidličku, takže zvolí-li uživatel alternativu, která nevede k řešení rébusu, může se vrátit do stavu těsně před volbou a pomocí nápovědy vybrat jiné z nabízených řešení. Třetí část řešitele zprostředkovává přepínač Zobrazovat chybné buňky v menu Nastavení. Je-li tento přepínač aktivní, jsou buňky v rozporu s pravidly rébusu zobrazeny inverzními barvami. Hráči je tím usnadněno nalezení chybné konfigurace zdí či nalezení pokoje na cestě při řešení rébusu Nurikabe nebo násobného výskytu čísla v rébusu Sudoku.
3.4.3 STATISTIKY Řeší-li rébusy více různých hráčů, mohou své výsledky porovnávat pomocí nástroje Kompletní statistika. Je-li funkce měření hry povolena, o každé měřené hře jsou uloženy základní údaje jako datum nebo rozměry čtvercové sítě. Jedná-li se o hru vygenerovanou aplikací, je uložena i obtížnost s jakou nechal uživatel hru vygenerovat (netýká se importovaných nebo ručně zadaných her). Navíc jsou uloženy informace o hře – čas, který uživatel strávil řešením rébusu, počet chyb, kterých se dopustil, kolik nápověd využil apod. Aplikace umožňuje grafické znázornění jednotlivých atributů her odehraných jednotlivými hráči. Lze zobrazit také tabulkovou statistiku nebo porovnat údaje o jednotlivých hráčích (počet odehraných her, samostatnost, atd.).
35
4
ZÁVĚR
V práci byly popsány běžně používané heuristiky pro řešení rébusů Sudoku a Nurikabe. V první části byla provedena analýza teoretických možností generování a řešení uvedených rébusů. Byly také popsány jednotlivé lidmi používané metody jejich řešení a možné implementace těchto metod. Práce také definuje stupně obtížnosti a heuristiky pro generování rébusu Nurikabe a zefektivňuje některé heuristiky používané pro řešení rébusu. Ve druhé části práce jsou popsány implementace heuristik a funkce aplikace, která byla v rámci práce vytvořena. Aplikace generuje a řeší rébusy Sudoku a Nurikabe. Poskytuje uživateli prostředky pro řešení rébusů, jejich vlastní tvorbu a import a export rébusů do obecného formátu hodnot oddělených čárkami. Dále aplikace nabízí možnost porovnání výsledků různých hráčů, měří jim čas a nabízí statistiku využití nápověd, úspěšnosti hráče apod. Uživatel může také zobrazit buňky, které jsou v rozporu s pravidly zvoleného rébusu.
37
5
LITERATURA
1. Wikipedia contributors. Nurikabe. Wikipedia, The Free Encyclopedia. [Online] [Citace: 17. 12. 2010.] http://en.wikipedia.org/wiki/Nurikabe. 2. —. Nurikabe (folklore). Wikipedia, The Free Encyclopedia. [Online] [Citace: 17. 12. 2010.] http://en.wikipedia.org/wiki/Nurikabe_(folklore). 3. Dent, Francesca. Japanese folklore: Legend of the Nurikabe. Helium. [Online] [Citace: 17. 12 2010.] http://bluemoa.wordpress.com/2007/08/07/nurikabe-a-japanese-spirit/. 4. Sudoku Dragon. What is Sudoku? Sudoku Dragon. [Online] [Citace: 17. 12. 2010.] http://www.sudokudragon.com/sudoku.htm. 5. —. Sudoku Origins. Sudoku Dragon. [Online] [Citace: 17. 12. 2010.] http://www.sudokudragon.com/sudokuorigins.htm. 6. Astraware Limited. About Sudoku. Sudoku Of The Day. [Online] [Citace: 17. 12. 2010.] http://www.sudokuoftheday.com/pages/about.php. 7. Ballew, Pat. Magic Squares. pballew. [Online] [Citace: 17. 12. 2010.] http://www.pballew.net/magsquar.html. 8. Přispěvatelé Wikipedie. Leonhard Euler. Wikipedie: Otevřená encyklopedie. [Online] [Citace: 17. 12. 2010.] http://cs.wikipedia.org/wiki/Leonhard_Euler. 9. Bogomolny, Alexander. Two Simple Problems with Latin Squares. Interactive Mathematics Miscellany and Puzzles. [Online] [Citace: 17. 12. 2010.] http://www.cut-theknot.org/arithmetic/latin.shtml. 10. Lars. Nurikabe - Generating and Auto-solving. Lars and Kathy's home page. [Online] [Citace: 17. 12. 2010.] http://www.huttar.net/lars-kathy/puzzles/nurikabe.html. 11. NIKOLI Co., Ltd. Nurikabe. Nikoli Puzzle Guide. [Online] [Citace: 17. 12. 2010.] http://www.nikoli.co.jp/en/puzzles/nurikabe/. 12. Sudokupedia contributors. Scramble. Sudopedia, the free Sudoku. [Online] [Citace: 17. 12. 2010.] http://www.sudopedia.org/wiki/Scramble. 13. —. X-Wing. Sudopedia, the free Sudoku. [Online] [Citace: 17. 12. 2010.] http://www.sudopedia.org/wiki/X-Wing. 14. Pramberg, Jörgen. Sudoku Solver and Generator. The Code Project. [Online] 3. 8. 2010. [Citace: 17. 12. 2010.] http://www.codeproject.com/KB/game/sudoku.aspx. 15. Gold, Mike. Using Genetic Algorithms to come up with Sudoku Puzzles. C# Corner. [Online] 23. 9 2005. [Citace: 17. 12. 2010.] http://www.csharpcorner.com/UploadFile/mgold/Sudoku09232005003323AM/Sudoku.aspx.
39
16. Wikipedia contributors. Sudoku algorithms. Wikipedia, The Free Encyclopedia. [Online] [Citace: 17. 12. 2010.] http://en.wikipedia.org/wiki/Sudoku_algorithms#Solving_Sudokus_via_stochastic_search _.2F_optimization_methods. 17. Sudoku Dragon. Sudoku Strategy. Sudoku Dragon. [Online] http://www.sudokudragon.com/sudokustrategy.htm. 18. —. Advanced Sudoku Strategy. Sudoku Dragon. [Online] [Citace: 17. 12. 2010.] http://www.sudokudragon.com/advancedstrategy.htm. 19. Chu, Jonathan. A Sudoku Solver in Java implementing Knuth’s Dancing Links Algorithm. University of California, Berkeley (OCF). [Online] 20. 4 2006. [Citace: 17. 12 2010.] http://www.ocf.berkeley.edu/~jchu/publicportal/sudoku/sudoku.paper.html. 20. Wikipedia contributors. Exact cover. Wikipedia, The Free Encyclopedia. [Online] [Citace: 17. 12. 2010.] http://en.wikipedia.org/wiki/Exact_cover. 21. —. Knuth's Algorithm X. Wikipedia, The Free Encyclopedia. [Online] [Citace: 17. 12. 2010.] http://en.wikipedia.org/wiki/Knuth's_Algorithm_X. 22. Gwerdy Software. SuDoku Solver. Gwerdy Software. [Online] [Citace: 17. 12. 2010.] http://www.gwerdy.com/products/sudoku_solver/. 23. Sudoku Dragon. Sudoku Puzze Solver. Sudoku Dragon. [Online] [Citace: 17. 12. 2010.] http://www.sudokudragon.com/dragonfeatures.htm. 24. Nurikabe. Головоломные программы. [Online] [Citace: 17. 12. 2010.] http://www.puzzleprograms.narod.ru/Puzels/Nurikabe/. 25. Wikipedia contributors. Taxicab geometry. Wikipedia, The Free Encyclopedia. [Online] [Citace: 17. 12. 2010.] http://en.wikipedia.org/wiki/Taxicab_geometry. 26. Teixera, Steve a Pacheco, Xavier. Borland Delphi: Průvodce vývojáře. [překl.] Vladimír Bodeček a Petr Macháček. Brno : UNIS publishing, 1998. str. 288. ISBN 80-8609736-6. 27. Swan, Tom. Mistrovství v Delphi 4: kompletní průvodce pro tvorbu. Brno : Computer Press, 1999. ISBN 80-7226-173-8. 28. Win 32 API - průvodce vývojáře: kompletní reference programátora pro Windows 95 a Windows NT. Brno : UNIS publishing, 1997. ISBN 80-86097-06-4. 29. Johnson, Peter. Version Information Component. DelphiDabbler. [Online] 3. 11 2010. [Citace: 17. 12. 2010.] http://www.delphidabbler.com/software/verinfo/main. 30. milley. Show baloon hint in delphi. CodeSnippets. [Online] 27. 6. 2008. [Citace: 17. 12. 2010.] http://codesnippets.joyent.com/posts/show/1545.
40
