Řešení Malovaných křížovek

České vysoké učení technické v Praze Fakulta elektrotechnická Katedra počítačů

Bakalářská práce

Řešení „Malovaných křížovek“ Filip Krejčí

Vedoucí práce: Šimeček Ivan Ing., Ph.D.

Studijní program: Softwarové technologie a management Obor: Softwarové inženýrství 10. června 2009

iv

Poděkování Chtěl bych poděkovat mamče za gramatickou korekturu textu a taťkovi za přepisování Griddlerů. v

vi

Prohlášení Prohlašuji, že jsem práci vypracoval samostatně a použil jsem pouze podklady uvedené v přiloženém seznamu. Nemám závažný důvod proti užití tohoto školního díla ve smyslu §60 Zákona č. 121/2000 Sb., o právu autorském, o právech souvisejících s právem autorským a o změně některých zákonů (autorský zákon).

V Praze dne 10.6.2009 ………………………………………………………………….…. vii

viii

Abstract Solving of Griddlers consist in founding hidden image using the legend, determining the number of continuous fields of same color in particular row and column. There are two types of Griddlers: two-colored and multicolored. Griddler can contain fields, consisting of two colors. I have programmed an application that allows Griddlers to create, to modify and to solve. Its user interface provides the user of many features sweetening his work, for example highlights the selected row and column, on user reqest zooms in or out the Griddler, or returns the steps of user solving process. Important part of the application is an solving algorithm. After run, the algorithm tries to solve the Griddler. The algorithm implements some methods commonly used in solving of Griddlers, such as the method of overlapping counting, and introduces a new idea to solve Griddlers using regular expressions, which is very powerful tool.

Abstrakt Řešení Malované křížovky spočívá v nalezení skrytého obrázku za pomocí legendy, určující počet souvislých políček dané barvy v konkrétním řádku a sloupci. Křížovky mohou být dvoubarevné nebo vícebarevné a mohou obsahovat i políčka složená ze dvou barev. Naprogramoval jsem aplikaci, která umožňuje křížovky vytvářet, upravovat a řešit. Její uživatelské rozhraní poskytuje uživateli množství funkcí, zpříjemňující mu jeho činnost, např. zvýrazňuje vybraný řádek a sloupec, na požádání zvětší nebo zmenší měřítko křížovky, nebo vrátí jednotlivé kroky řešení. Součástí programu je řešící algoritmus, který se po spuštění pokusí danou křížovku vyřešit. Algoritmus implementuje některé metody, běžně používané při řešení křížovek, jako je například metoda překrývajícího se počítání a přináší novou myšlenku řešit křížovky pomocí regulárních výrazů, což se ukázalo jako velmi silná zbraň.

ix

x

Obsah 1 Úvod ................................................................................................................................ 1 2 Problém malovaných křížovek...................................................................................... 3 2.1 Dělení křížovek......................................................................................................... 3 2.2 Cíl a struktura této práce........................................................................................... 4 2.3 Jiné aplikace umožňující řešení Griddlerů................................................................ 5 3 Výběr implementačního prostředí................................................................................ 7 4 Realizace programu ....................................................................................................... 9 4.1. Slovníček pojmů ...................................................................................................... 9 4.2 Zkratky.................................................................................................................... 11 4.3 Formát souboru s křížovkou ................................................................................... 11 4.4 Konfigurační soubor ............................................................................................... 13 4.4.1 Struktura konfiguračního souboru................................................................... 13 4.4.2 Config Reader...................................................................................................... 14 4.5 Struktura programu, okno aplikace......................................................................... 14 4.5.1 Nabídka aplikace ............................................................................................. 15 4.5.1.1 Menu Griddler.......................................................................................... 15 4.5.1.2 Menu Vzhled............................................................................................ 17 4.5.1.3 Menu Upravit ........................................................................................... 17 4.5.1.4 Menu Editor ............................................................................................. 17 4.5.1.5 Menu Nápověda ....................................................................................... 18 4.5.2 Řešení křížovek ............................................................................................... 18 4.5.3 Ovládání a funkce editoru ............................................................................... 21 5 Techniky řešení křížovek............................................................................................. 27 5.1 Vyplnění jednoznačných oblastí v křížovce ........................................................... 27 5.2 Vyplnění jednoznačně určených řádků................................................................... 28 5.3 Vyplnění částečně určených řádků ......................................................................... 28 5.4 Doplnění vyřešeného řádku prázdnými políčky ..................................................... 29 5.5 Doplnění částečně vyřešeného řádku políčky pozadí ............................................. 30 5.6 Doplnění dalších barevných políček do částečně vyřešeného řádku ...................... 31 5.7 Řešení pomocí legendy více řádků najednou ......................................................... 33 5.8 Komplexní logika ................................................................................................... 35 5.9 Metoda vylučování barev ....................................................................................... 36 5.10 Komplexní logika s barvami................................................................................. 38 xi

xii

OBSAH

6 Implementovaný algoritmus řešení Griddlerů ..........................................................41 7 Testování .......................................................................................................................45 8 Závěr..............................................................................................................................47 Literatura .........................................................................................................................49 A Příklad souboru křížovky a DTD...............................................................................51 B Seznam křížovek ..........................................................................................................55 C Uživatelská a instalační příručka ...............................................................................57 D Obsah přiloženého CD ................................................................................................59

Seznam obrázků Obrázek 1: Obrázek Fénixe skrytý v křížovce .................................................................... 1 Obrázek 2: Ukázka vyřešeného Griddleru .......................................................................... 3 Obrázek 3: Dva malé Griddlery .......................................................................................... 4 Obrázek 4: Triddler............................................................................................................. 4 Obrázek 5: Program malované křížovky 0.9....................................................................... 6 Obrázek 6: Rozbalené menu Griddler............................................................................... 15 Obrázek 7: Volby typu souboru ........................................................................................ 16 Obrázek 8: Okno aplikace pro řešení křížovek ................................................................. 19 Obrázek 9: Statusy řádků .................................................................................................. 20 Obrázek 10: Okno aplikace v módu úprav........................................................................ 22 Obrázek 11: Schéma tříd odvozených od kolor ................................................................ 23 Obrázek 12: Křížovka s doplněnými jednoznačnými oblastmi ........................................ 27 Obrázek 13: Příklady jednoznačně určených řádků.......................................................... 28 Obrázek 14: Možnosti rozmístění skupiny 7 černých políček do řádku délky 10 ............ 28 Obrázek 15: Metoda překrývajícího se počítání ............................................................... 28 Obrázek 16: Řešení řádku pomocí zobrazení všech možností.......................................... 29 Obrázek 17: Zjednodušená metoda překrývajícího se počítání ........................................ 29 Obrázek 18: Zjednodušená metoda překrývajícího se počítání ........................................ 29 Obrázek 19: Doplnění vyřešeného řádku mezerami ......................................................... 30 Obrázek 20: Doplnění částečně vyřešeného řádku políčky pozadí................................... 31 Obrázek 21: Doplnění dalších barevných políček do částečně vyřešeného řádku............ 32 Obrázek 22: Řešení pomocí legendy více řádků najednou ............................................... 33 Obrázek 23: Výsledek použití metody řešení pomocí legendy více řádků najednou ....... 33 Obrázek 24: Metoda řešení pomocí legendy více řádku najednou použita 1x.................. 34 Obrázek 25: Metoda řešení pomocí legendy více řádku najednou použita 2x.................. 34 Obrázek 26: Metoda řešení pomocí legendy více řádku najednou použita 3x.................. 35 Obrázek 27: Výsledek opakovaného použití metody na jeden řádek ............................... 35 Obrázek 28: Komplexní logika ......................................................................................... 36 Obrázek 29: Další příklad použití komplexní logiky ........................................................ 36 Obrázek 30: Použití metody vylučování barev na 1. řádek............................................... 37 Obrázek 31: Další použití metody vylučování barev ........................................................ 37 Obrázek 32: Vyznačení čtverečků, na kterých nemůže být červená barva ....................... 38 Obrázek 33: Komplexní logika s barvami ........................................................................ 39 Obrázek 34: Další příklad komplexní logiky s barvami ................................................... 39 Obrázek 35: Třetí příklad komplexní logiky s barvami .................................................... 39 Obrázek 36: Čtvrtý příklad komplexní logiky s barvami.................................................. 40 xiii

xiv SEZNAM OBRÁZKŮ Obrázek 37: Dvě řešení křížovky velikosti 2x2 ................................................................41 Obrázek 38: Křížovka 4x4 obsahující křížovku 2x2 z obrázku 37 ...................................41 Obrázek 39: Rozdělení řádku na části ...............................................................................42 Obrázek 40: Částečně určené oblasti algoritmem .............................................................42 Obrázek 41: Pole barev vyskytujících se v křížovce.........................................................43

Seznam tabulek Tabulka 1: Seznam křížovek............................................................................................. 56

xv

xvi SEZNAM TABULEK

Seznam ukázek kódu Ukázka kódu 1: Tag colors ............................................................................................... 12 Ukázka kódu 2: Tag legend .............................................................................................. 13 Ukázka kódu 3: Příklad souboru křížovky........................................................................ 52 Ukázka kódu 4: DTD křížovek ......................................................................................... 53

xvii

xviii SEZNAM UKÁZEK KÓDU

Kapitola 1

Úvod Souslovím „Malované křížovky“, „Kódované obrázky“ nebo anglickým názvem „Griddlers“ se označuje speciální typ křížovek. Tyto křížovky nejsou tolik rozšířené jako jejich známější konkurent Sudoku. Obě fungují na podobném principu – posloupnosti logických úvah, pomocí nichž se postupně vyplňuje mřížka. Vyplněním celé mřížky je Griddler i Sudoku vyřešeno. Správnost nalezeného řešení je možné jednoduše zkontrolovat. Oproti Sudoku, kde je nutné jednotlivé řádky, sloupce a čtverce 3x3 zkontrolovat, je u Griddlerů na první pohled zřejmé, zda byl nalezen správný obrazec. Malované křížovky poskytují mnohem větší variabilitu ve složitosti než Sudoku – od jednoduchých, které lze vyřešit za pár vteřin, přes složitější, které se řeší několik minut, až po rozsáhlé křížovky, nad kterými si bude hodiny lámat hlavu i zkušený luštitel. Odměnou za námahu a obětovaný čas je velmi pěkný obrázek a radost z jeho postupného odkrývání, což jsou další výhody oproti Sudoku. Zvědavost, jaký obrázek je v křížovce skrytý, motivuje luštitele, aby se lehce nevzdával, pokud se mu právě nedaří (obrázek 1).

Obrázek 1: Obrázek Fénixe skrytý v křížovce (zdroj griddlers.net [1])

1

2

KAPITOLA 1. ÚVOD

Kapitola 2

Problém malovaných křížovek Na obrázku 2 je zobrazen vyřešený Griddler. Skládá se ze tří částí: z hledaného obrázku obdélníkového tvaru a ze dvou legend (vlevo a nahoře). Každému řádku obrázku odpovídá řádek levé legendy, sloupci obrázku sloupec horní legendy. V jednotlivých řádcích / sloupcích legendy jsou uvedeny barevné čtverečky s čísly. Ve stejném pořadí jako v legendě jsou čtverečky této barvy v obrázku. Číslo na čtverečku udává souvislý počet čtverečků odpovídající barvy v obrázku. Tato křížovka má bílou barvu pozadí a 4 typy políček: celé oranžové, celé šedé a 2 typy dělených políček, skládajících se z šedé a bílé barvy.

Obrázek 2: Ukázka vyřešeného Griddleru (zdroj griddlers.net [1])

Mezi dvěma sousedními stejnými typy čtverečků v legendě musí být v řešeném obrázku alespoň jedno políčko barvy pozadí (např. 3. řádek obrázku 2). Mezi dvěma sousedními různými typy čtverečků nemusí (např. 5. řádek obrázku 2), ale může být i několik políček barvy pozadí (např. 4. řádek obrázku 2). Na začátku a na konci každého řádku a sloupce se může, ale nemusí, vyskytovat libovolný počet políček barvy pozadí.

2.1 Dělení křížovek Křížovky se dělí na dvoubarevné (černobílé, někdy nepřesně nazývané jednobarevné, též monochromatické) a vícebarevné (multichromatické). Obě kategorie se dají dále rozdělit podle toho, zda obsahují dělená políčka (tzv. trojúhelníky) či nikoli (obrázek 3). V každé této skupině lze křížovky dále rozdělit podle velikosti: na malé, střední a velké. Jako malé jsou klasifikovány křížovky do 400 políček obrázku. Střední 3

4

KAPITOLA 2. PROBLÉM MALOVANÝCH KŘÍŽOVEK

mají 400 až 1225 políček obrázku a velké více než 1225 políček. Maximální rozměr křížovky je 50 polí na šířku a 50 na výšku. Griddlery se stranou delší než 50 se nevyrábějí.

Obrázek 3: Dva malé Griddlery (zdroj griddlers.net [1]) vlevo dvoubarevný Griddler s dělenými políčky vpravo tříbarevný Griddler bez dělených políček Křížovky většího rozsahu než 50x50 čtverečků se nazývají Multigriddlery. Jsou rozděleny do několika křížovek s rozměrem menším nebo stejným jako je maximální rozměr Griddleru. Všechny části musí být stejně velké. Pro vyřešení Multigriddleru je nutné vyřešit všechny dílčí křížovky. Speciálním odvětvím Griddlerů jsou Triddlery. Obrázky u Triddlerů nejsou ve tvaru obdélníku, nýbrž šestiúhelníku. Políčka obrázku nejsou čtverečky, ale rovnostranné trojúhelníky. Legendy se zadávají ve vodorovném směru a ve dvou šikmých směrech (obrázek 4). Triddlery neobsahují dělená políčka. Jejich rozměry se počítají obtížněji.

Obrázek 4: Triddler (zdroj griddlers.net [1])

2.2 Cíl a struktura této práce Cílem práce je vytvořit vhodné prostředí pro vytváření, úpravu a řešení Malovaných křížovek. Bude složeno ze tří propojených modulů. První modul bude editor, umožňující vytvořit novou, případně upravit stávající křížovku. Druhým, a také hlavním modulem, bude grafické prostředí, umožňující uživateli samostatně řešit Griddlery. Mezi těmito moduly se bude možné libovolně přepínat. Třetím modulem je

2.3. JINÉ APLIKACE UMOŽŇUJÍCÍ ŘEŠENÍ GRIDDLERŮ algoritmus, který vyřeší nebo alespoň pomůže křížovku vyřešit. Realizace jednotlivých prostředí bude podrobně popsána v dalších kapitolách této práce. V této práci nejprve popíšu dva příklady doposud existujících aplikací pro řešení Griddlerů. Dále se zaměřím na moje vlastní řešení problému. Nejprve představím prostředí a následně popíšu samotnou implementaci programu. Budu se zabývat strukturou souborů s křížovkami, konfiguračním souborem, základní strukturou programu, dále vysvětlím funkci jednotlivých menu a popíši ovládání aplikace včetně editoru. Nakonec vysvětlím základní i pokročilé metody řešení křížovek a jejich použití v řešícím algoritmu.

2.3 Jiné aplikace umožňující řešení Griddlerů Existuje mnoho aplikací na řešení Malovaných křížovek. Asi největší a nejznámější je server www.griddlers.net [1], který je celý věnovaný Griddlerům a křížovky jsou zde dostupné zdarma. Stránky jsou přeloženy do 23 jazyků včetně češtiny. Je zde možné najít přes 75 000 Griddlerů a přes 6 500 Triddlerů. Pro jejich řešení je zde velmi pěkné rozhraní s jednoduchým ovládáním, které podporuje mnoho užitečných funkcí, které řešení zpříjemňují. Toto prostředí mi bylo inspirací při vývoji mého programu. Křížovky jsou na serveru rozděleny do kategorií podle obsahu skrytého obrázku a uživatel si tak může vybrat tematickou křížovku. Křížovky lze vyhledávat podle velikosti, výšky, šířky, počtu barev, klíčových slov, autora nebo zda obsahují dělená políčka. Server nabízí i editor, pomocí něhož lze malovat křížovky ručně nebo je generovat přímo z obyčejného obrázku ve formátech jpeg, gif nebo bmp. Křížovku může vytvořit každý, ale pro její publikaci na serveru je nutné schválení administrátora. Velmi šikovné jsou zde publikované návody na řešení, od jednoduchých úvah pro začátečníky až po složité a komplexní úvahy nad několika řádky současně, nebo komplexní logiky s barvami, bez jejichž použití je možné některé náročnější křížovky vyluštit jen velmi obtížně nebo vůbec. Některé úvahy se však používají pouze ve speciálních situacích. Griddlers.net je komunitní server, proto také poskytuje funkce navíc, např. měření času stráveného řešením křížovky, počítání průměrného času na její vyřešení atp. Ke každé křížovce je také přiřazené hodnocení oblíbenosti a podle obtížnosti přiřazen počet bodů, který uživatel získá za její vyřešení. Podle získaných bodů se sestavují různé žebříčky a vedou se statistiky. Jedno číslo za všechny: přes 68 milionů vyluštěných křížovek všemi uživateli dohromady. Na serveru mohou uživatelé uveřejňovat komentáře a hodnotit oblíbenost křížovek. Na internetu je zdarma dostupný program s názvem Malované křížovky 0.9 [2] (obrázek 5), který umožňuje řešit a vytvářet vícebarevné křížovky. V křížovkách se mohou vyskytovat pouze následující barvy: bílá, žlutá, červená, zelená, modrá, černá. Žádné další barvy není možné přidat. Program obsahuje 14 hotových křížovek, které může uživatel buď vyřešit ručně, nebo zkusit štěstí s automatickým řešením, které část křížovky vyřeší, většinou však ne celou. Uživatelské rozhraní není moc příjemné a funkce jsou chudé, aplikace nemá ani žádné menu. 5

6

KAPITOLA 2. PROBLÉM MALOVANÝCH KŘÍŽOVEK

Obrázek 5: Program malované křížovky 0.9 [2] Na internetu je možné najít celou řadu dalších aplikací, které se řešením Malovaných křížovek zabývají.

Kapitola 3

Výběr implementačního prostředí Při hledání vhodného nástroje pro implementaci jsem vybíral mezi C#, C++ s WinApi a Javou. Zvolil jsem C# z balíku programovacích jazyků .NET od Microsoftu. S Javou zkušenosti mám, ale tíhnu spíše k jazykům založených na C. Proto jsem Javu zavrhnul. Kód Javy je interpretovaný, kdežto C# překládá zdrojový kód přímo do bytekódu, který následně spouští. C# poskytuje oproti C++ s WinApi velké množství prefabrikovaných komponent, vše se v něm píše jednodušeji a hlavně rychleji. Nemusí se vkládat stovky řádků pro vytvoření okna a smyčky zpráv. C# je ideální nástroj pro psaní okenních aplikací. Podporuje obsluhu událostí, způsobem obvyklým ve Windows. Problém však nastává, když programátor požaduje nějakou speciální funkčnost, která se běžně nepoužívá. Např. pokud chce přepínat mezi dvěma textboxy pomocí šipek. Když je textbox aktivní, zpracovává všechny zprávy od klávesnice včetně šipek. Pokud programátor potřebuje události stisku šipek odchytávat, musí přepsat stávající smyčku zpráv u textboxu, což C# umožňuje. Výhodou C# je typová bezpečnost. Každá instance v sobě obsahuje informace o tom, jaké je třídy. Tím se zabrání jejímu přetypování mezi nekompatibilními třídami. Další výhodou je možnost spouštění knihovních funkcí jiných jazyků. V dnešní době se C# stává stále oblíbenějším jazykem pro vývoj aplikací, čemuž také napomáhá rozšířenost Windows. Platformní závislost je samozřejmě nevýhodou. Proto jsem se i já nechal unést dnešním trendem, zapsal si předmět Vývoj aplikací v prostředí .NET a svůj program implementoval právě v C#. Vývojové prostředí jsem zvolil Microsoft Visual Studio 2008 [3]. Pro spuštění aplikace je nutné mít nainstalovaný .NET Framework. Cituji z první přednášky předmětu Vývoj aplikací .NET [3]: „NET Framework se považuje za „update“, lze ho získat bezplatně. Do Windows 98, NT, 2000, XP je ho možné nainstalovat ručně nebo pomocí Windows Update. Ve všech dalších Windows bude integrovanou součástí systému jako „objektové API“ (Windows Server 2003, Windows Vista).“ 7

8

KAPITOLA 3. VÝBĚR IMPLEMENTAČNÍHO PROSTŘEDÍ

Kapitola 4

Realizace programu 4.1 Slovníček pojmů Barevná políčka

políčka jiné barvy než barvy pozadí

Barva políčka

vzhled políčka; skládá se z typu políčka (celé, šikmo dělené, kosmo dělené), jedné či dvou základních barev a stejného počtu barev textu. Celé políčko obsahuje pouze jednu základní barvu a barvu textu, dělené políčko dvě základní barvy a dvě barvy textu. Text na políčku nemusí být zobrazen.

Barva políčka legendy barva políčka umístěného v legendě Barva pozadí

barva políčka, typu celé, složená z nulté základní barvy; určuje vzhled podkladové barvy, která se nachází v mřížce na místech, kde nejsou žádná barevná políčka; nevyskytuje se v legendě

Barva textu

barva definovaná pomocí složek RGB, touto barvou se píší čísla na základní barvy

Barva základní

barva definovaná pomocí složek RGB, z těchto barev se skládají barvy políček

Celé políčko

políčko typu celé; skládá se z jedné barvy textu a jedné barvy pozadí

Číslo barvy

každá barva (základní, textu, políčka) má svůj index, který ji jednoznačně identifikuje; barvy se indexují od 0 9

10

KAPITOLA 4. REALIZACE PROGRAMU

Délka legendy

součet všech čísel na políčkách legendy řádku / sloupce, ke kterému se přičte jednička za každé dvě sousedící políčka legendy stejné barvy

Délka skupiny

počet souvislých políček v řádku / sloupci vybrané barvy

Dělené políčko

políčko typu dělené šikmo nebo dělené kosmo; skládá se ze dvou základních barev a dvou barev textu

GridException

klasická výjimka rozšířená o smysluplný text, který je zobrazován uživateli

GridFatalException

výjimka vyhazovaná v situacích, kdy dojde k závažné chybě, po které není možné pokračovat v běhu aplikace. Tato výjimka je většinou vyhazována, když chybí hodnoty v konfiguračním souboru, nebo jsou neplatné.

Kosmo

z levého horního rohu do pravého dolního rohu

Levá barva

u děleného políčka označuje tu základní barvu, jejíž větší část se nachází vlevo od svislé osy políčka.

Levá legenda

označuje legendu vlevo od mřížky

Mód aplikace

stav, ve kterém se nachází aplikace; existují tři módy: mód řešení, mód úprav, mód náhledu

Mřížka

prostor pro řešení křížovky

Neurčené políčko

políčko, u kterého není rozhodnuto, jakou má barvu

Políčko

jednotka legendy a mřížky; v mřížce může mít nějakou barvu nebo být neurčené; v legendě může obsahovat políčko legendy

Políčko legendy

barva políčka s číslem nalézající se v legendě

Pravá barva

u děleného políčka označuje tu základní barvu, jejíž větší část se nachází vpravo od svislé osy políčka

Pravá legenda

označuje legendu nad mřížkou

Prázdné políčko

viz. barva pozadí

4.2. ZKRATKY Status

konstanta určující stav řešení řádku nebo sloupce; stav může být správně vyřešený, špatně vyřešený nebo nerozhodnutý

Šikmo

z pravého horního rohu do levého dolního rohu

Šířka křížovky

počet políček v řádku křížovky

Výška křížovky

počet políček ve sloupci křížovky

Zubaté pole

dvourozměrné pole obsahující řádky různých délek.

4.2 Zkratky XML

eXtensible Markup Language

DTD

Dokument Type Definition

RGB

Red, Green, Blue

px

pixelů

4.3 Formát souboru s křížovkou Soubory křížovek jsou ukládány v XML formátu a při čtení validovány pomocí DTD [5]. Pro ukládání se používají dvě různé přípony souborů, avšak struktura je velmi podobná a oba se validují proti stejnému DTD. Do souborů s příponou gri se ukládají hotové křížovky, určené k řešení. Přípona grr (Griddlers rozpracované) je určena pro uložení částečně vyřešených nebo částečně vytvořených křížovek, což se velmi hodí při řešení či vytváření větších křížovek. Kompletní DTD soubor a příklad grr souboru je publikován jako dodatek A této práce nebo je ho možné nalézt na přiloženém CD. V dalším bude popsaná struktura souborů s křížovkami. Přesné názvy XML tagů a atributů jsou zvýrazněny tučně. Všechny informace jsou uzavřeny do tagu griddler s atributem version, který bude usnadňovat načítání souborů pro případ, že se ukáže doposud zvolená reprezentace souborů nevhodná. Prvními tagy jsou name a size. Size pomocí atributů udává šířku (width) a výšku (height) Griddleru. Následuje tag legend, ve kterém se definují barvy, vertikální a horizontální legenda. Barvy políček se definují v tagu colors (ukázka kódu 1) s atributem count určujícím jejich počet. V tomto tagu předchází definici barev políček definice základních barev (basecolors) a barev textu (textcolors). Tagy basecolors a textcolors 11

12


mají atribut count určující jejich počty. Jednotlivé barvy políček se definují v tagách basecolor a textcolor pomocí jejich složek (RGB). Každá barva má své id, číslo od 0 do count - 1, pomocí kterého se na barvu odkazuje a id také barvu identifikuje v rámci skupiny, do které patří (základní barvy, barvy textu, barvy políček). Griddler musí obsahovat alespoň 2 základní barvy, 1 barvu textu a 2 barvy políček.

Ukázka kódu 1: Tag colors Po definici základních barev a barev textu následuje v tagu colors definice barev políček. Používají se tři typy políček: •

celé políčko (color-full)

•

dělené políčko šikmo (color-slash)

•

dělené políčko kosmo (color-backslash).

Každá barva políčka je identifikována jednou nebo dvěma základními barvami a stejným počtem barev textu, ze kterých se skládá. Dělené barvy obsahují dvě základní barvy a dvě barvy textu. Rozlišují se na levé a pravé. I barvy políček mají svůj identifikátor. Identifikátory bohužel nebylo možné zvolit jako vzájemně propojené reference (typ ID a IDREF), protože by takový identifikátor musel obsahovat na prvním místě písmeno. Přidání písmena před číslo barvy se mi zdálo velmi neelegantní a raději jsem oželel kontrolu vzájemné korespondence mezi id barev a jejich použití v políčkách, jakož i korespondenci id políček a jejich výskyt v legendě. Jinými slovy: Je možné vytvořit barvu políčka, skládající se z neexistující základní barvy a barvy textu, taktéž vložit neexistující barvu políčka do legendy. To však vyžaduje ruční zásah do souboru s křížovkou, program takovéto chybné soubory negeneruje a při jejich čtení hlásí chybu! Po definici barev následuje v tagu legend definice levé (vertical) a horní (horizontal) legendy (ukázka kódu 2). Levá legenda se skládá z řádků (line), zatímco horní ze sloupců (column). Řádka a sloupec mají atribut fields, určující počet políček legendy, která se v daném řádku či sloupci vyskytují. Jednotlivá políčka (field) obsahují informace o tom, jakou mají barvu (color) a číslo (value), přiřazené k danému políčku legendy, které určuje délku souvislé oblasti té barvy.

4.4. KONFIGURAČNÍ SOUBOR ... ... ...

Ukázka kódu 2: Tag legend Další vnořené tagy do griddler jsou nepovinné a používají se v rozpracovaných Griddlerech. Pro uložení obsahu mřížky slouží tag save. Jednotlivá políčka se ukládají po řádcích. Každé políčko mřížky je reprezentováno id své barvy. Nevyplněnému poli odpovídá hodnota -1. Jednotlivá políčka se oddělují znakem #. Pro uložení id barev políček, aplikovaných tlačítky myši, slouží tag mousebuttons, který má atributy pro levé (left-button) a pravé (right-button) tlačítko.

4.4 Konfigurační soubor Aplikace používá konfigurační soubor griddlers.ini, který se musí nacházet ve stejném adresáři jako spustitelný soubor aplikace. Obsahuje definice minimálních a maximálních hodnot parametrů a konstanty pro vykreslování všech dialogů. Výhodou používání konfiguračního souboru oproti psaní konstant přímo do zdrojového kódu je, že lze dosáhnout malé změny v aplikaci, aniž by se musela znova překompilovat. Další výhodou je přehledné seskupení všech parametrů na jednom místě.

4.4.1 Struktura konfiguračního souboru Aplikace používá konfigurační soubor typu INI [6]. INI soubor se dělí na sekce. Každou sekci uvozuje její název uzavřený do hranatých závorek. Její základní stavební jednotkou je přiřazení identifikátor=hodnota. Výčet identifikátorů jedné sekce končí deklarací další sekce. Každá hodnota je tedy přesně určena sekcí a identifikátorem. Identifikátor i hodnota jsou při načítání ořezány o počáteční a koncové mezery, avšak mezery, obsažené uvnitř řetězce, se zachovají. V případě, kdy je potřeba zamezit ořezání počátečních a koncových mezer, je nutné řetězec uzavřít do uvozovek. Jako komentář slouží nepárový znak středník, který zakomentuje text až do konce řádky. Prázdné řádky konfiguračního souboru jsou ignorovány. 13

14


4.4.2 Config Reader Pro čtení konfiguračního souboru slouží v mém programu statická třída ConfigReader. Obsahuje List kategorií (sekcí), z nichž každá obsahuje List

záznamů. Každý záznam se skládá z identifikátoru a hodnoty. Při vytváření třídy se načtou data z konfiguračního souboru. Pro přístup k hodnotám slouží funkce Find s parametry sekce a identifikátor, která vrací hodnotu typu string. Funkce FindInt a FindFloat vrací již přetypovaný výsledek. Vstupní formát čísla float může být buď podle české kultury s desetinnou čárkou, nebo americké s desetinnou tečkou. Funkce hledají nejprve požadovanou kategorii a v ní následně zadaný identifikátor. V případě nenalezení kategorie, identifikátoru či chybě při přetypování vyhodí GridException. Tato výjimka je výše v programu odchycena. Pokud je požadovaná hodnota nezbytná pro běh programu, je při zpracování GridException vyhozena GridFaltalException, která způsobí ukončení programu. Okomentovaný konfigurační soubor je na přiloženém CD.

4.5 Struktura programu, okno aplikace Hlavní komponentou programu je třída Griddlers. Tato třída je předávána téměř všem dialogům, které s ní pak manipulují pomocí metod. Třída Griddlers obsahuje všechny informace o Griddleru. Jsou jimi: •

jméno

•

šířka a výška

•

obě legendy (2-dimenzionální zubaté pole prvků LegendField, což jsou dvojice id barvy políčka a čísla na ní zobrazeného)

•

šířka legend, která je větší nebo rovna nejdelšímu řádku / sloupci legendy

•

statusy řádků a sloupců

•

předpočítané regulární výrazy pro řádky obou legend

•

mřížka (2-dimenzionální pole čísel – id barev políček)

•

barvy vybrané pro jednotlivá tlačítka myši

•

instanci třídy Undo_Redo zajištující uchovávání informací o změnách v mřížce

•

pole základních barev (prvky RGBColor)

•

pole barev textu (prvky RGBColor)

•

pole barev políček (prvky GColor)

4.5. STRUKTURA PROGRAMU, OKNO APLIKACE Třída obsahuje řadu funkcí, např. pro načítání a ukládání Griddleru. Dále obsahuje property pro přístup k datovým členům.

4.5.1 Nabídka aplikace Aplikace nabízí tato menu: Griddler, Vzhled, Upravit, Editor, Nápověda. Dále popíšu jednotlivá menu. Položky menu jsou také přístupné přes klávesové zkratky, což umožňuje rychlé ovládání programu pomocí klávesnice.

4.5.1.1 Menu Griddler

Obrázek 6: Rozbalené menu Griddler První část menu Griddler (obrázek 6) slouží pro operace se soubory křížovek. Umožňuje vytvořit novou křížovku (Nový), otevřít existující (Otevřít), otevřenou uložit (Uložit jako) nebo ji zavřít (Zavřít). V případě, že by mohlo dojít ke ztrátě částečně vyřešené křížovky, např. při zavření bez uložení, je uživatel nejprve dotázán, zda chce rozpracovanou křížovku uložit. Položka Nový vyvolá dialog, do kterého uživatel zadá jméno a velikost nového Griddleru. Program následně vytvoří Griddler požadované velikosti a přepne aplikaci do módu úprav. Práce v módu úprav je popsána v kapitole 4.5.3. Existující křížovky se otvírají přes položku Otevřít. Tato volba umožňuje načíst jak křížovky hotové, připravené k řešení (.gri), tak i částečně vytvořené nebo částečně vyřešené křížovky (.grr). Oba typy jsou v dialogu odděleny (obrázek 7).

15

16


Pro soubory s příponou gri se dodržuje následující konvence pro názvy souborů: <šířka>xx<počet základních barev> x<počet barev políček>_<jméno křížovky>

Obrázek 7: Volby typu souboru

Symboly <šířka>, , <počet základních barev>, <počet barev políček> označují dvouciferná čísla s příslušným významem. Symbol <jméno křížovky> by neměl obsahovat písmena s háčky a čárkami a je od posledního čísla oddělen podtržítkem. Příklad názvu souboru: 13x18x02x06_Carodejnice.gri. Křížovky se při načítání validují podle DTD (soubor griddler.dtd), který musí být umístěn ve stejném adresáři jako otvíraný Griddler. Pokud se v daném adresáři DTD soubor nenachází, je do něj nejprve zkopírován (cesta ke zdrojovému DTD se nachází v konfiguračním souboru) a po načtení Griddleru smazán. Načtení souboru zajišťuje funkce ReadFromXmlFile (filename), jejíž hlavní částí je třída XmlReader. Tato třída parseruje soubor na jednotlivé XML elementy, které načítací funkce následně zpracovává. Po zpracování celého souboru se vytvoří regulární výrazy pro každý řádek a sloupec křížovky (tato akce může u velkých, hodně barevných křížovek nějakou dobu trvat). Pomocí regulárních výrazů se počítají jednotlivé statusy řádků / sloupců. Nakonec se provede základní kontrola, kterou validace přes DTD nemůže zajistit. Tato kontrola zjišťuje chyby, způsobené uživatelem při ruční editaci souboru křížovek. Při volbě Uložit jako se nejprve zkontroluje, zda obě legendy nejsou prázdné a zda Griddler obsahuje alespoň dvě barvy políček (barvu pozadí a jednu další). Následně je vyvolán dialog pro uložení rozpracované křížovky. Tento dialog neumožňuje uložit křížovku s příponou gri. Zároveň se také dotazuje uživatele na přepsání souboru, pokud požadovaný soubor již existuje. Křížovky se ukládají funkcí SaveToXmlFile (filename, true). Ukládání se realizuje třídou StreamWriter, která je ukládá jako datový proud. Kontrola pomocí DTD se zde neprovádí. Volba Zavřít křížovku zavře a vyčistí všechny panely. Další tři nabídky v menu Gridder obsahují volby pro automatické řešení křížovek. Při výběru některé z těchto metod se nejprve zkontroluje, zda korespondují počty jednotlivých barev v levé a horní legendě. Pokud tomu tak není, program oznámí chybu a algoritmus řešení se nespustí. Dále se zkontroluje, zda je mřížka prázdná. Pokud není, zobrazí se dotaz na vymazání mřížky a v případě kladné volby je mřížka vymazána, jinak se pokračuje dále. Dalším krokem je spuštění řešícího algoritmu s požadovanými parametry. Implementace metod řešení je popsána v kapitole 6. Nakonec je uživatel informován o nalezení, případně nenalezení řešení. Pokud je řešení nalezeno, uživateli se zobrazí. Nabídka Konec ukončí aplikaci.

4.5. STRUKTURA PROGRAMU, OKNO APLIKACE

4.5.1.2 Menu Vzhled Menu Vzhled umožňuje křížovku zvětšit, zmenšit, či nastavit původní velikost. Zde se také dají nastavit barvy jednotlivých čar. Všechny konstanty jsou načítány z konfiguračního souboru a dají se tedy jednoduše změnit. Základní výška i šířka políčka je 20 px. Při každém požadavku na zvětšení nebo zmenšení se k této velikosti přičtou nebo odečtou 3 px. Požadavek je možné opakovat až do maximální velikosti 50 px nebo minimální velikosti políčka 5 px. Volba Barvy čar umožňuje změnit barvu čar Griddleru (defaultně šedá), barvu zvýrazněných a okrajových čar (defaultně černá) a barvu vodících čar (defaultně žlutá). Změna tohoto nastavení zpříjemňuje uživateli řešení křížovek.

4.5.1.3 Menu Upravit Menu Upravit umožňuje uživateli po jednom kroku vracet všechny změny ve vyplněných políčkách mřížky (Krok zpět), či je opět znovu vyplňovat (Krok vpřed). Nabídka Začít znovu vymaže celou mřížku a historii změn. Ukládání změn zajišťuje třída Undo_Redo. Každá změna je reprezentována třídou Step jako skupina 4 hodnot (souřadnice x, souřadnice y, původní hodnota políčka, nová hodnota políčka). Třída Undo_Redo obsahuje dva zásobníky (undo a redo) hodnot typu Step. Při kliknutí na mřížku je přidána nová hodnota do undo a zásobník redo je vymazán. Při požadavku na vrácení o krok zpět se přesune hodnota z vrchu zásobníku undo na vrch zásobníku redo. Při požadavku na znovu provedení změny je tomu naopak. Třída Undo_Redo také poskytuje funkce indikující, zda je možné provést krok zpět či vpřed. Podle těchto funkcí se povoluje či zakazuje kliknutí na položky tohoto menu. Třída umí na požádání oba zásobníky vymazat.

4.5.1.4 Menu Editor V menu Editor je v řešícím módu přístupná pouze položka Mód úprav. Je to stejný mód, do kterého přepíná volba vytvoření nového Griddleru. Při přepnutí do módu úprav se zvětší šířka levé legendy na šířku mřížky a výška horní legendy na výšku mřížky, aby bylo možné přidat do legendy další políčka. Ostatní položky menu budou rozebrány v kapitole 4.5.3.

17

18


4.5.1.5 Menu Nápověda Program obsahuje 4 nápovědy: O autorovi, Griddlers, Jak řešit a Editor. Dialog O autorovi je klasická informativní zpráva. Ostatní nápovědy realizuje jediný dialog, jen se mění zdroj dat. Zdrojem dat jsou rtf soubory v podobě datových zdrojů aplikace (součást spustitelného souboru), které jsou v dialogu zobrazovány. Texty jednotlivých nápovědních souborů jsou na přiloženém CD. Nápověda Griddlers vysvětluje uživateli pravidla pro řešení Griddlerů a popisuje základní funkce pro ovládání programu. Nápověda Jak řešit uvádí základní metody řešení Griddlerů. Nápověda Editor popisuje základní funkce editoru, sloužící pro vytvoření nové křížovky.

4.5.2 Řešení křížovek Po otevření zvoleného souboru s křížovkou se v okně Griddleru zobrazí uživatelské rozhraní pro řešení křížovek (obrázek 8). Funkci jednotlivých ovládacích prvků vysvětlím na následujícím příkladu. V titulku aplikace je zobrazen název právě řešeného Griddleru. Na panelu Myš jsou zobrazeny dvě barvy políček nebo neurčené políčko vybrané pro levé (vlevo) a pravé (vpravo) tlačítko myši. Na panelu Barvy je zobrazeno neurčené políčko a všechny barvy políček, které Griddler obsahuje. Kliknutím levým či pravým tlačítkem myši na některé z těchto políček se vybrané políčko objeví na panelu Myš. Pro prostřední tlačítko myši je vždy vybrané neurčené políčko. Největší plochu zabírá hlavní panel s křížovkou, která se skládá z levé legendy, horní legendy a mřížky určené k vyplňování. Při kliknutí na políčko mřížky se políčku nastaví barva zvolená pro tlačítko myši, kterým se kliklo. Tlačítko myši je možné přidržet a táhnout po mřížce, čímž se všechna přetažená políčka vybarví zvolenou barvou. Všechny panely v okně aplikace (myš, barvy, hlavní, atd.) používají techniku double bufferování. Tato technika zabraňuje blikání obrázku při jeho překreslování na panel. Při překreslování vybrané oblasti se tato oblast nejprve přebarví na barvu pozadí a teprve následně se do ní maluje obrázek. Vymazání na barvu pozadí způsobuje blikání obrázku. Technika double bufferování tento problém odstraní. Při ní je obrázek nejprve kreslen do bufferu, který byl předtím vymazán na barvu pozadí. Teprve když je celý obrázek vykreslen v bufferu, dojde k jeho překreslení na monitoru, aniž by se mazalo na barvu pozadí. Standardně při požadavku na překreslení oblasti na monitoru ji operační systém vymaže na barvu pozadí. Aby double bufferování mohlo fungovat, je nutné tomu zabránit. Problém je v tom, že zabránit volání této systémové funkce ve všech případech vyžaduje složitý zásah do jednotlivých komponent panelu, protože toto volání je v nich zabudováno. V mém programu tedy např. při zobrazení skrolovací lišty obrázek blikne.

4.5. STRUKTURA PROGRAMU, OKNO APLIKACE

Obrázek 8: Okno aplikace pro řešení křížovek 1 – Menu aplikace 2 – Panel Myš zobrazuje vybrané barvy políček z palety barev pro tlačítka myši 3 – Panel Barvy slouží jako paleta barev, zobrazuje neurčené políčko a všechny barvy políček Griddleru 4 – Hlavní panel s Griddlerem 5 – Mřížka 6 – Levá legenda 7 – Horní legenda 8 – Panel pro zobrazení legendy zvýrazněného řádku 9 – Panel pro zobrazení legendy zvýrazněného sloupce 10 – Miniatura Griddleru 11 – Název křížovky 12 – Vodící čáry 13 – Sloupec obsahující jednotlivé statusy řádků 14 – Řádka obsahující jednotlivé statusy sloupců

19

20


Metoda double bufferování je ještě rozšířena při vykreslování hlavního panelu s křížovkou. Ten se nejprve vykreslí do bitmapy, ze které se pak maluje do bufferu. To umožňuje, aby se časově náročná operace vykreslení mřížky a obou legend prováděla jen v nezbytných situacích, jako je například změna velikosti políčka. V ostatních případech je použita křížovka z bitmapy. Bitmapa je proto aktualizována při každé změně v křížovce. V programu je také významně urychleno opakované kreslení políček stejné barvy se stejným číslem a políček mřížky se stejnou barvou. Tato políčka jsou proto malována pro každé požadované číslo a barvu jen jednou a další požadavky na stejné číslo a barvu jsou uspokojovány ze zálohy. Toto urychlení je tím významnější, čím méně různých kombinací barev políček a čísel se v křížovce vyskytuje. Barvy vybrané pro jednotlivá tlačítka myši lze také měnit kliknutím na legendu. Do myši se tím vybere barva políčka legendy, na které se kliklo, nebo barva pozadí, pokud se kliklo na prázdné políčko. Nad levou legendou a vlevo od horní legendy je nakreslena miniatura křížovky, která místo neurčených polí zobrazuje barvu pozadí. Miniatura slouží řešiteli pro lepší představu o vzhledu částečně vyřešené křížovky. Při pohybu myši po mřížce se na mřížce objevují vodící čáry, zvýrazňující řádek a sloupec, na kterém je aktuálně kurzor myši. Políčka legendy zvýrazněného sloupce a řádku se zobrazují dole a vpravo od hlavního panelu, na panelech pro zobrazení zvýrazněného řádku a sloupce. Mezi legendami a mřížkou je prostor pro zobrazení statusu řádku a sloupce. Status může nabývat vždy jedné z těchto hodnot: •

správně vyřešený, pokud řádek / sloupec odpovídá legendě – je zobrazen zeleně. Neurčené políčko je počítáno jako barva pozadí

•

špatně vyřešený, pokud řádek / sloupec obsahuje chybu nebo již nemůže být dořešen správně – je zobrazen červeně

•

neurčený, pokud není řádek / sloupec správně, ani špatně vyřešený – je zobrazen bílou barvou.

Statusy všech řádků a sloupců jsou uloženy v poli. Při kliknutí myši na mřížku se přepočítá status pouze změněného řádku a sloupce. Status se počítá pomocí regulárních výrazů. Pro určení statusu řádky nebo sloupce jsou zapotřebí dva regulární výrazy. První umí rozhodnout, zda je řádek správně vyřešený. Druhý rozhodne, zda je řádek špatně vyřešený či neurčený. Vytváření regulárních výrazů je výpočetně náročné a proto se vytváří jen při otevření křížovky nebo při jejím přepnutí do módu řešení. V ostatních případech se použijí již vytvořené regulární výrazy. Při požadavku na určení statusu řádku nebo sloupce se nejprve vytvoří řetězec odpovídající obsahu řádku / sloupce mřížky: Do řetězce se přidává id barev políček postupně tak, jak na sebe navazují v mřížce. Za každé id barvy se přidává znak #, bude tedy i na konci řetězce. Místo neurčeného políčka se používá písmeno x. Např. pro 2. řádek obrázku 9 (nechť černá barva políčka má id = 1 a červená id = 2)

Obrázek 9: Statusy řádků

4.5. STRUKTURA PROGRAMU, OKNO APLIKACE vypadá řetězec následovně: 1#x#x#2#x#. Po sestavení řetězce se buď vytvoří regulární výraz, nebo se vezme již existující. Pro vytvoření nového regulárního výrazu je nutné nejprve zkonstruovat pattern. Ten se vytváří podle řádku / sloupce legendy. Pattern testující, zda je řádek / sloupec správně vyřešený, začíná řetězcem „^(0#|x#)*“, což znamená, že na začátku řádky se může vyskytovat libovolné množství prázdných nebo neurčených políček. Jednotlivá políčka legendy se reprezentují barvou políčka s křížkem a hodnotou – počtem jejího opakování ve složených závorkách, např. červená barva s číslem tři je reprezentována řetězcem „(2#){3}“. Mezi jednotlivá políčka legendy je přidána možnost 0 a více prázdných nebo neurčených políček, pokud jsou obě sousedící barvy různé (řetězec „(0#|x#)*“), 1 a více prázdných nebo neurčených políček v případě, že jsou jejich barvy stejné (řetězec „(0#|x#)+“). Patern se zakončí řetězcem „(0#|x#)*$“, což znamená, že na konci může být libovolné množství prázdných či neurčených políček. Pro 2. řádek legendy z obrázku 9 vypadá pattern následovně: „^(0#|x#)*(1#){3}(0#|x#)*(2#){2}(0#|x#)*$“. Podle vytvořeného patternu systém vytvoří regulární výraz a vyzkouší, zda mu odpovídá řetězec vytvořený z řádku / sloupce mřížky. Pokud ano, řádek je správně vyřešený. V opačném případě se rozhodne status podle 2. regulárního výrazu. Pro vytvoření druhého regulárního výrazu je nutné nejprve zkonstruovat jeho pattern. Ten se od prvního liší pouze v konstrukci části, odpovídající políčku legendy. Kromě barvy políčka se zde připouští i neurčené políčko, např. červená barva s číslem tři je reprezentována řetězcem „(2#|x#){3}“ namísto „(2#){3}“. Pro 2. řádek legendy z obrázku 9 vypadá pattern následovně: „^(0#|x#)*(1#|x#){3}(0#|x#)*(2#|x#){2}(0#|x#)*$“. Opět se provede test, zda řetězec odpovídá regulárnímu výrazu podle druhého patternu. Pokud ano, řádek má status neurčený, pokud ne, má řádek status špatně vyřešený. Regulární výrazy se dále používají v jedné z metod řešení. Pokud dojde k vyřešení křížovky, je o tom uživatel informován a je mu nabídnuta možnost zobrazit náhled křížovky. Při náhledu jsou odstraněny obě legendy, miniatura křížovky a všechny statusy. Neurčená políčka jsou nahrazena barvou pozadí a obrázek je vykreslen bez mřížky.

4.5.3 Ovládání a funkce editoru Při přepnutí do módu úprav poskytuje program uživateli možnost vytvořit nebo upravit stávající Griddler. Informaci, že se aplikace nachází v módu úprav, symbolizuje řetězec „[Mód úprav]“ přidaný do titulku okna za jméno Griddleru (obrázek 10). V módu úprav jsou také přístupné všechny položky menu Editor. Ostatní menu poskytují uživateli stejnou funkcionalitu, jaká je popsána výše. Funkci jednotlivých položek menu Editor budu demonstrovat na vytváření nového Griddleru. Po vyplnění názvu, šířky a výšky nového Griddleru následuje nastavení barev. Pro vytvoření barev políček je nutné nejprve vytvořit alespoň dvě základní barvy a jednu barvu textu. 21

22


Volbou položky Barvy základní je vyvoláno okno pro správu základních barev. Pro výběr konkrétní barvy je použit klasický Windows dialog. První přidaná barva je nastavena jako barva pozadí. O této skutečnosti je uživatel informován hláškou. Přidané základní barvy jsou v dialogu zobrazeny čtverečkem. U každé barvy je její název a checkbox, sloužící pro její označení. Vybraná barva může být nahrazena jinou. Označená barva, s výjimkou barvy pozadí, může být smazána, pokud není použita v barvě políčka. Pro reprezentaci základních barev slouží třída RGBColor, která ukládá informace o jejím čísle a o jejích jednotlivých složkách ve schématu RGB. Třída RGBColor obsahuje metodu, která z informací uložených v instanci, vytvoří klasickou barvu určenou k malování. Všechny základní barvy jsou uložené v poli baseColors.

Obrázek 10: Okno aplikace v módu úprav 1 – Upozornění na práci v módu úprav je přidáno za název křížovky 2 – Všechny položky menu Editor jsou v módu editace přístupné 3 – Textbox pro vytvoření nového políčka legendy

Dalším krokem při vytváření Griddleru je vytvoření barev textu výběrem položky Barvy textu. Pro správu barev textu slouží podobný dialog jako pro správu

4.5. STRUKTURA PROGRAMU, OKNO APLIKACE základních barev. Rozdíl je však v tom, že všechny barvy textu jsou na stejné úrovni, tedy neexistuje zde obdoba barvy pozadí. Posledním krokem je vytvoření vlastních barev políček. Pro správu barev políček slouží dialog vyvolávaný přes položku Barvy políček. Dialog Barvy políček je velmi podobný výše zmíněným dialogům a umožňuje přes další Skládací dialog vytvořit novou či upravit stávající barvu políčka. Dialog Barvy políček také umožňuje barvu políčka smazat, pokud se ovšem nevyskytuje v některé z legend. Pro názornější pochopení smyslu Skládacího dialogu nejprve vysvětlím strukturu barev políček. Od abstraktní třídy GColor jsou odvozeny třídy GColorFull (celé políčko), GColorSlash (políčko dělené šikmo), GColorBackSlash (políčko dělené kosmo) viz obrázek 11. Jednotliví potomci třídy GColor obsahují členské proměnné pro uložení jednotlivých barev, ze kterých se skládají. Dále obsahují metody, které nemohly být definovány v třídě GColor, pro jejich vykreslování a např. pro zjišťování, zda obsahují vybranou základní barvu či barvu textu.

Obrázek 11: Schéma tříd odvozených od GColor Hlavní výhodou dělených políček v mém programu oproti děleným políčkům v aplikaci na serveru griddlers.net je možnost volby různé barvy textu na jednotlivé základní barvy, ze kterých se skládá dělené políčko. To ovšem vyžaduje použití triku při vykreslování, protože funkce na psaní textu neumožňují psát dvoubarevný text, natož s šikmým barevným přechodem. Trik spočívá v odděleném kreslení dvou celých políček, z nich každé může mít různou barvu textu. Jedno z políček je následně zvoleno 23

24


jako textura. Texturovým štětcem je jedna polovina políčka překreslena texturou druhého políčka. Tím vznikne políčko s obecně různými základními barvami a různými barvami textu. Skládací dialog umožňuje uživateli vybrat ze tří typů políček. V případě zvolení celého políčka zobrazí dialog jednu sadu základních barev a barev textu. V ostatních případech zobrazí dialog dvě sady – jednu pro levou základní barvu a barvu textu, druhou pro pravou. Uživatel zaškrtne požadovanou kombinaci a program vytvoří novou barvu políčka. Dialog samozřejmě neumožní vytvořit barvu políčka se stejnou kombinací základních barev a typu políčka jako má jiné již existující políčko. Barva pozadí je zobrazena mezi barvami políček, ovšem její úprava je možná pouze přes dialog základních barev. Existují dvě možnosti vytváření křížovek. První možnost je malovat obrázek přímo do mřížky. Při malování se automaticky dopočítávají políčka legendy, vždy pro změněný řádek a sloupec. Malování funguje stejně jako řešení křížovky až na to, že kliknutí na políčko legendy má jinou funkcionalitu, než změnu barvy políčka. Druhou možností je kliknout myší do legendy, což zobrazí textbox, do kterého je možné vepsat číslo. Pro zobrazení textboxu musí být pro tlačítko myši zvolena jiná barva, než je barva pozadí, a nesmí být tlačítko myši nastavené na neurčené políčko. Po stisknutí klávesy Enter se ověří, zda uživatel během psaní nevyměnil barvu pod tlačítkem myši, kterým kliknul, za barvu pozadí nebo neurčené políčko. Dále se zkontroluje, zda vytvořením takového políčka by nebyla legenda příliš dlouhá, tedy delší než řádek či sloupec křížovky. Pokud je vše v pořádku, vytvoří se z napsaného čísla a zvolené barvy nové políčko legendy. Textbox se následně skryje. V době, kdy není používán, je zmenšený, nepřístupný a schovaný v levém horním rohu hlavního panelu. Tímto způsobem lze vytvářet křížovky, aniž by uživatel předem znal jejich řešení. Obě metody vytváření křížovek nelze kombinovat. V případě, že se maluje do mřížky a následně chce uživatel něco vepsat do legendy, je obrázek v mřížce nenávratně smazán. Naopak, když uživatel vyplňuje křížovku a následně klikne do mřížky, přichází o všechna dosud napsaná políčka legendy. Nová legenda se začne zobrazovat až po malování do mřížky. Toto chování se může zdát uživateli nežádoucí, ale je nutné zamezit situaci, kdy si obrázek v mřížce nebude odpovídat s legendou. Pokud se při řešení Griddleru uživatel přepne do módu úprav, jsou uchovány hodnoty v legendách a pokud je křížovka vyřešena, jsou zachovány hodnoty i v mřížce. V opačném případě je mřížka vymazána. Pokud chce uživatel zvětšit nebo zmenšit rozměry křížovky, umožní mu to dialog Ořezat / Orámovat přes stejnojmennou položku v menu. Dialog se skládá ze čtyř textboxů. Každý je přiřazen k jedné straně křížovky. Intuitivní názvy (nahoře, dole, vlevo, vpravo) vedou uživatele k zadání požadovaných změn do textboxů. Počet políček, o které má být křížovka zvětšena nebo zmenšena, se vepíše do odpovídajícího textboxu. Kladné číslo určuje přidání políček (orámování) na stranu křížovky, záporné značí odebrání políček (ořezání) ze strany křížovky. Ořezávané řádky či sloupce musí být prázdné. Při překročení maximální nebo minimální velikosti Griddleru je uživateli zobrazena hláška, že akci nelze provést. Volba Vymazat Griddler vymaže mřížku a obě legendy.

4.5. STRUKTURA PROGRAMU, OKNO APLIKACE Možnost Mód řešení přepne křížovku z módu úprav do módu řešení. Dojde k ořezání šířky legend na délku nejdelší řádky a sloupce + 1, vymazání mřížky, vymazání historie kroků zpět a vpřed a také se znepřístupní položky menu Editor, kromě možnosti přepnutí do módu úprav. Pouze v editoru je možné vytvořit soubory Griddlerů s příponou gri. Umožňuje to volba Generovat Griddler. Soubory s příponou gri by měly být platné křížovky, proto je před zobrazením dialogu pro uložení zkontrolováno, zda je v obou legendách stejný počet políček od každé barvy. Pokud je v křížovce chyba, je uživatel upozorněn, ve které barvě a dialog pro uložení souboru není zobrazen.

25

26


Kapitola 5

Techniky řešení křížovek V této kapitole popíšu běžně používané metody řešení křížovek. Všechny zde prezentované metody jsou publikovány na serveru griddlers.net [7]. Metody jsem seřadil od nejjednodušších (úvahy nad jedním řádkem) po nejsložitější (komplexní logika s barvami). Všechny metody demonstrované na řádcích lze samozřejmě použít i na sloupce.

5.1 Vyplnění jednoznačných oblastí v křížovce Tato metoda se zaměřuje na křížovky obsahující v legendě velmi malý počet políček od některé barvy. Legenda na obrázku 12 určuje, že mřížka obsahuje jedno bílo-šedé šikmo dělené políčko a jedno šedo-bíle kosmo dělené políčko. Jejich poloha vyplývá z obou legend. Dále mřížka obsahuje čtyři oranžová pole, tři v pátém řádku a jedno ve čtvrtém. Legenda ve sloupcích určí přesně jejich pozici. Obrázek 12: Křížovka s doplněnými jednoznačnými oblastmi (zdroj griddlers.net [1])

27

28

KAPITOLA 5. TECHNIKY ŘEŠENÍ KŘÍŽOVEK

5.2 Vyplnění jednoznačně určených řádků Jednoznačně určené řádky jsou takové, jejichž délka legendy je stejná jako šířka mřížky. Délka legendy se spočítá jako součet všech čísel na políčkách legendy, ke kterému se přičte jednička (prázdné políčko) za každé dvě sousedící políčka legendy stejné barvy. Obrázek 13 znázorňuje jednoznačně určené řádky, jejichž legenda má délku 5. Obrázek 13: Příklady jednoznačně určených řádků

5.3 Vyplnění částečně určených řádků Šířka křížovky na obrázku 14 je 10 políček, zatímco délka legendy je pouze 7. Řádky a) – d) obrázku 14 zobrazují všechny 4 možnosti, jak do řádku umístit souvislou skupinu 7 černých políček. Poslední řádek e) ukazuje společnou část všech rozmístění, kterou je možné jednoznačně vyplnit. Pro zjištění této oblasti není potřeba malovat všechny možnosti, kterých může být mnoho. Společné čtverečky jsou průnikem vybarvených čtverečků při posunutí skupiny co nejvíce doleva a doprava. Této metodě se říká překrývající počítání (obrázek 15). Zprava i zleva počítám políčka od 1 až do délky skupiny (řádky a) a b)). Políčka započítaná dvakrát se mohou vybarvit (řádek c)).

a) b) c) d) e) Obrázek 14: Možnosti rozmístění skupiny 7 černých políček do řádku délky 10

a) b) c) Obrázek 15: Metoda překrývajícího se počítání

5.4. DOPLNĚNÍ VYŘEŠENÉHO ŘÁDKU PRÁZDNÝMI POLÍČKY Stejnou úvahu lze použít i pokud se legenda skládá z několika skupin políček (5 černých a 3 zelených). Všechny možnosti rozmístění 5 černých a 3 zelených čtverečků v řádku o 10 políčkách (řádek a) – f)) a také jejich průnik (řádek g)) znázorňuje obrázek 16. Metoda kreslení všech možností však není příliš praktická, proto se většinou používá zjednodušená metoda překrývajícího se počítání (obrázek 17). Od délky řádku se odečte délka legendy (v tomto případě 8) a vyjde počet vynechávaných polí (10 – 8 = 2). Počítá se pouze zleva vždy od 1 do délky skupiny (řádek a)) a vybarvují se pouze políčka s číslem vyšším, než je počet vynechávaných polí (řádek b)). Další skupina se začíná počítat od ukončení předchozí.

a) b) c) d) e) f) g) Obrázek 16: Řešení řádku pomocí zobrazení všech možností

a) b) Obrázek 17: Zjednodušená metoda překrývajícího se počítání

a)

Příklad na obrázku 18 má délku legendy 8, budou se tedy vynechávat opět 2 pole. b) Při této metodě je nutné vynechávat vždy jedno pole Obrázek 18: Zjednodušená metoda mezi dvěma sousedícími překrývajícího se počítání políčky legendy stejné barvy, kde je povinné prázdné políčko (řádek a)). Je také vidět, že ze skupin menších nebo stejně velkých, jako je počet vynechávaných polí, se nemůže vybarvit nic (řádek b)). Tuto metodu lze tedy použít, pokud některé políčko legendy obsahuje větší číslo než je počet vynechávaných polí.

5.4 Doplnění vyřešeného řádku prázdnými políčky V řádku, ve kterém každému políčku legendy odpovídá v mřížce skupina vybarvených políček (řádek je vyřešený), se nahradí všechna neurčená políčka barvou 29

30


pozadí (obrázek 19). Doplnění políčka barvy pozadí díky legendě k řádku může umožnit doplnění dalších políček určené legendou ve sloupci.

Obrázek 19: Doplnění vyřešeného řádku mezerami

5.5 Doplnění částečně vyřešeného řádku políčky pozadí Jedná se o případy, kdy rozmístění již určených políček v řádku napovídá, kde nemohou být další barevná políčka, ale pouze políčka barvy pozadí. Několik typických situací je zobrazeno na obrázku 20. Legenda k řádku a) obsahuje pouze skupiny políček délky dvě, tedy šesté políčko musí být prázdné. Skupina dvou políček v mřížce v řádku b) je součástí trojice určené legendou. Legenda obsahuje pouze jedinou skupinu políček. Ke dvojici určených políček lze chybějící černé políčko připojit pouze zleva nebo zprava. Ostatní pole musí být prázdná. Řádek c) je obdobný jako předchozí. Zdá se, že každé černé políčko patří do jiné skupiny. Opravdu tomu tak je, protože v opačném případě by legenda musela obsahovat pole délky 5. Každému políčku legendy odpovídá jedna skupina políček v mřížce. Za těchto okolností mohu provést pro každou skupinu zvlášť stejnou úvahu jako v předchozím případě. Při následujících úvahách je důležité si uvědomit, které políčko legendy odpovídá které konkrétní skupině políček v mřížce. V řádku d) je jasné, že zelené pole je součástí zelené trojice, která je poslední vybarvenou skupinou řádku. Vlevo od ní musí být políčka barvy pozadí. V řádku e) jsou obě zelená pole určená. Podle legendy se mezi nimi a vpravo od druhého zeleného pole nenachází žádné další barevné pole. Všechna neurčená políčka v těchto dvou oblastech musí mít barvu pozadí. V následujícím řádku f) musí dvě černá pole v mřížce patřit skupině tří černých polí. Vpravo od této skupiny již žádné barevné pole nebude. V řádku g) odpovídá skupina tří černých políček políčku legendy s číslem 3. Předchozí i následující políčko legendy mají stejnou barvu jako políčko s číslem 3, proto bude skupina tří černých políček ohraničená z každé strany alespoň jedním políčkem barvy pozadí. V řádku h) nemohou všechna černá políčka patřit k jednomu políčku legendy, protože by mělo délku nejméně čtyři. První dvojice je ze skupiny tří polí, zatímco třetí

5.6. DOPLNĚNÍ DALŠÍCH BAREVNÝCH POLÍČEK DO ČASTEČNĚ VYŘEŠENÉ pole je ze skupiny dvou polí. Mezi těmito skupinami musí být prázdné políčko. (Také poslední políčko bude prázdné). V řádku i) odpovídají dvě černá políčka políčku legendy s číslem 3. Kdyby tomu tak nebylo a odpovídala by políčku s číslem 2, znamenalo by to, že černá trojice a jedno prázdné políčko se nachází vlevo od nich. Tam jsou však jen tři volná pole. Poslední řádek j) je velmi podobný předchozímu, přesto ale nelze určit, kterému políčku legendy odpovídá skupina dvou černých políček. Není tedy možné do řádku cokoliv doplnit. Tato situace nastává u křížovek nejčastěji, takže nezbývá než upřít pozornost na další řádek. a) b) c) d) e) f) g) h) i) j) Obrázek 20: Doplnění částečně vyřešeného řádku políčky pozadí

5.6 Doplnění dalších barevných políček do částečně vyřešeného řádku Obrázek 21 znázorňuje několik situací, při kterých lze do řádku doplnit barevná pole. Již určená políčka zmenší prostor pro umístění barevných polí. Pozici všech černých políček v řádku a) lze přesně určit – délka legendy je stejná jako délka všech zatím neurčených políček. Díky políčkům barvy pozadí lze řádek b) doplnit metodou překrývajícího se počítání (viz metoda 5.3). Skupina tří černých políček v řádku c) odpovídá políčku legendy s číslem 3. Je tedy zřejmé, že skupina dvou černých polí je vlevo od ní a jedno černé pole bude vpravo. Skupinu dvou černých polí částečně vyplníme metodou překrývajícího se 31

32


počítání do skupiny tří neurčených políček. Pozici černého políčka s číslem 1 nelze doplnit. Legenda řádku d) jednoznačně určuje, že první vybarvené pole je první pole první trojice a druhé vybarvené pole je poslední políčko druhé trojice legendy. Přesná poloha obou trojic daných legendou je jasná. První černé políčko v mřížce na řádku e) je buď první, nebo druhé políčko černé čtveřice. Po něm bezprostředně následují alespoň tři další černá políčka, z nich jedno je již vyplněné. V dalším řádku f) by podle legendy měla být vlevo skupina tří černých políček. Přesně určené zelené políčko dělí legendu na políčka vlevo a vpravo od něj a funguje podobně jako okraj mřížky v předchozím řádku. Černé políčko je tedy druhé nebo třetí z černé trojice. Vlevo od něj tedy musí být alespoň jedno černé políčko. Neurčená políčka na řádku g) jsou v tomto případě rozdělena do dvou skupin. Do každé ze skupin lze vepsat právě jednu skupinu černých polí podle legendy. Do žádné skupiny neurčených polí nelze vepsat dvě sousední skupiny políček podle legendy. Na posledním řádku h) náleží první dvojice černých polí černé trojici. Třetí černé pole z mřížky již do této trojice patřit nemůže, patří tedy do čtveřice, jakožto i poslední černé pole v mřížce. Prostor mezi oběma těmito políčky do této čtveřice také patří. S rostoucí délkou řádku složitost určení odpovídajících skupin políček roste, avšak princip těchto úvah zůstává stejný. Vždy je nutné rozpoznat, zda na políčku musí, nebo naopak nesmí být konkrétní barevné políčko nebo barva pozadí. a) b) c) d) e) f) g)

h) Obrázek 21: Doplnění dalších barevných políček do částečně vyřešeného řádku

Řešitel musí odhadnout, který z výše jmenovaných postupů se hodí pro vybraný řádek. Nejprve použije metody 5.1 – 5.3 a následně pak, díky určeným políčkům, může používat metodu 5.4 – 5.6. Výše popsané metody stačí k vyřešení mnoha křížovek, avšak pro řešení ještě složitějších je někdy potřeba použít i další logické úvahy.

5.7. ŘEŠENÍ POMOCÍ LEGENDY VÍCE ŘÁDKŮ NAJEDNOU

5.7 Řešení pomocí legendy více řádků najednou Následující křížovka se výše uvedenými metodami řeší velmi těžce. Vysvětlím na ní, jak funguje metoda řešení pomocí více řádků najednou. Zaměřím se na poslední řádek a zkusím umístit skupinu 10 černých čtverců co nejvíce doprava. Podle horní legendy doplním další černé čtverečky do sloupců (obrázek 22). Červeně zvýrazněné čtverečky ukazují rozpor s legendou předposledního řádku.

Obrázek 22: Řešení pomocí legendy více řádků najednou (zdroj griddlers.net [1]) Skupina 10 černých polí tedy nemůže zasahovat pod obě červená pole. Zasahuje-li pod pravé, musí zasahovat i pod levé. Skupina tedy může zasahovat pouze pod levé červené pole a tedy posledních 6 políček posledního řádku (označených křížkem) musí být prázdných (obrázek 22). Tím se omezil prostor pro souvislou skupinu deseti černých polí, jejíž část můžu nyní vyplnit do křížovky (obrázek 23).

Obrázek 23: Výsledek použití metody řešení pomocí legendy více řádků najednou (zdroj griddlers.net [1])

Tyto úvahy lze pro jeden řádek i několikrát opakovat, jak ukazuje následující křížovka. Opět se zaměřím na poslední řádek se skupinou 8 černých políček. Na obrázku 24 je umístěná skupina osmi černých políček co nejvíce doprava a doplněna o další černá políčka určená horní legendou. Červená políčka ukazují konflikt s legendou předposledního řádku.

33

34


Obrázek 24: Metoda řešení pomocí legendy více řádku najednou použita 1x (zdroj griddlers.net [1])

Jediná možnost odstranění konfliktu je vyplnit posledních 6 políček (označených křížkem) barvou pozadí. Opakuji předešlý postup a umístím skupinu co nejvíce doprava k políčkům barvy pozadí. Po doplnění políček určených horní legendou opět nastane konflikt (obrázek 25), který se odstraní vyplněním posledních dvou políček (označených křížkem) barvou pozadí.


Stejnou úvahou, kdy umístím skupinu co nejvíce vlevo, zjistím, že první tři políčka posledního řádku (označené křížkem) musí být barvy pozadí (obrázek 26).

5.8. KOMPLEXNÍ LOGIKA


Nyní umístím část skupiny do devíti zbylých neurčených políček (obrázek 27).

Obrázek 27: Výsledek opakovaného použití metody na jeden řádek (zdroj griddlers.net [1])

5.8 Komplexní logika Další velmi užitečná metoda využívá pro určení políček komplexní logiku. Na příkladech ze serveru griddlers.net budu demonstrovat její aplikaci. Podle legendy řádku musí černý čtvereček v řádku a) obrázku 28 patřit některému ze samostatných čtverečků nebo černé dvojici. Obě možnosti jsou znázorněny v řádku b) a c) obrázku 28. V obou variantách je čtvereček vpravo od určeného černého prázdný (řádek d)). Znázorněny byly všechny možnosti, a proto mohu čtvereček vyplnit barvou pozadí.

35

36


a) b) c) d) Obrázek 28: Komplexní logika (zdroj griddlers.net [1])

Stejnou úvahu použiju i v dalším příkladu. Podle legendy lze spočítat, že první černý čtverec na řádku a) obrázku 29, je buď jeden ze dvou samostatných čtverečků nebo součástí skupiny sedmi černých čtverečků. Obě varianty jsou naznačeny na řádku b) a c) obrázku 29. Políčko vlevo od prvního černého je v obou případech prázdné. Další možnost už není, čtvereček má určitě barvu pozadí. a) b) c) d) Obrázek 29: Další příklad použití komplexní logiky (zdroj griddlers.net [1])

5.9 Metoda vylučování barev Metoda vylučování barev je založena na úvaze, že vybraná barva musí nebo naopak nesmí být na některých políčkách. Ve srovnání s předchozími metodami se začíná výběrem barvy a následně určení políček, na kterých se smí nebo nesmí vyskytovat. Metoda má velmi široké použití a jednotlivé případy se od sebe můžou značně lišit. Jednu z těchto úvah předvedu na následující křížovce. Úvahu začínám s prázdnou mřížkou. Zaměřím se na první řádek. První políčko legendy prvního řádku můžu umístit do prvního nebo do čtvrtého sloupce, protože se vyskytuje jako první políčko legendy těchto sloupců. Pro umístění druhého políčka legendy prvního řádku je pouze jediná možnost a to první políčko třetího sloupce mřížky (obrázek 30). Můžu ho

5.9. METODA VYLUČOVÁNÍ BAREV tedy umístit. Nyní již umístění prvního políčka legendy do čtvrtého sloupce odporuje legendě prvního řádku a musí být umístěno do prvního sloupce. Na obrázku 30 je stav mřížky po této úvaze. Podobnou úvahu lze uplatnit i na následující křížovce. Nejprve se budu zabývat prvním sloupcem mřížky. První políčko legendy ve sloupci je černá trojice. První řádek však neobsahuje žádné takové černé políčko, obsahuje pouze bílo-černá šikmo dělená políčka, Obrázek 30: Použití metody která nemohou být v prvním sloupci. vylučování barev na 1. řádek Z toho je zřejmé, že první políčko prvního sloupce musí být prázdné (obrázek 31). Druhý řádek obsahuje černé políčko stejně tak jako sloupec, nelze tedy určit. U druhého sloupce budu postupovat stejně. Sloupec obsahuje jeden černý čtvereček. Černé čtverečky se v prvním řádku nenachází, proto můžu první políčko druhého sloupce mřížky vyplnit barvou pozadí. Zajímavý je šestý sloupec, jehož první políčko se nenachází v žádném z prvních tří řádků, proto první tři políčka šestého sloupce musí mít barvu pozadí. Výsledek úvahy provedené pro všechny sloupce křížovky je na obrázku 31. Stejnou úvahu mohu opakovat pro zbylé strany křížovky (levá, pravá a dolní).

Obrázek 31: Další použití metody vylučování barev

Pro další případy platí, že v křížovce na neurčených polích nebudou pro přehlednost zobrazovány otazníky jako dosud. Toho bylo dosaženo změnou jediného parametru v konfiguračním souboru. Dále budu označovat políčka černou tečkou, což bude znamenat, že dané políčko může být jen černé nebo mít barvu pozadí. Podobně, na políčkách s červenou tečkou se nemůže vyskytovat černá barva, ale pouze červená barva nebo barva pozadí. Řešení křížovky na obrázku 32: První řádek legendy obsahuje jedno červené políčko, které může být umístěno pouze v osmém sloupci, protože legenda všech 37

38


ostatních sloupců začíná černým políčkem. Tím je dáno umístění pětice červených políček. Zbytek osmého sloupce označím černou tečkou. V prvních a posledních čtyřech sloupcích legendy se žádné červené políčko nevyskytuje, označím je tedy černou tečkou. Políčkem s černou tečkou můžu označit zbytek prvních tří řádků, protože všechna červená pole jsou již umístěna. Další políčka, na kterých určitě nemůže být umístěn červený čtvereček, jsou ve čtvrtém a pátém řádku, protože jejich legenda obsahuje pouze jedinou skupinu červených políček, z nichž je jedno už určené. „Vytečkování“ křížovky umožňuje umístění dalších červených čtverečků do mřížky.

Obrázek 32: Vyznačení čtverečků, na kterých nemůže být červená barva

5.10 Komplexní logika s barvami Další příklad ukazuje, jak vyloučit z políček výskyt některé barvy. Výchozí situace je v řádku a) na obrázku 33. Legenda začíná černým čtverečkem a končí dvojicí černých čtverečků. Na těchto čtverečkách mřížky může být jen černá barva nebo barva pozadí. Označím je černou tečkou (řádek b)). Černý čtvereček patří do jedné z černých skupin. Všechny čtyři varianty umístění čtverečků jsou znázorněny v řádkách c) – f). V ani jednom z případů se na políčkách 7,8 a 12,13 řádku neobjevuje černé políčko. Tato políčka můžu označit červenou tečkou (řádek g)).

5.10. KOMPLEXNÍ LOGIKA S BARVAMI a) b) c) d) e) f) g) Obrázek 33: Komplexní logika s barvami (zdroj griddlers.net [1]) Další příklad vychází ze situace zobrazené v řádku a) obrázku 34. Mezi dvěma políčky, označenými černou tečkou, by mohla být červená políčka. Nejmenší délka červené skupiny políček jsou tři. Ta se však nevejdou mezi políčka označená černou tečkou. Proto i tato dvě vnitřní políčka nemohou být červená, tedy je označím černou tečkou (řádek b)). a) b) Obrázek 34: Další příklad komplexní logiky s barvami (zdroj griddlers.net [1]) Na obrázku 35 jsou daná dvě černá pole oddělená dvěma neurčenými políčky (řádek a)). Ta nemohou být červená, protože všechny červené skupiny v legendě jsou větší než dvě. Nemohou být ani prázdná, protože tím by vznikly 2 za sebou jdoucí skupiny černých políček, což je v rozporu s legendou. Musí být tedy černá (řádek b)). a) b) Obrázek 35: Třetí příklad komplexní logiky s barvami (zdroj griddlers.net [1])

39

40


V posledním příkladě je výchozí situace v řádku a) obrázku 36. První dvě a posledních pět políček nemůže být červených (řádek b)). Skupina dvou černých polí může být buď první dvojice, nebo součást poslední černé trojice. Je nutné podotknout, že této trojici předchází černá skupina o délce jedna, mezi nimiž musí být alespoň jedno prázdné políčko. V řádcích c) – f) jsou zobrazeny jednotlivé možnosti umístění políček ve mřížce. Všechny varianty ukazují, že dvě pole vlevo od černé dvojice nemohou být červená (řádek g)). a) b) c) d) e) f) g) Obrázek 36: Čtvrtý příklad komplexní logiky s barvami (zdroj griddlers.net [1]) Tímto končí přehled základních i pokročilých metod řešení malovaných křížovek. Jistě existuje mnoho typů úvah, které zde nebyly vyjmenovány a na které si musí každý luštitel přijít sám. Za závěr této kapitoly bych chtěl podotknout, že není jednoduché poznat, která metoda na vybraný řádek bude fungovat a zda vůbec nějaká. Také je velký rozdíl mezi tím znát pokročilé metody řešení a používat je.

Kapitola 6

Implementovaný algoritmus řešení Griddlerů Pro řešení Griddlerů jsem naprogramoval několik různých metod. Budou popsány dále. Pokud všechny tyto metody selžou, je možné použít algoritmus, který zkouší dosadit políčka „hrubou silou“. Malovaná křížovka by měla mít pouze jedno řešení, především proto, aby ji bylo možné vyřešit sérií logických úvah. Stejně jako u Sudoku však lze vytvořit Griddler s více než jedním řešením. Na obrázku 37 je vidět, že i křížovka 2x2 může mít více než jedno řešení. Každá větší křížovka, jejíž částí je křížovka na obrázku 37, má také více řešení (obrázek 38). Obecně se mohou jednotlivá řešení i výrazně lišit.

Obrázek 37: Dvě řešení křížovky velikosti 2x2

Obrázek 38: Křížovka 4x4 obsahující křížovku 2x2 z obrázku 37

41

42

KAPITOLA 6. IMPLEMENTOVANÝ ALGORITMUS ŘEŠENÍ GRIDDLERŮ

Zjistit počet řešení křížovky není snadná úloha. Navrhl jsem řešící rozhraní, které dokáže vyluštit i křížovky, které mají více řešení. Spustí-li uživatel algoritmus na řešení křížovky, program nejprve ověří pomocí statusů řádků a sloupců, zda křížovka již není vyřešená. Pokud ano, nahradí se zbylá neurčená políčka v řádcích a sloupcích políčky barvy pozadí a algoritmus skončí. V opačném případě se postupně spouštějí jednotlivé metody řešení. Nejprve se uplatní metody popsané v 5.2 a 5.3, které vyplní jednoznačně nebo částečně určené řádky a sloupce. Následně dojde k nahrazení všech zbylých neurčených polí u jednoznačně určených řádků a sloupců za barvu pozadí (metoda 5.4). Je-li křížovka vyřešena, algoritmus skončí. Další metoda pracuje postupně se všemi řádky a sloupci. Každý řádek rozdělí na několik částí. Dělícím znakem je jedno nebo více políček barvy pozadí, která nebudou patřit do žádné části. Zároveň jsou tyto části ještě rozděleny na menší barevnými přechody (dvě bezprostředně sousedící barevná políčka různých barev). Neurčené políčko, sousedící s barevným políčkem, se nepovažuje za barevný přechod. Algoritmus zjistí nejmenší číslo v legendě příslušného řádku nebo sloupce. Všechny kratší části než je toto číslo vyplní barvou pozadí, protože do nich podle legendy nelze umístit žádnou skupinu barevných políček (obrázek 39).

Obrázek 39: Rozdělení řádku na části Následně se provede kontrola, zda do některé části nemůže být vepsána více než jedna skupina sousedních políček z legendy. V případě, že do každé části řádku patří právě jedna skupina políček, se na každou část aplikuje metoda zjednodušeného překrývajícího se počítání (popsaná v kapitole 5.3). Dále se v každé části provede doplnění částečně určených oblastí stejného typu jako na obrázku 40.

Obrázek 40: Částečně určené oblasti algoritmem

Podobný algoritmus jsem napsal i pro případ, že do některé části lze umístit více skupinek z legendy. Ten se však zabýval řešením dalších speciálních případů těchto částí, byl proto relativně složitý a v některých speciálních případech vykazoval nepředvídatelné chování. Jeho funkci však plně nahradí další algoritmus, proto jsem tuto část z řešícího procesu vyřadil.

KAPITOLA 6. IMPLEMENTOVANÝ ALGORITMUS ŘEŠENÍ GRIDDLERŮ Výše popsaný algoritmus se následně provede ještě jednou s tím rozdílem, že pokud zpracovává nějaký řádek a doplní některé políčko, přidá číslo sloupce tohoto políčka do fronty připravené ke zpracování. Řádek se zpracuje až do konce a pak opět znovu od začátku, dokud celý průchod řádkem nepřinesl žádné doplnění. Se zpracováním sloupců je tomu obdobně. Po průchodu všech řádků a sloupců se začnou znovu zpracovávat řádky a sloupce, jejichž čísla jsou uložená ve frontě, protože další doplnění políček lze očekávat pouze v těch řádcích a sloupcích. Po zpracování řádku / sloupce se vymaže jeho číslo z fronty. Při doplnění dalších políček jsou čísla změněných řádků a sloupců jsou opět přidávána do fronty. Proces zpracování řádků a sloupců se opakuje, dokud není fronta prázdná. Nakonec se ověří, zda nedošlo k úplnému vyřešení křížovky. Řešení pokračuje třetí metodou, která využívá stejné regulární výrazy, jako se používají pro zjištění statusu řádku či sloupce. Tato metoda by bez problémů nahradila všechny předchozí, ale počítání regulárních výrazů trvá dlouho. Pro zkrácení času řešení se proto nejprve provedou první dvě metody a následně až metoda využívající regulární výrazy. Před samotným spuštěním metody jsou pro levou a pro horní legendu vytvořena dvoudimenzionální pole hodnot bool. Jedním rozměrem je výška / šířka křížovky, druhým počet barev políček v křížovce. Na obrázku 41 Obrázek 41: Pole barev je výška křížovky 3 a počet barev v křížovce vyskytujících se v křížovce dvě – pole je rozměru 3x2. Každý sloupec tohoto pole odpovídá jedné barvě. Prvek pole má hodnotu true, pokud se v řádku vyskytuje příslušná barva. Jinak má hodnotu false. Analogicky pro horní legendu. Toto pole bude použito v řešícím algoritmu. Algoritmus řešení pomocí regulárních výrazů zpracovává mřížku po řádcích a výpočet se provádí jen na neurčených políčkách. Myšlenka algoritmu je následující: Pokud po vyplnění políčka postupně všemi barvami políček vyskytujícími se v křížovce, vyjde kromě jednoho případu vždy chybný status, musí být políčko vyplněno právě tou barvou, při níž jediné nebyl status chybný. Sloupcové statusy se počítají odděleně od řádkových, a pokud je podmínka splněna alespoň v jedné z těchto dvou skupin, může se políčko vybarvit nechybovou barvou. K urychlení výpočtu se používá předem vytvořené pole barev. Barva, která se současně nenachází v řádku a ve sloupci, se nemůže nacházet ani na vybraném políčku. Oba statusy jsou potom pro vybranou barvu nastaveny jako chybné, aniž by bylo nutné vyhodnocovat regulární výrazy. Tato metoda se opakuje třikrát. Při prvním průchodu se vyplní všechny jasné situace. Druhý průchod se od prvního liší tím, že pokud se v řádku vyplní algoritmem nějaké políčko, je algoritmus rekurentně zavolán na sloupec vyplněného políčka a v řešení řádku se pokračuje až po návratu z rekurze. Obdobně je to s řešením sloupce, kdy je algoritmus volán rekurentně na řádek. Třetí průchod je jen čistící, pro případ, že by v mřížce zbyly nějaké neurčené drobnosti, které by bylo možné algoritmem vyřešit.

43

44

KAPITOLA 6. IMPLEMENTOVANÝ ALGORITMUS ŘEŠENÍ GRIDDLERŮ

Tato metoda vyřeší všechny případy doplnění dalších barevných políček do částečně vyřešeného řádku (metoda 5.6), případy doplnění částečně vyřešeného řádku prázdnými políčky (metoda 5.5), situace, kdy je nutné užít komplexní logiku (metoda 5.8) a jednoduché varianty vylučování barev (metoda 5.9). Řešení složitějších případů vylučování barev není implementováno, protože ani řešící rozhraní neumožňuje přidávat značky určující, že políčko nemá některou barvu. Čtvrtá a zároveň poslední metoda je volaná pouze při volbě Vyřešit s použitím hrubé síly z menu Griddler. Je zde pro případ, kdy předcházející metody nejsou na vyřešení Griddleru dostatečně silné, nebo pokud má Griddler více řešení, a tudíž není dořešitelný logickou úvahou. Tato metoda prochází všechna neurčená políčka a zkouší do nich postupně dosadit všechny barvy políček. V případě nechybového statusu řádku i sloupce se pokusí dořešit Griddler pomocí metody regulárních výrazů. Když nedojde metodou regulárních výrazů k dořešení křížovky nebo není během řešení nalezena chyba, opakuje se rekurentně proces pro další neurčená políčka. Algoritmus se pokouší nalézt všechna řešení křížovky a nekončí nalezením prvního. Nalezená řešení se přidávají do zásobníku. Pro řešení může být stanoven limit. Limit je načítán z konfiguračního souboru. Chybí-li v konfiguračním souboru, je nastaven na Long.MaxValue. Jedná se o počet barev křížovky umocněný na počet políček, určených hrubou silou. Tento limit nesmí být překročen. Pokud bylo dosaženo limitu a algoritmus by musel dosadit všechny možnosti do dalšího pole, je zabráněno dalšímu zanoření do rekurze a pokračuje se v řešení s následující kombinací dosazených polí. Uživatel je o této skutečnosti informován. Algoritmus o své činnosti podá uživateli zprávu (zda bylo nebo nebylo řešení nalezeno a v případě vyřešení křížovky také počet řešení). Je-li řešení nalezeno, chová se program stejně jako v případě vyluštění Griddleru uživatelem (je nabídnuto zobrazení náhledu). Pokud má křížovka více řešení, je zobrazeno menu Řešení s volbami Zobraz následující a Zobraz předchozí, umožňující přepínání mezi jednotlivými řešeními. Ta se přesouvají mezi dvěma zásobníky a je zobrazováno vždy řešení na vrcholu prvního z nich. Mezi řešeními se lze přepínat i v módu náhledu řešení.

Kapitola 7

Testování Aplikace byla při vývoji průběžně testována. Nejprve byly testovány a opravovány jednotlivé moduly tak, jak byly postupně vytvářeny: správa barev, mód řešení křížovek, mód úprav, řešící algoritmus a mód náhledu. Při spojování jednotlivých modulů bylo testováno, zda přidáním nového nedošlo k narušení již existující funkcionality. Následně byla testována i celá aplikace. Testování nemůže nikdy odhalit 100 % chyb v programu, je však velmi důležité. Seznam Griddlerů, na kterých byla aplikace testována, je uveden v Dodatku B. Většina byla vytvořena podle předlohy křížovek na serveru griddlers.net [1] a přepsána do XML formátu podporovaného mým programem. Časová náročnost takového přepisu je velká, proto byly vybrány pouze křížovky malé a střední velikosti. Jak již bylo řečeno v kapitole o jiných aplikacích, umožňujících řešení Griddlerů, program Malované křížovky 0.9 [2] vyřeší většinu ze 14 s ním distribuovaných křížovek jen zčásti. Můj program tyto křížovky vyřeší bez problémů. Grafické prostředí, uživatelská příjemnost a hlavně možnosti poskytované mým programem jsou nesrovnatelně lepší. Aplikace na serveru griddlers.net [1] je velmi rozsáhlý projekt, obsahující tisíce křížovek, které mohou uživatelé řešit. Na rozdíl od mého programu neumožňuje tyto křížovky automaticky vyřešit. Zaměřím-li se na rozhraní, umožňující vytváření a řešení křížovek, poskytuje aplikace na serveru oproti mé některé možnosti navíc, např. označení políčka křížkem či kolečkem, vyplnění větší oblasti najednou, volbu velikosti štětce při kreslení nebo kreslení dělených políček pomocí klávesnice. Rozhraní pro řešení Griddlerů na serveru nemá žádné menu, volby se provádějí pomocí tlačítek. Výhodou mé aplikace je dobře uspořádané menu pro vytváření i pro řešení křížovek a možnost použít text odlišné barvy na každé části děleného políčka.

45

46

KAPITOLA 7. TESTOVÁNÍ

Kapitola 8

Závěr Úkolem této práce bylo navrhnout a implementovat algoritmus pro řešení Malovaných křížovek. Součástí měl být editor, který uživateli umožní vytvořit obrázek, k němuž vygeneruje legendu a následně ho umožní uložit. Hlavním přínosem práce je poměrně chytrý algoritmus na řešení křížovek. Zvládne napodobit velké množství úvah, používaných při klasickém řešení křížovek. V práci je popsáno deset technik řešení křížovek, z nichž jsem v programu plně implementoval šest a jednu zčásti. Implementaci některých metod jsem realizoval pomocí regulárních výrazů, což se ukázalo jako velmi silná zbraň. Navíc jsem přidal metodu používající „hrubou sílu“, která může v některých případech pomoci křížovku dořešit. Tato metoda se při každém kroku kombinuje s ostatními implementovanými metodami. Prostředí pro řešení křížovek nabízí uživateli velké množství užitečných funkcí. Umožňuje měnit měřítko křížovky, měnit barvy mřížky, zvýrazňuje vybraný řádek a sloupec, jejichž legendu zobrazuje v dolní resp. pravé části okna, umožňuje jednotlivé vyplnění políček vrátit zpět či je provést znovu, či celou mřížku vymazat. Aktuální stav při řešení křížovky je pro přehled zobrazen jako miniatura. Výběr barvy pro kreslení do křížovky může být realizován přes paletu, obsahující všechny barvy políček křížovky nebo kliknutím na konkrétní políčko legendy. Aplikace také obsahuje šikovnou nápovědu. Prostředí editoru poskytuje nejen základní způsob vytváření křížovky požadovaný zadáním práce, kdy generuje legendu k obrázku namalovanému do mřížky, ale i druhý způsob, kdy uživatel vyplňuje přímo legendu, aniž by předem znal obrázek křížovky. Dialogy správy barev umožňují přidávat, mazat a upravovat políčka křížovky. Lze v nich upravovat jednotlivé odstíny barev nebo úplně změnit typ políčka a barvy, ze kterých se skládá. Další funkcionalitou, kterou poskytuje editor navíc, je možnost změnit velikost křížovky. Ve vývoji aplikace je možné pokračovat přidáváním dalších funkcionalit a vylepšováním těch současných. Pozornost může být zaměřena na vytvoření dialogu, umožňujícího vybírat křížovky pro řešení pomocí různých kritérií (výška, šířka, počet základních barev, počet barev políček, klíčových slov, či tematický výběr). Dále může být vylepšeno rozhraní pro řešení křížovek např. možností přidat pomocné značky, které 47

48

KAPITOLA 8. ZÁVĚR

vylučují použití některé barvy na daném políčku. Pro některé uživatele může být také příjemná možnost výběru barev pomocí klávesnice. Další oblastí může být vylepšení řešícího algoritmu implementováním dalších metod řešení, aby se omezila nutnost použití „hrubé síly“.

Literatura [1] Griddlers Net – server věnovaný Griddlerům http://www.griddlers.net/ [2] Program Malované křížovky 0.9 http://www.slunecnice.cz/sw/malovane-krizovky-tokarcik/ [3] Vývojové prostředí Microsoft Visual Studio 2008 http://www.microsoft.com/cze/msdn/produkty/vstudio/default.mspx [4] První přednáška z předmětu Vývoj aplikací v prostředí .NET http://dcenet.felk.cvut.cz/van/pdf/van2009pr1.pdf [5] DTD – Definice typu dokumentu http://www.kosek.cz/clanky/xml/xml-01.html http://www.kosek.cz/clanky/xml/xml-02.html [6] Struktura INI souboru http://en.wikipedia.org/wiki/INI_file [7] Návody na řešení Griddlerů http://www.griddlers.net/pages/gexample1 http://www.griddlers.net/pages/gexample2 http://www.griddlers.net/pages/gexample3 http://www.griddlers.net/pages/gexample4 http://www.griddlers.net/pages/gexample5 http://www.griddlers.net/pages/gexample6 http://www.griddlers.net/pages/gexample7 http://www.griddlers.net/pages/gexample8 49

50

LITERATURA

Dodatek A

Příklad souboru křížovky a DTD Krb <size width="5" height="5" />
red="255" green="255" blue="255" /> red="102" green="102" blue="102" /> red="255" green="153" blue="0" /> red="255" green="255" blue="255" /> red="0" green="0" blue="0" />

basecolor="0" textcolor="0" />

51

52

DODATEK A. PŘÍKLAD SOUBORU KŘÍŽOVKY A DTD

<save>0#3#1#1#1#1#1#1#0#2#0#0#0#2#2#1#1#1#0#2#0#4#1#1#1# <mouse-buttons left-button="1" right-button="0" />

Ukázka kódu 3: Příklad souboru křížovky


Ukázka kódu 4: DTD křížovek

53

54


Dodatek B

Seznam křížovek Šířka

Výška

5 5 5 5 5 5 5 5 5 5 5 5 5 5 6 7 10 10 10 10 10 10 10 10 10 10 13 15

5 5 5 5 5 5 5 5 5 5 5 5 10 10 5 7 5 5 5 10 10 10 10 10 15 15 18 10

Základní barvy 2 2 2 2 2 2 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 3 2 2 2 2

Barvy políček 2 2 2 2 2 6 3 3 5 6 6 6 2 2 2 2 2 2 2 2 2 2 2 14 2 2 6 2

55

Název Křížovky Jelen Kaktus Krab Větrník Více řešení (2) Jin Jang Krb Pinky Krb Neřešitelná převržená plachetnice Nevalidní soubor Převržená plachetnice Otazník Tulipán Neřešitelný Více řešení (34) Autobus Nákladní vlak Želva Čaj Jablko Květina Srdce Labuť Běžec Papoušek Čarodějnice Traktor

56 DODATEK B. SEZNAM KŘÍŽOVEK Šířka

Výška

15 15 15 15 15 15 15 20 20 20 20 20 20 20 20 22 25 25 25 25 35 35

15 15 15 15 15 15 20 10 16 20 20 20 25 25 30 22 25 25 25 25 35 35

Základní barvy 2 2 2 2 3 4 5 6 2 2 2 2 2 2 2 7 4 5 5 6 2 2

Barvy políček 2 2 2 6 3 4 5 6 6 2 2 6 2 6 2 15 4 5 18 6 2 2

Název Křížovky Krab Mravenec Želva Taneční pár Dolar Beruška Žába Auto Kachnička Holka s kloboukem Koala Houby Pirát Fotoaparát Lebka Iluze Papoušek Medúza Fénix Květina Orel Pamatujete na Gizma?

Tabulka 1: Seznam křížovek

Dodatek C

Uživatelská a instalační příručka Pro spuštění aplikace je nutné mít nainstalovaný .NET Framework 3.5. Ten je integrovanou součástí všech Windows od verze Vista. Do verzí XP a starších je ho možné zdarma doinstalovat. Instalační program Setup.exe umístěný na CD v adresáři Install aplikaci nainstaluje. V případě absence Frameworku ho automaticky stáhne z internetu a nainstaluje ho. Instalátor Frameworku lze také získat např. na adrese http://www.stahuj.centrum.cz/vyvojove_nastroje/ostatni/net-framework/ . Ovládání programu je popsáno v jednotlivých položkách aplikačního menu Nápověda. Nápověda Griddlers vysvětluje uživateli pravidla pro řešení Griddlerů a popisuje základní funkce pro ovládání programu. Nápověda Jak řešit uvádí základní metody řešení Griddlerů. Nápověda Editor popisuje základní funkce editoru, sloužící pro vytvoření nové křížovky.

57

58

DODATEK C. UŽIVATELSKÁ A INSTALAČNÍ PŘÍRUČKA

Dodatek D

Obsah přiloženého CD Install

adresář obsahující instalační program

Ruzne

adresář obsahující soubory nápovědy, DTD a konfigurační soubor

Text

adresář obsahující text bakalářské práce ve formátu PDF a DOC

Zdrojove kody

adresář obsahující celý C# projekt, včetně všech zdrojových kódů

59

60

DODATEK D. OBSAH PŘILOŽENÉHO CD

Řešení Malovaných křížovek

Recommend Documents