České vysoké učení technické v Praze Fakulta elektrotechnická
Bakalářská práce
Generátor sudoku Jindřich Mašek
Vedoucí práce: Prof. Ing. Pavel Tvrdík, CSc. Studijní program: Elektrotechnika a informatika strukturovaný bakalářský Obor: Výpočetní technika červenec 2007
Prohlášení Prohlašuji, že jsem svou bakalářskou 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 20. 8. 2007 ---------------------------------------------
i
ii
Abstrakt Cílem této práce je vytvořit program, který vygeneruje sudoku úlohu tak, aby měla jednoznačné řešení. Komunikovat s programem se bude pomocí internetového prohlížeče přes webové rozhraní. Vstupem bude maximální počet děr, které mají být ve výsledné sudoku úloze. Výstupem pak sudoku úloha s počtem děr menším nebo rovným požadovanému. V práci je vysvětleno, jak program funguje, jaké algoritmy používá a proč jsem si je zvolil.
Abstract The intention of this work is implement program for generating sudoku puzzle having unique solution. Communication with the program is provided by internet browser through the web interface. Input of the program is maximal number of holes that can be in final sudoku puzzle. Output is sudoku puzzle with number of holes less or equal to requested number. In this work is described how program works, what algorithms uses and why have I chosen them.
iii
iv
Obsah 1. Úvod ....................................................................................................................................... 1 2. Sudoku .................................................................................................................................... 1 2.1. Vymezení pojmů ............................................................................................................. 2 3. Analýza úlohy ........................................................................................................................ 3 3.1. Co je třeba implementovat .............................................................................................. 3 3.2. Volba programovacího jazyka ........................................................................................ 3 4. Generátor sudoku úlohy, úplného pole sudoku a možného postupu řešení ........................... 4 4.1. Volba algoritmů............................................................................................................... 4 4.2. Popis algoritmů ............................................................................................................... 5 4.2.1. Generace sudoku úlohy za použití algoritmu řešení pomocí logiky ........................ 5 4.2.2. Generování možného postupu řešení sudoku úlohy ................................................. 6 4.2.3. Generování úplného pole sudoku rekurzivním algoritmem ..................................... 6 4.3. Metody řešení .................................................................................................................. 6 4.4. Implementace .................................................................................................................. 9 4.4.1. Funkce int main() - hlavní funkce generátoru sudoku ................................... 10 4.4.2. Funkce bool one_turn() - provádějící jedno kolo generování ..................... 11 4.4.3. Metoda make_field() a bool make_cell(vector
&,int,int) - generující úplné pole sudoku ......................................................................................... 13 4.4.4. Funkce bool make_hole(int,int) - rozhodující zdali lze na daném místě udělat díru ......................................................................................................................... 15 4.4.5. Funkce bool make_clues(int,int) - aplikující řešící metody na buňku . 16 4.4.6. Funkce bool make_hole_sol() a bool make_clues_sol(int,int) - generující postup řešení ................................................................................................. 18 5. Rozhraní ............................................................................................................................... 20 5.1. Volba použitých technik................................................................................................ 20 5.2. Internetové stránky ........................................................................................................ 21 5.3. Internetová verze ........................................................................................................... 22 5.3.1. Přenášené bloky...................................................................................................... 23 5.3.2. Přenos dat - Implementace ..................................................................................... 24 5.3.3. Funkce bool vypis_sock(stringstream&) - Kontrolující a upravující výstupní data před předáním dalším funkcím .................................................................. 26 5.3.4. Funkce bool server_snd(char *, int) - Posílající data na stránku .... 27 5.3.5. Internetová stránka index.php ................................................................................ 28 5.3.6. Internetová stránka send.php .................................................................................. 28 5.4. Lokální verze ................................................................................................................. 29 5.4.1. Html žádosti ........................................................................................................... 29 5.4.2. Zpracování žádostí ................................................................................................. 31 5.4.3. Internetová stránka index.html ............................................................................... 34 5.4.4. Internetová stránka send.html ................................................................................ 34 6. Testování .............................................................................................................................. 34 7. Závěr..................................................................................................................................... 37 8. Seznam použité literatury ..................................................................................................... 39 A) Uživatelská příručka ........................................................................................................... 41 A.1 Instalace a spuštění ........................................................................................................ 41 A.1.1 Internetová verze .................................................................................................... 41 A.1.2 Lokální verze .......................................................................................................... 41 A.2 Obsluha .......................................................................................................................... 41 B) Obsah přiloženého CD ........................................................................................................ 43
v
vi
1. Úvod Sudoku je v dnešní době dobře známý pojem. Je to hra, která dokázala zaujmout velké množství lidí. Osobně jsem ho před započetím této práce nikdy neluštil. Jen jsem věděl, že sudoku existuje a znal jsem zhruba pravidla. Proto jsem také věděl, že jde o zajímavý matematický problém a protože mě matematika baví, není se čemu divit, že mě téma této bakalářské práce zaujalo. Navíc se jednalo o úlohu zaměřenou hlavně na programování, které je mi z různých dovedností, které jsem se během studia naučil, nejbližší. Nyní tedy k tomu, co je třeba udělat. Připomeňme si zadání: „Prostudujte známé metody pro generování a řešení hry sudoku. Navrhněte a implementujte co nejobecnější algoritmus generování zadání sudoku úlohy, aby měla jednoznačné řešení, jak z hlediska výsledku, tak z hlediska postupu vyplňování prázdných políček. Vytvořte pro tento generátor jednoduché webové rozhraní.“ Nejprve se proto seznámíme s hrou sudoku jako takovou, řekneme si jaká má pravidla a vysvětlíme některé pojmy, používané v tomto textu. Poté následuje návrh generátoru sudoku. Po krátké úvodní analýze, kdy si vyjasníme, co je třeba naprogramovat a jaký programovací jazyk je k tomu vhodný, se další popis dělí na dvě části. Jedna část se zabývá samotným generováním a druhá se zabývá vstupním/výstupním rozhraním. V první části začneme zamyšlením, jaký typ algoritmu použijeme. Potom naznačíme, jak budou zvolené algoritmy vykonávány a nakonec se podíváme na jejich samotnou implementaci. Ve druhé části o rozhraní se nejprve rozhodneme, jaké techniky při budování rozhraní použijeme. Tyto techniky budou dvě, a proto budou také dvě verze programu. Nejdříve krátce pohovoříme o tom, co mají obě verze rozhraní společné a pak se text dále rozdělí na sekce lokální a internetovou. Každá sekce obsahuje bližší vysvětlení, jak dané rozhraní pracuje a poté jak je implementováno v sudoku generátoru. Dále jsou popsány internetové stránky, které rozhraní využívají při komunikaci s internetovým prohlížečem. Nakonec popíšeme, jak probíhalo testování a obsah a výsledek této úlohy shrneme v závěru.
2. Sudoku Hru sudoku vymyslel Howard Garns ,74letý architekt a tvůrce rébusů z Indiany. Poprvé byla vydána v roce 1979 v Dell Magazines pod názvem „Number Place“. Garns zemřel v roce 1989, aniž by viděl, jaké celosvětové obliby jeho hra dosáhla. Hra byla v roce 1984 uvedena v Japonsku pod názvem Suuji wa dokushin ni kagiru, což může být přeloženo jako „čísla musí být samotná“ nebo „čísla jsou omezena na jeden výskyt“. Později byl název zkrácen na sudoku a ujal se i ve světě. Obecně je sudoku pole o rozměrech n2 × n2 logicky dělených na boxy o rozměrech n × n. Tato práce se zaměřuje na klasické sudoku tj. n=3. V roce 2005 spočítal Bertram Felgenhauer, že počet různých polí tohoto sudoku je 6 670 903 752 021 072 936 960. Minimální počet vodítek, aby úloha měla stále jednoznačné řešení, je 17 a pokud má být pole symetrické, pak 18. Cílem hry je doplnit chybějící čísla 1 až 9 v předem dané předvyplněné tabulce (sudoku úloze). Tato tabulka je rozdělena na 9x9 buněk, které se dělí do 9 logických čtverců (boxů) o rozměrech 3x3 buňky. Na obrázcích 1 a 2 je toto dělení znázorněno tlustou čarou.
1
1 2 3 4 5 6 7 8 9
1 1 5 7 6 8 4 9 2 3
2 2 4 8 9 3 5 1 6 7
3 9 6 3 1 7 2 4 8 5
4 6 8 5 7 9 1 2 3 4
5 3 1 2 4 6 8 5 7 9
6 7 9 4 5 2 3 6 1 8
7 5 7 9 8 1 6 3 4 2
8 8 2 1 3 4 9 7 5 6
9 4 3 6 2 5 7 8 9 1
Obrázek 1 - Úplné pole sudoku
1 2 3 4 5 6 7 8 9 1 9 6 2 1 7 3 8 4 6 4 7 5 3 5 7 9 1 6 4 2 3 6 7 2 6 8 8 6 4 5 9 8 Obrázek 2 - Sudoku úloha
K předem vyplněným číslům je potřeba doplnit další čísla tak, aby platilo, že v každé řadě, v každém sloupci a v každém z devíti čtverců byla použita vždy všechna čísla jedna až devět. Pořadí čísel není důležité. Čísla se nesmí opakovat v žádném sloupci, řadě nebo boxu. Obtížnost Sudoku není dána počtem nepředvyplněných políček, ale jejich vzájemnými vazbami, které na první pohled nejsou vidět. Těžká sudoku mohou průměrně zkušenému luštiteli zabrat kolem 15 – 60 minut. 2.1. Vymezení pojmů Text se snažím psát tak, aby i laik pochopil, o co se jedná. I když tu jde převážně o popisování práce programu, jsou algoritmy nejdříve vysvětleny pomocí logiky, blízké každému člověku bez ohledu na jeho znalosti. Při bližším vysvětlení, jak sudoku generátor dané algoritmy vykonává, jsem však nucen uchýlit se k používání pojmů z programovacích jazyků jako jsou funkce, datové typy, proměnné a podobně. Tyto pojmy tu však vysvětlovat nebudu, protože cílem této práce není výuka programování. Laik proto tyto pasáže pravděpodobně zcela nepochopí. Uvádím tu však několik neodborných pojmů, používaných dále v textu, aby nedocházelo k nedorozuměním, o čem se vlastně píše. Hra sudoku - je obecně hra jako taková. Pole sudoku - je obecné pole hry sudoku (když hovoříme o poli sudoku a není důležité, jestli v něm jsou díry nebo ne). Úplné pole sudoku - je kompletně vyplněné pole sudoku (tzn. bez děr). Sudoku úloha - je pole sudoku obsahující díry (sám název napovídá, že je to něco k řešení). Buňka - je jedno políčko (nezáleží, jestli vyplněné nebo prázdné), pole sudoku má 81 buněk. Kandidát - kandidát buňky je celé číslo z intervalu 1 až 9, které mohu do buňky doplnit, aby nedošlo k porušení pravidel hry sudoku vzhledem k již vyplněným buňkám. Jedna prázdná buňka mívá více kandidátů. Někdy se pro usnadnění zapisují malými číslicemi do prázdných buněk a říká se jim vodítka. Box - čtverec o rozměrech 3x3 buňky. Standardní pole sudoku je logicky členěno na 9 boxů. Tento výraz již patří spíše do překladové sekce, ale jelikož jsem si ho zvykl používat i v běžném českém textu (namísto používání slova čtverec apod.), tak ho uvádím raději zde.
2
Generátor sudoku - program jehož vytvoření bylo cílem této práce. Program jsem tak nazval, protože generuje jak výchozí úplné pole sudoku, tak i sudoku úlohu a nakonec i možný postup řešení. Odvodit díru (buňku) - Znamená že pomocí řešících metod odvodíme číslo, které jako jediné můžeme vepsat do prázdné buňky a tím díru odstranit. Locked Candidates X – Souhrnné označení řešících metod Locked Candidates a Locked Candidates 2. Při studování podkladů jsem často narazil na literaturu v cizím jazyce, a proto se může stát, že zvláště při procházení komentářů ke zdrojovému kódu narazíte na některé cizí výrazy. Proto zde raději uvedu překlad: Row – řádek Column – sloupec Cell – buňka (políčko) House – Je buď řádek, sloupec nebo box. Prostě vše, co může určitou hodnotu obsahovat pouze jednou Peers – peers jedné buňky je její okolí které se jí týká, tj. řádek, sloupec a box, do kterých buňka náleží. (rozdíl mezi house a peers je ten, že house je vlastně podmnožinou peers) Candidate – kandidát buňky Clue - vodítko Některé cizí výrazy, jako například názvy řešících metod, nepřekládám, protože jejich překlad většinou nenapovídá nic o jejich principu a jen by čtenáře více mátl.
3. Analýza úlohy 3.1. Co je třeba implementovat Dle zadání máme vytvořit program, jehož výstupem bude sudoku úloha, mající jednoznačné řešení. Musíme tedy naprogramovat generování této sudoku úlohy. Ačkoli to v zadání není, dám si ještě za cíl, aby spolu se sudoku úlohou byl vytvořen i možný postup řešení této úlohy. Musíme tedy naprogramovat generátor postupu řešení. Vstup programu není nijak specifikován. Proto si určím sám, že vstupem bude maximální počet děr, které mohou být ve výsledné sudoku úloze (avšak ne minimální). Pokud pro generování sudoku úlohy zvolím algoritmus, založený na postupném odebírání čísel z úplného pole sudoku, budu muset naprogramovat i generátor tohoto výchozího pole. Další věc, kterou nám zadání předepisuje, je vytvoření webového rozhraní. 3.2. Volba programovacího jazyka Vytvoření generátorů sudoku úlohy, úplného pole sudoku a postupu řešení, nemá žádné specifické požadavky a můžu proto zvolit jakýkoliv jazyk. Pro tvorbu webového rozhraní by bylo vhodné použít jazyk, který je určen pro práci s webem. V úvahu přicházejí jazyky javascript a PHP. Tyto jazyky mají výhodu, že utvářejí přímo webovou stránku a vytvoření webového rozhraní by bylo tedy velmi snadné. Na druhou stranu to jsou jazyky interpretační, a proto jsou pomalejší než klasické kompilované programy. PHP navíc vyžaduje k chodu webový server a javascript zas podporu ze strany prohlížeče. Oba jazyky jsem přímo nestudoval a proto je znám jen okrajově. Po zvážení výhod a nevýhod jsem se rozhodl pro jazyk C++. Je to jazyk kompilační a pro tuto úlohu, která bude pravděpodobně
3
vykonávat mnoho výpočtů, se hodí. S tímto jazykem jsem se také v průběhu studia dobře seznámil.
4. Generátor sudoku úlohy, úplného pole sudoku a možného postupu řešení 4.1. Volba algoritmů Pro generování sudoku úlohy můžeme volit jeden ze dvou postupů. Buď začít s úplným polem sudoku a podle určitého algoritmu v něm vytvářet díry tak, aby sudoku úloha měla stále jednoznačné řešení, nebo naopak začít s prázdným polem a přidávat prvky, dokud úloha nebude mít jednoznačné řešení. Rozhodl jsem se pro první postup, jelikož mi přijde jednodušší jak na pochopení, tak na implementaci. Pro vytvoření sudoku úlohy mohu dále volit ze dvou typů algoritmů. Na jedné straně hrubá síla a rekurzivní algoritmy, na straně druhé logické postupy simulující lidského řešitele. Jako další krok je tedy nutné zvolit si jednu z těchto cest. Zadáním bylo vytvořit sudoku úlohu, která by měla jednoznačné řešení. Toho rekurzivní algoritmy dosahují tak, že vezmou úplné pole sudoku, udělají do něj díru a pak vyzkouší všechny možnosti doplnění čísel do buněk tak, aby nebyly v rozporu s pravidly hry sudoku. Tak naleznou všechna možná řešení. Pokud je právě jedno, udělají další díru a vše se opakuje. Pokud ne, díra na tomto místě nebude vytvořena a zkusí se místo jiné. Výhoda těchto algoritmů je relativní jednoduchost a také zde není žádná spojitost s obtížností sudoku a dobou potřebnou k jeho řešení těmito algoritmy. Obtížností se zde myslí obtížnost pro řešení lidmi, tzn., že logické vazby se těžce hledají. Na druhé straně totiž existují sudoku úlohy, které jsou naopak obtížné pro některé algoritmy, využívající hrubou sílu. Řešení těchto úloh může trvat velmi dlouho, což je nevýhoda těchto algoritmů. Takovým příkladem je sudoku úloha na obrázku 3. Má první řádek zcela prázdný, často dochází ke kolizím a program, využívající hrubou sílu, se musí často vracet. Na počítači s procesorem o frekvenci 500Mhz trvalo vyřešení této úlohy 96 minut. Ovšem modernější stroje dokáží i takovéto úlohy vyřešit hrubou silou během pár vteřin a proto jsou tyto algoritmy používány. 1 2 3 4 5 6 7 8 9 1 2 3 8 5 3 1 2 4 5 7 5 4 1 6 9 7 5 7 3 8 2 1 9 4 9 Obrázek 3 - Příklad sudoku úlohy obtížné pro vyřešení hrubou silou
Dalším často používaným algoritmem pro řešení sudoku je „Dancing links“, označovaný také jako DLX, který vymyslel Donald Knuth jako efektivní implementaci jeho Algoritmu X, což je rekurzivní algoritmus, který najde všechna řešení problému 4
úplného pokrytí. Já jsem si ale žádný z těchto algoritmů nezvolil, a proto je zde nebudu podrobně popisovat. Rozhodl jsem se pro druhou cestu a to vymyslet algoritmus, který řeší sudoku úlohu pomocí logiky a napodobuje tak do značné míry lidského řešitele. Jelikož jsem od začátku zamýšlel, že sudoku generátor bude vypisovat také postup řešení namísto jen strohé sudoku úlohy, je volba tohoto algoritmu výhodná, protože na rozdíl od předchozí skupiny algoritmů stačí zaznamenat postup sudoku generátoru a návod na vyluštění je hotov. Použité postupy jsou shodné s těmi lidskými, a proto jsou algoritmy jednoduché na pochopení (avšak implementace již být nemusí). Nevýhodou je, že řešící schopnost závisí na tom, které metody řešení program umí (není-li schopen nalézt složitější logické souvislosti, nemusí vyřešit některé sudoku úlohy, které ale řešení mají). Také čas, potřebný k vyřešení, již závisí na logické obtížnosti sudoku úlohy. Jelikož námi zvolený algoritmus potřebuje pro svou činnost úplné pole sudoku a toto pole není vstupem sudoku generátoru, je třeba vytvořit vlastní generátor tohoto pole. Máme tedy vytvořit funkci, která vyplní 81 buněk čísly podle pravidel hry sudoku. Rozhodl jsem se pro rekurzivní algoritmus, protože není tak složitý na implementaci a pro tento typ úlohy se hodí. 4.2. Popis algoritmů 4.2.1. Generace sudoku úlohy za použití algoritmu řešení pomocí logiky Generátor sudoku používá standardní řešící metody, známé každému středně zdatnému luštiteli sudoku. Tyto metody aplikuje postupně od nejjednodušší po ty složitější a snaží se odvodit číslo, náležící do prázdné buňky. Začínáme s úplným polem sudoku. Představa je taková, že se náhodně vybere buňka. Do této buňky je dočasně udělána díra a zkoumá se, zdali ji lze odvodit danými metodami, tj. zdali dosáhne statusu odvoditelná (neluštíme tedy celou sudoku úlohu až do konce, ale stačí odvodit jen vybranou buňku). Ne vždy jde buňka odvodit přímo, proto procházím pole sudoku zleva doprava, odshora dolů a zkouším doplnit každou prázdnou buňku. Pokud se mi to nějakou metodou povedlo, nebo se alespoň změnily kandidáty, pak se celá procedura opakuje ještě jednou. Pokud se při procházení pole již nadále nemění a daná buňka stále nebyla odvozena, nemůže být odebrána. Proč by to mělo fungovat? Udělám náznak důkazu na základě logické úvahy. Ve výchozím stavu v čase 0 máme úplné pole sudoku, na které by se dalo pohlížet jako na sudoku úlohu s počtem děr 0 a jednoznačným řešením. Dále platí pravidlo: Díru vytvořím, jen když dokážu zpětně odvodit číslo, které na její místo patří (zpětným odvozením se myslí, že do dané buňky mohu zapsat pouze jediné číslo a žádné jiné, abych neporušil pravidla hry sudoku). Proto pokud v čase 1 mám vytvořenu první díru, mám jistotu, že mohu logicky odvodit její hodnotu a dostat se do výchozího stavu. V čase 2, kdy mám v poli sudoku již 2 díry, mám jistotu, že pro díru, kterou jsem právě vytvořil, můžu logicky odvodit číslo, které do ní patří. Tím bych se dostal do stavu v čase 1, ze kterého, jak sem již dokázal, musí být způsob, jak se dostat do výchozího stavu. Tedy i ze stavu v čase 2 se lze vždy dostat do výchozího stavu. Obdobně bych mohl teoreticky pokračovat až do stavu v čase 64 (maximální počet děr, které může mít sudoku úloha, aby stále měla jednoznačné řešení). Pokud je vždy dodržena podmínka: Díru vytvořím, jen když dokážu zpětně odvodit číslo, které na její místo patří, mám vždy zaručeno, že se dostanu do předchozího stavu a z něho zas do předchozího atd. až k výchozímu stavu, který má jednoznačné řešení a tudíž i sudoku úloha v libovolném čase má jednoznačné řešení. Řečeno jinak, musím zajistit, aby buňka, kterou chci právě odebrat, nebyla klíčová při odvození buňky, která je klíčová při
5
odvození buňky, kterou chci právě odebrat. Pokud by k tomuto došlo, dostal bych se při luštění minimálně jednou do situace, kdy nemám žádná vodítka jak dál pokračovat a musel bych hádat (metoda pokus omyl), jaké číslo do buňky doplnit. A to je v rozporu se zadáním jednoznačného postupu. 4.2.2. Generování možného postupu řešení sudoku úlohy Z předchozího textu je zřejmé, že vygenerovaná sudoku úloha má vždy pevně danou alespoň jednu cestu, vedoucí k vyřešení. Tato cesta byla vytvořena za pomoci podporovaných řešících metod, a proto je zajištěno, že pomocí těchto metod se dá nalézt. Nám jen stačí zaznamenat, jaké řešící metody a v jakém pořadí byly při hledání této cesty aplikovány a tento záznam je náš postup řešení. 4.2.3. Generování úplného pole sudoku rekurzivním algoritmem Jedná se o klasický rekurzivní algoritmus. Do prázdného pole sudoku jsou vkládána náhodná čísla. Postupuje se po jednotlivých boxech. Po vložení čísla je otestováno, zdali neporušuje pravidla hry sudoku. Pokud ano, je vloženo jiné číslo, jinak pokračujeme dále. Pokud nám nezbývají již žádná čísla, která by tato pravidla neporušovala, vracíme se o krok zpět. 4.3. Metody řešení Sudoku generátor využívá následující řešící metody: Forced Digit Pokud v peersu (housu) určité buňky chybí jen jedno číslo, pak toto číslo musí být umístěno v této buňce. V tomto případě je číslo přímo odvozeno. Tato metoda se ovšem používá i k eliminaci kandidátů. Odstraní ta čísla z kandidátů určité buňky, jejichž hodnoty se vyskytují v okolí (peersu) této buňky. Jinak řečeno, pokud je v nějaké buňce číslo 8, tak si buňky, které jsou s ní např. v boxu, toto číslo vyškrtnou ze svých kandidátů. Obrázek 4 ilustruje příklad přímého odvození buňky pomocí této metody.
6
1 1
8
2 3
2
3
4
5
6
9
3
1
6
6
2
5
4
8
7
8
9
5
7
1 2
4
9 1
5
9
6
9
7
7
4
1
2 8
8
4
9
6
2
5
8
Obrázek 4 - Buňka v 3. řádku a 6. sloupci má ve svém okolí všechny hodnoty kromě 7, a proto do ní musíme vepsat právě toto číslo.
Cross Hatching Pokud kandidát určité buňky nemůže být umístěn nikde jinde v housu, pak tento kandidát musí být vepsán do této buňky (protože house musí obsahovat všechna čísla 1 až 9). Tato metoda neeliminuje žádné kandidáty, ale buňky přímo odvozuje. 1 1
8
2 3
2
3
4
9
5
6
1
6
6
2
5
8
7
8
9
5
7
1 2
4
9 1
5
9
6
9
7
7
4
1
2 8
8
4
9
6
2
5
8
Obrázek 5 - Buňka v 3. řádku a 9. sloupci nemá ve svém řádku jinou možnost umístění čísla 6, a proto ho musíme zapsat právě sem.
7
1 1
8
2 3
2
3
4
9
5
6
1
6
6
2
5
8
7
8
9
5
7
1 2
4
9 1
5
9
6
9
7
7
4
1
2 8
8
4
9
6
2
5
8
Obrázek 6 - Buňka v 9. řádku a 2. sloupci nemá ve svém boxu jinou možnost umístění čísla 8, a proto ho musíme zapsat právě sem.
Locked Candidates Tato metoda slouží k eliminaci kandidátů, a to hned skupiny buněk. Její pochopení bude nejsnadnější z obrázku 7. 1
2
3
1 2
4
3 6
5
7
9
5
6
7
1 5 6 7 9
2
3
4
5 6 79
8
1
3
7
3
2
6
8 9
7 8 6
5
4
6 1
7
8
9
1
1 6 7
5
4
4
9 9
2
8
1
7
6
1 4 68 1 5 6 7 9 1 4 9
4 5
8
7
Obrázek 7 - Jak je vidět, horní box může obsahovat číslo 1 jen na 2 pozicích. Pokud tyto pozice leží v jednom sloupci, pak ve zbytku sloupce musí být číslo jedna vyškrtnuto ze seznamu kandidátů ve všech buňkách, protože sice nevíme, kde přesně číslo 1 bude, ale máme jistotu, že to bude v tomto sloupci (platí obdobně i pro řádek).
8
Locked Candidates2 1 1
2
3
5
4
5
6
7
8
3
46
1
9
7
3
6
8
2
2
1
3 4
5
5
6
2
3
6 7 8 9
1 4 6
2 9
1 4 5
4
3
6 8
4 7
3
6
7
9
8
1 2 45
2 4 5 7 8
1 2 3 4 57
9
25
1 2 35
1 2 4 5 6
2 4 5 6 8
1 2 4 5 6
Obrázek 8 - Podobný princip jako Locked Candidates ale opačně. Tj. pokud se v některém sloupci mimo určitý box nenachází v kandidátech určitá hodnota, pak musí ležet ve stejném sloupci uvnitř boxu a ostatní buňky v boxu mimo sloupec si můžou danou hodnotu vyškrtnout z kandidátů.
4.4. Implementace Zde bych rád zmínil některé konvence, používané při popisu implementace sudoku generátoru. Postupy se snažím popisovat jen slovně (tzn., že neuvádím výpisy kódu přímo z programu) a postupuji tak, jak je algoritmus prováděn, aby byla zachována srozumitelnost. Funkce nebo metody, dále jen funkce, jsou psány ve stejném tvaru jako při deklaraci v programu, tj. x y(p1,pn), kde x je datový typ návratové hodnoty, y je název funkce a p1 až pn jsou datové typy vstupních parametrů. Typy návratové hodnoty a vstupních parametrů jsou však většinou uváděny jen při první zmínce o funkci. Pokud o funkci píši dále, uvádím ji z důvodu přehlednosti již jen ve zkráceném tvaru y(), kde y je název funkce. Při psaní názvů funkcí je pro zvýraznění použit jiný typ písma než pro okolní text. Dále si lze všimnout, že text je členěn do kapitol, které jsou věnovány určitým funkcím. To by mělo čtenáři pomoci se v popisu algoritmu lépe zorientovat. Pokud je to nutné, je na počátku kapitoly vývojový diagram dané funkce. Jeho úkolem není dopodrobna popsat danou funkci, ale spíše napomoci pochopení následujícího textu, který funkci popisuje. Obsahuje tedy převážně klíčová místa, rozhodující o návratové hodnotě, hlavní cykly a volání dalších funkcí. Vlastní kapitolu mají jen takové funkce, které reprezentují nějaký hlavní úkon nebo fázi programu. Menší funkce, které např. inicializují pár pomocných proměnných, jsou popsány přímo v textu a vlastní kapitoly nemají, protože by to naopak orientaci znesnadňovalo. Ačkoli se tomu snažím vyhýbat, někdy je nutné z důvodu přehlednosti uvést název některé proměnné. Tyto názvy jsou zvýrazněny tučnou kurzívou. K určení polohy buňky používám dva způsoby. Jeden je číslovat buňky zleva doprava, odshora dolů (začínáme tedy vlevo nahoře a končíme vpravo dole). Každá buňka má přiřazeno jedinečné číslo z intervalu 0 až 80. Druhý (používanější) způsob je dvojice souřadnic x, y z intervalu 0 až 8 (ve slovním popisu číslujeme řádky a sloupce jako 1 až 9)
9
pro každou buňku, kde x vyjadřuje pozici ve svislém směru (číslo řádku) a roste směrem dolů. Y vyjadřuje pozici ve vodorovném směru (číslo sloupce) a roste směrem doprava. Souřadnice buňky úplně vlevo nahoře je tedy x=0 a y=0 a buňka vpravo dole má souřadnice x=8 a y=8. 4.4.1. Funkce int main() - hlavní funkce generátoru sudoku
Obrázek 9 - Hrubý vývojový diagram funkce main()
Po spuštění sudoku generátoru se do konzole vypíše informace o verzi programu se stručným návodem, jak s programem dále pracovat. Poté se spustí funkce init_server(), která inicializuje WSA (používá se pro zachytávání chybových kódů soketů v os windows) a dále vytvoří naslouchací soket, který bude přijímat a ustavovat příchozí spojení. Pokud dojde k chybě, vrátí funkce false, sudoku generátor vypíše do konzole hlášení „Selhala inicializace vstupu/vystupu“ a ukončí se, protože bez správně fungujícího vstupu/výstupu nemůže pracovat. Pokud funkce vrátí true, je vše v pořádku a pokračuje se dále. Nastaví se generátor náhodných čísel a vynuluje se počítadlo vygenerovaných sudoku úloh. Poté se vstoupí do nekonečného while cyklu. Program proto buď skončí chybou, nebo ručním uzavřením jeho okna. V tomto cyklu se volá jediná funkce one_turn(), která provede jedno kolo kompletního generování. Pokud v ní dojde k chybě, vrací false a do konzole se vypíše „Generace zadani cislo x selhalo“. Při úspěšném návratu se vypíše „Bylo uspesne generovano zadani cislo x“ a po každém průchodu cyklem se o jedničku zvýší počítadlo průchodů. V následujících funkcích se využívá hlavní datová struktura cell, která tvoří pole 81 buněk cells[9][9]. Struktura Cell obsahuje pole devíti prvků typu boolean, které uchovává vodítka dané buňky. Pokud mě zajímá, zdali má buňka mezi vodítky číslo 1, podívám se do pole na první pozici. Pokud je zde true, buňka vodítko má, pokud false, 1 se mezi vodítky buňky nevyskytuje. Číslo 2 bych kontroloval na druhé pozici v poli atd. pro všechna čísla 1 až 9. Seznam vodítek bych také mohl uchovávat v nějaké dynamické struktuře, což by odstranilo nevýhodu mého řešení, že pro každou buňku uchovávám 9 logických hodnot bez ohledu na to, kolik má vodítek. Datový typ boolean však není tak náročný na obsazení paměti a navíc by moje řešení mělo být o mnoho rychlejší, než prohledávání nějakého seznamu nebo množiny, protože při kontrole vodítka „jdu na jisto“ (hodnota vodítka zároveň určuje jeho pozici v poli). Datová struktura cell dále obsahuje celočíselnou proměnnou, která udává počet vodítek. Funkce, měnící počet vodítek, modifikují také tuto proměnnou a ta se pak dá použít k rychlému testu, jestli byla buňka 10
odvozena (když klesne počet vodítek na 1), bez toho, aniž bychom museli pokaždé procházet celé pole s vodítky. Důležitá je proměnná deductived na signalizaci, zdali již byla původně prázdná buňka odvozena (true-ano, false-ne). S odvozenou buňkou se pak pracuje, jako by tam díra nebyla. Podobnou proměnnou je logická proměnná cover, která určuje, zdali se v buňce nachází číslo (true), nebo je tam díra (false). Logická proměnná lc se používá k signalizaci, jestli byla buňka již použita jako výchozí pro metody Locked Candidates X. Poslední věc, kterou je třeba zmínit, je že struktura cell má funkci bool unset(int), která provede odstranění vodítka s číslem, které dostane jako vstupní parametr. Postará se o dekrementaci počtu vodítek a v případě že klesne na 1, nastaví odvoditelnost buňky. Vrací false, pokud vodítko, které má odebrat, bylo již odebráno dříve. Jinak vrací true. Opačná funkce pro přidání vodítka není potřeba, protože ve výchozím stavu má každá buňka všechna vodítka nastavena a v průběhu řešení se jen odebírají. 4.4.2. Funkce bool one_turn() - provádějící jedno kolo generování
Obrázek 10 - Hrubý vývojový diagram funkce one_turn()
Ve funkci one_turn() se jako první zavolá metoda init_values(), která inicializuje některé globální proměnné a pole na výchozí hodnoty. Poté se vytvoří pomocné proměnné a vektor celých čísel used o 81 prvcích, obsahující čísla 0 až 80. Tento vektor nám pomůže
11
při náhodném výběru buňky k odebrání. Kdybychom totiž použili nejjednodušší řešení, tj. vygenerujeme náhodné číslo v rozsahu 0 až 80 a uděláme díru v buňce s tímto číslem, může se nám stát, že díra již v buňce existuje. To by se dalo vyřešit jednoduchým testem na díru a v případě potřeby zvolit jiné náhodné číslo. Ovšem ke konci generování, kdy již máme hotovo např. 50 děr, je šance, že netrefíme díru menší než 50% a při troše „smůly“ by mohlo dojít k mnoha iteracím cyklu generování náhodného čísla, než bychom trefili nějaké použitelné. Proto jsem se rozhodl pro řešení, které sice zabere navíc proměnnou typu vektor a operace s touto proměnnou stojí také nějaký čas, ale není tak nevyzpytatelné jako předchozí možnost. Vygeneruje se náhodné číslo od 0 až do velikosti vektoru used a z vektoru je přečtena hodnota prvku s indexem rovnému tomuto číslu. Tento prvek je pak z vektoru odebrán. Jak je vidět, vždy dostaneme na první pokus číslo, které ještě nebylo použito. Po nadeklarování lokálních proměnných je zavolána metoda make_field(), která vygeneruje nové, úplné pole sudoku do globální proměnné typu pole celých čísel, sudoku[9][9]. Po návratu z metody make_field() je sudoku generátor připraven vytvořit sudoku úlohu. Na to potřebuje vstupní data. Získání vstupních dat se trochu liší v závislosti na verzi programu. Popis práce vstupu/výstupu jednotlivých verzí naleznete v kapitole o Rozhraní. U obou verzí však dostaneme stejný výsledek, a to počet děr, které je třeba udělat. Provedeme tedy jejich otestování. V případě, že by vstupní data byla mimo rozsah, vypíše sudoku generátor do konzole hlášení „Vstupni informace mimo rozsah“ a změní vstupní data na 0. Pokud data nejsou platná (byla zadána písmena místo číslic), provede se generování opět pro 0. Pokud nedojde k chybě při příjmu a testu vstupních dat, vstoupíme do while cyklu, který probíhá, dokud jsme nevytvořili zadaný počet děr, nebo dokud nevyzkoušíme všechna možná umístění děr (tj. vektor used je prázdný). Vygenerujeme náhodné číslo v rozsahu 0 až velikost vektoru used. Hodnota prvku vektoru s tímto indexem bude předána funkci pair* xy(int), která převádí čísla z intervalu 0 až 80 na dvojici souřadnic x, y, které odkazují na stejnou buňku. Tyto souřadnice jsou uloženy do proměnné typu pair. Zde je vidět, proč používám dva způsoby odkazování se na buňku. Pokud potřebuji náhodně vybrat buňku, je výhodné vygenerovat jedno číslo z rozsahu 0 až 80 namísto dvou čísel x a y. Na druhou stranu je pro práci s polem výhodnější používat pro adresu buňky souřadnice x, y, protože se lépe procházejí jednotlivé řádky a hlavně sloupce. Proměnná cells[x][y].cover je nastavena na 0. Poté je zavolána funkce make_hole(), která se pokusí obhájit díru. Pokud uspěje, vrátí true a díra je považována za platnou. Sníží se počítadlo děr, které je ještě třeba vytvořit. Pokud díra nemohla být vytvořena, nastaví se cells[x][y].cover opět na hodnotu 1. V obou případech se odstraní použitý prvek z vektoru used (nikde se nevracíme, a proto když jsme prvek nemohli použít teď, nebude ho možné použít ani v budoucnu), nastaví se některé proměnné na výchozí hodnoty pomocí funkce reset_cells() a celý cyklus se opakuje. Po dokončení cyklu se přejde na fázi vypsání výsledků. Ta se opět liší v závislosti na verzi sudoku generátoru a opět se více dočtete v kapitole o Rozhraní. Po vypsání výsledků vrací funkce one_turn() true, čímž signalizuje úspěch celého kola generování.
12
4.4.3. Metoda make_field() a bool make_cell(vector&,int,int) - generující úplné pole sudoku
Obrázek 11 - Hrubý vývojový diagram funkce make_field() a make_cell()
13
Metoda make_field() zavolá rekurzivní funkci bool make_cell(vector&, int,int), které předá souřadnice x, y buňky, do které má být vyplněno nějaké číslo a ukazatel na vektor celých čísel box2 obsahující čísla 1 až 9. Význam tohoto pole bude vysvětlen záhy. Vyplňovat se začíná od levého horního rohu, tedy x=0 a y=0 a pokračuje se po řádcích v rámci jednoho boxu zleva doprava, odshora dolů. Tzn., že následující buňky budou x=0,y=1 x=0,y=2 a pak x=1,y=0 atd. Po úspěšném vyplnění buňky x=2,y=2, tedy poslední buňky (pravý dolní roh) prvního boxu se pokračuje první buňkou (levý horní roh) druhého boxu x=0,y=3 a vše se opakuje. Doplňovaná čísla jsou náhodně vybírána z vektoru celých čísel box2, který si funkce make_cell() předávají jako vstupní parametr. Tento vektor vlastně vyjadřuje možné kandidáty pro aktuální box. Používá se z důvodů urychlení testů správnosti pole sudoku. Při každém doplnění čísla do buňky je totiž zkontrolováno, jestli dané číslo není v rozporu s pravidly hry sudoku. Test unikátnosti čísla v rámci řádku a sloupce je jednoduchý. Při procházení řádku zůstává x-ová souřadnice stejná a rovna x-ové souřadnici právě zpracovávané buňky, zatímco y-ová se inkrementuje o jedničku od nuly až po y-ovou souřadnici právě zpracovávané buňky (jelikož se vyplňuje zleva doprava, je řádek za právě zpracovávanou buňkou prázdný). Sloupec se prochází obdobně, y-ová souřadnice je stejná a rovna y-ové souřadnici právě zpracovávané buňky, zatímco x-ová se inkrementuje o jedničku od 0 do x-ové souřadnice právě zpracovávané buňky (jelikož buňky vyplňujeme odshora dolů, není ve sloupečku pod buňkou už co kontrolovat). Test unikátnosti čísla v boxu by byl složitější, jelikož nepoužíváme žádnou datovou strukturu, která by přímo vyjadřovala vztahy mezi buňkami v boxu. Máme jen dvourozměrné pole a tam je třeba příslušnost buňky k boxu ověřovat několika výpočty, což je neefektivní. Ovšem pokud bereme jen čísla z našeho vektoru box2, máme zaručeno, že se v boxu ještě nevyskytují, protože po každém použití prvek z vektoru odstraníme. Test unikátnosti čísla v boxu nám tedy odpadá. Takže funkce make_cell() ještě jednou. Z vektoru box2, který funkce dostala, se náhodně zvolí jeden prvek. Číslo, které prvek obsahuje, se zapíše do pole sudoku na souřadnice x, y, které byly funkci také předány. Poté se provede test jedinečnosti tohoto čísla pro řádek a sloupec (pro box test dělat nemusíme, viz předchozí vysvětlení). Pokud se v řádku ani sloupci takové číslo nevyskytuje, znamená to, že ho můžeme použít. Odstraníme prvek s použitým číslem z vektoru box2 a otestujeme, zdali vektor není prázdný. Pokud by byl, znamenalo by to, že jsme vyplnili celý box, a proto ještě otestujeme, jestli právě nezpracováváme buňku na souřadnicích x=8 a y=8, což je poslední buňka pole sudoku a to by znamenalo, že jsme úspěšně vyplnili celé pole a vrátíme true. Pokud se nacházíme u buňky jiné, musíme přejít na další box. Znovu tedy naplníme vektor čísly 1 až 9. Poté otestujeme, zdali se nacházíme v boxu na konci řádku (to jsou všechny boxy úplně vpravo) nebo se jedná o boxy, které vpravo sousedí s dalším boxem (to jsou boxy vlevo a uprostřed) a podle toho spočteme souřadnice následující buňky. Jedná-li se o box, který nemá pravého souseda, budou nové souřadnice x2=((x+1)%3+(x/3)*3)+3 a y2=0 kde x je souřadnice právě zpracovávané buňky. Pro zbylé boxy platí x2=(x+1)%3+(x/3)*3 a y2=y+1 kde x a y jsou souřadnice právě zpracovávané buňky. Poté zavoláme funkci make_cell(), které předáme nový vektor s čísly 1 až 9 a souřadnice x2 a y2. Pokud nám funkce vrátí true, vracíme také true. V případě, že je návratová hodnota false, znamená to, že touto cestou se pole sudoku vytvořit nepodařilo a musíme se vrátit. Jelikož jsme v buňce na konci boxu, nevrátíme se o jeden krok ale rovnou o dva (pokud bychom se vrátili jen o jeden krok, byli bychom ve stavu, kdy má box nevyplněnu poslední buňku a připadá na ni jen jeden kandidát, kterého jsme už vyzkoušeli, takže bychom se stejně hned vraceli o další krok zpět). V případě, že jsme úspěšně vyplnili buňku a vektor není prázdný (tzn. není to poslední buňka v boxu) zavoláme rovnou funkci
14
make_cell(),
které předáme pozměněný vektor (odebrali jsme z něj prvek s hodnotou kterou jsme právě doplnili) a souřadnice následující buňky, které se vypočítají: if((y%3)==2)x2=(x+1)%3+(x/3)*3; else x2=x; a y2=(y+1)%3+(y/3)*3), kde x2 a y2
jsou nové souřadnice a x a y jsou souřadnice právě zpracovávané buňky. Pokud volaná funkce vrátí true, vrací i tato funkce true. Pokud false vrátím do vektoru prvek z pozice x,y na místo, od kud jsem ho předtím umazal a vezmu hodnotu prvku, který následuje a test se zopakuje, pokud opět nevyhovuje, vezme se zas následující prvek atd. Pokud projdeme celý vektor a skončíme u původního, náhodně vybraného prvku, máme zaručeno, že jsme vyzkoušeli všechny možné hodnoty a musíme se vrátit o buňku zpět. Proto vrátíme false. Pokud test jedinečnosti čísla pro řádek a sloupec selhal, tzn. doplněné číslo je v rozporu s pravidly hry sudoku, musí se použít jiné. Stejně, jak bylo uvedeno v předešlém, vezme se hodnota prvku, který následuje za tím, který byl náhodně vybrán a test se zopakuje. Pokud opět nevyhovuje, vezme se zas následující prvek atd. Pokud projdeme celý vektor, musíme se vrátit o buňku zpět, takže vracíme false. Takto rekurzivně vytvoří funkce make_cell() pole se sudoku. Pokusem bylo zjištěno, že pro vytvoření jednoho pole je funkce volána v průměru 330krát. 4.4.4. Funkce bool make_hole(int,int) - rozhodující zdali lze na daném místě udělat díru
Obrázek 12 - Hrubý vývojový diagram funkce make_hole()
Vstupem této funkce jsou dvě celá čísla, vyjadřující souřadnice x a y. Tato funkce se pokusí obhájit díru na těchto souřadnicích (obhájit znamená dokázat, že díru mohu vytvořit na základě pravidla: díru vytvořím, jen když dokážu zpětně odvodit číslo, které na její místo patří). Pokud uspěje, vrací true, jinak vrací false. Nejprve se pokusí o rychlý test, zdali lze díru odvodit zavoláním funkce bool make_clues(int,int), které předáme souřadnice x, y. Pokud byla buňka odvozena, obhájili jsme platnost díry a vracíme true.
15
Přímé odvození buňky je časté jen ze začátku, kdy je celkový počet děr v poli sudoku malý. V pozdějších fázích je třeba pro odvození buňky nejprve odvodit jiné buňky. Proto se přejde do while cyklu, který volá funkci make_clues() postupně pro všechny díry celého pole sudoku zleva doprava a odshora dolů. Po každém návratu z funkce make_clues() se otestuje, jestli nebyla buňka na souřadnicích x, y odvozena. Pokud ano, tak se končí a vrací true. Funkce make_clues() vrací true, pokud způsobila nějakou změnu, a to jak v poli sudoku, tak ve vodítkách jednotlivých buněk. Cyklus while končí, když ke změnám docházet přestane, tj. make_clues() vrátí false pro všechny díry v poli sudoku (pokud jsme buňku neodvodili a v poli už nedochází k žádným změnám, je tento stav trvalý a danou buňku už neodvodíme). Díru jsme neobhájili, takže se na souřadnicích x, y nemůže vyskytovat a vracíme false. 4.4.5. Funkce bool make_clues(int,int) - aplikující řešící metody na buňku
Obrázek 13 - Hrubý vývojový diagram funkce make_clues()
Úkolem této funkce je odvodit buňku na souřadnicích x, y, které jsou funkci předány. Pokud se to funkci podaří, vrací true. Když neodvodí žádnou buňku, ale podaří se jí alespoň eliminovat některé kandidáty, vrací také true. Pokud funkce nezpůsobí žádnou změnu v poli sudoku nebo kandidátech nějaké buňky, vrací false. Funkce aplikuje různé metody logického odvození buňky. Popis těchto metod najdete v sekci Metody řešení. Nejprve se pokusí odvodit buňku pomocí Forced digit. Prohledá peers buňky a zaznamená si všechny vyplněné hodnoty, které tam najde a na ty pak zavolá funkci unset(). Poté zkontroluje, zdali byla buňka odvozena a pokud ano, vrátí true. Pokud ne, pokračuje další metodou, kterou je Cross Hatching. V té prochází nejdříve řádek
16
a hledá, jestli má nějaká prázdná buňka ve svých vodítkách stejné číslo jako je hodnota buňky, kterou se právě snažíme odvodit. Pokud ne, je buňka, v souladu s principem této metody, odvozena. Pokud ano, pokračujeme podobným testem pro sloupec a pak pro box. Pokud se povedlo při některém testu buňku odvodit, vracíme true. Pokud ne, přichází na řadu metoda Locked Candidates. Aby se redukoval počet průchodů polem se sudoku, byly již během metody Cross Hatching nastaveny určité příznaky, které nám říkají, zdali lze metody Locked Candidates X použít. Starší verze sudoku generátoru redukovala počet průchodů ještě tak, že se Cross Hatching i Locked Candidates X hledaly již během průchodů v metodě Forced digit. To ale učinilo kód velmi nepřehledným a ušetřený čas nebyl zase tak velký. Proto jsem se rozhodl metody více rozdělit. Příznaky, které Locked Candidates využívají, jsou: - detekce, jestli má buňka mimo sloupec i řádek ale ve stejném boxu jako je právě zpracovávaná buňka takové vodítko, jako je hodnota této buňky. Pokud ano, nemůže být již Locked Candidates použita. - detekce, jestli má buňka ve stejném řádku a boxu jako je právě zpracovávaná buňka takové vodítko, jako je hodnota této buňky. Pokud ano, byl nalezen Locked Candidates pro řádek. - detekce, jestli má buňka ve stejném sloupci a boxu jako je právě zpracovávaná buňka takové vodítko, jako je hodnota této buňky. Pokud ano, byl nalezen Locked Candidates pro sloupec. Na základě těchto příznaků jsou provedeny patřičné kroky a metoda Locked Candidates je hotova. Po ní následuje metoda Locked Candidates2, která pracuje obdobně jako její předchůdkyně. Využívá příznaky: - detekce, jestli má buňka takové vodítko jako je hodnota právě zpracovávané buňky a je s ní ve stejném řádku a boxu. Pokud ne, našel jsem tuto hodnotu mimo box a Locked Candidates2 již nemůže být použita. - detekce, jestli má buňka takové vodítko jako je hodnota právě zpracovávané buňky a je s ní ve stejném sloupci a boxu. Pokud ne, našel jsem tuto hodnotu mimo box a Locked Candidates2 již nemůže být použita. Na základě těchto příznaků jsou opět provedeny patřičné kroky a metoda Locked Candidates2 je hotova. Pokud metody Locked Candidates X změní počet vodítek nějaké buňky, jsou podniknuty kroky, aby funkce make_clues() na konci vrátila true (hodnota proměnné number pro porovnání, zdali u buňky došlo ke změně počtu vodítek je nastavena na -1, takže vždy bude vyhodnoceno, že k změně počtu vodítek došlo a tak bude návratová hodnota true). Každá buňka může vyvolat nalezení Locked Candidates X několikrát. Ovšem význam má jen první nález. Při ostatních nálezech se jen opakují akce, které se již provedly při prvním nálezu, což zbytečně stojí čas. Každá buňka proto obsahuje kontrolní proměnnou lc typu boolean , která signalizuje, zdali již daná buňka byla použita při těchto metodách (true - nebyla, false - byla). I když jsou metody dvě a ještě se dělí na verzi pro řádek a pro sloupec, stačí nám jen jedna proměnná. Platí totiž, že pokud byly nalezeny Locked Candidates nebo Locked Candidates2 pro řádek, nemohou již existovat pro sloupec. Z popisu obou metod si lze navíc všimnout, že jsou svým opakem. Přesněji, to co je následkem jedné, je příčinou druhé. Proto ať provedeme jakoukoliv z nich, výsledek je v podstatě stejný. Z těchto poznatků plyne, že nám stačí jen jedna logická proměnná, která když je nastavena, nemá smysl již Locked Candidates ani Locked Candidates2 vykonávat. Pokud nebyla zadaná buňka během funkce make_clues() odvozena a tudíž nebyla ihned vrácena hodnota true, zkontrolujeme ještě, zdali u ní alespoň došlo ke změně počtu vodítek. Pokud ano, vrátíme true, pokud ne tak false.
17
4.4.6. Funkce bool make_hole_sol() a bool make_clues_sol(int,int) - generující postup řešení
Obrázek 14 - Hrubý vývojový diagram funkce make_hole_sol()
Generování postupu řešení probíhá na stejném základě jako generování sudoku úlohy až na to, že při tom pořizujeme záznam, jak byla buňka odvozena. Proto tyto funkce pracují prakticky stejně jako jejich jmenovkyně (neobsahující slovo _sol). Pro záznam se používá pole celých čísel solution[4][162]. Jeho rozměry byly stanoveny tak, že pro každý záznam máme k dispozici čtyři čísla. Záznamů tedy můžeme pořídit 162. V poli se pohybujeme pomocí ukazatele za poslední záznam sol_iter. Jeho maximální velikost je kontrolována, aby nedošlo k překročení hranice pole a následné chybě programu. Teoreticky však nemůže být pořízeno více než 162 záznamů. Každé odvození buňky se totiž zaznamenává jen jednou. Máme tedy maximálně 81 záznamů (Protože máme 81 buněk. Minimální počet vyplněných políček, který musíme zachovat, je však 17, takže máme ještě rezervu). Dále se záznam pořizuje při změně kandidátů pomocí metod Locked Candidates X. Tyto metody, jak bylo vysvětleno v kapitole 4.4.5 Funkce bool make_clues(int,int) - aplikující řešící metody na buňku, jsou aplikovány pro každou buňku jen jednou, a proto dostáváme opět maximálně 81 záznamů. Jednoduchým výpočtem 81 + 81 = 162 tedy vypočteme dostatečnou velikost pole pro záznamy řešení. O odebrání kandidátů pomocí metod Forced digit a Cross Hatching se záznam nedělá. Cross Hatching totiž buňku přímo odvodí a s kandidáty vůbec nepracuje. Forced digit kandidáty sice odebírá, ale zaznamenávat například, že ve všech buňkách v určitém řádku je odstraněn kandidát 3, protože číslo 3 se vyskytuje v tomto řádku, mi přijde zbytečné, jelikož to každý vidí na první pohled a spíše by to výpis řešení znepřehledňovalo. Když tedy sudoku generátor dojde do fáze, kdy je třeba generovat postup řešení, je sol_iter nastaven na nulu a zavolána funkce make_hole_sol() , která zkusí odvodit všechny buňky. Volá tedy funkci make_clues_sol() pro všechny prázdné buňky, dokud
18
nejsou všechny zaplněny. Pokud byla sudoku úloha vygenerována sudoku generátorem, je zaručeno, že řešení bude nalezeno. Ovšem pro případ nějaké neočekávané chyby, nebo pro snadnější rozšíření sudoku generátoru pro řešení cizích úloh, se na konci testuje, zdali byly všechny buňky opravdu odvozeny. Pokud ne, vrací false. Jinak vrací true. Po každém návratu z funkce make_clues_sol() je pro jistotu otestováno, jestli sol_iter nepřerostl velikost pole. Po prvním průchodu celým polem je nastavena globální proměnná first na false. Tato proměnná se používá k zajištění, že na všechny buňky bude aplikována alespoň jednou metoda Forced Digit ještě před prvním použitím metod Locked Candidates X. Tyto metody tedy nejsou používány, dokud je proměnná first nastavena na true. To se dělá z důvodu omezení zbytečných výpisů o odstranění kandidátů. Že musí být určitý kandidát odstraněn na základě toho, že je v okolí buňky již vyplněné stejné číslo jako je sám kandidát, je totiž vidět na první pohled. Toto odstranění kandidátů provádí metoda Forced digit, aniž by o tom dělala nějaké záznamy. Forced digit má před Locked Candidates X přednost. Jelikož jsou ale metody aplikovány zleva doprava a odshora dolů, může se stát, že při prvním průchodu metody Locked Candidates X odstraní nějaké kandidáty z buněk napravo nebo pod aktuálně zpracovávanou buňkou (kde ještě nikdy nebyla aplikována metoda Forced digit) a udělá o tom záznam, i když by stejné kandidáty mohly být odstraněny v tichosti metodou Forced digit. A proto jsou metody Locked Candidates X používány až poté, co je na každou buňku alespoň jednou aplikována metoda Forced digit. Funkce make_clues_sol() provádí řešící metody úplně stejně jako funkce pro sestavování sudoku úlohy make_clues(). Jediný rozdíl je v tom, že pořizuje záznamy do pole solution. Do tohoto pole se zapisuje číselný kód, jehož význam je následující: Pro jeden záznam máme k dispozici 4 čísla. První číslo je vždy dvouciferné a vyjadřuje, jakou metodou byla odvozena buňka nebo odebrány kandidáty skupině buněk. Popřípadě může informovat o mimořádných stavech. 10 - Forced digit, čisté odvození (tzn., že buňka měla na počátku 9 kandidátů a 8 jich bylo eliminováno touto metodou). 11 - Forced digit, dodělání buňky (tzn., že buňka měla již na začátku nějaké kandidáty eliminovány jinými metodami a nemůžeme tedy mluvit přímo o odvození metodou Forced Digit). 12 - Odvození pomocí Cross Hatching v řádku. 13 - Odvození pomocí Cross Hatching ve sloupci. 14 - Odvození pomocí Cross Hatching v boxu. 20 - Eliminace kandidátů v řádku mimo box pomocí metody Locked Candidates. 21 - Eliminace kandidátů ve sloupci mimo box pomocí metody Locked Candidates. 22 - Při provádění jednoho z předchozích dvou postupů byla odvozena nějaká buňka (kód 22 tedy vždy předchází kód 21 nebo 22). 23 - Eliminace kandidátů v boxu mimo řádek pomocí metody Locked Candidates2. 24 - Eliminace kandidátů v boxu a mimo sloupec pomocí metody Locked Candidates2. 25 - Při provádění jednoho z předchozích dvou postupů byla odvozena nějaká buňka (kód 25 tedy vždy předchází kód 23 nebo 24). Druhé a třetí číslo pak u všech metod udává nějaké upřesnění polohy. U kódů 10 až 14, 22 a 25 udává druhé číslo řádek a třetí číslo sloupec odvozené buňky. U kódů 20 a 23 udává druhé číslo řádek a třetí číslo box. U kódů 21 s 22 udává druhé číslo sloupec a třetí číslo box. Čtvrté číslo je pak vždy hodnota, která byla do buňky doplněna nebo kandidát který byl eliminován. Všechna tato čísla jsou v rozsahu 1 až 9. Začíná-li první číslo nulou, jedná se o speciální případ, signalizující zvláštní stavy. 00 - Řešení nebylo generováno (např. v případě, že někdo zadal generovat sudoku úlohu o 0 dírách).
19
01 - Řešení je příliš dlouhé (řešení se nevešlo do pole. Jak bylo vysvětleno v této kapitole výše, nemůže k tomu za bezchybného provozu dojít). 02 - Další postup řešení se nepodařil nalézt (K tomuto stavu také nemůže za normálních okolností dojít, ledaže by někdo modifikoval sudoku generátor). Jak je kód nadále zpracováván, je popsáno v kapitole o rozhraních. Funkce generující řešení a funkce, které se používají pro sestavování sudoku úlohy jsou si velice podobné. Ve starší verzi generátoru sudoku nebyly dokonce odděleny. V jakém módu mají pracovat bylo řízeno globální logickou proměnnou. To ovšem vyžadovalo, že při každé události, která by se měla zaznamenat, bylo nutné otestovat nastavení této proměnné. To vedlo k mnoha testům v průběhu sestavování sudoku úlohy, přestože generování postupu řešení provádíme jen jednou na konci. Proto jsem se rozhodl funkce rozdvojit a prodloužit tak kód za cenu ušetření provádění mnoha testů logické proměnné.
5. Rozhraní 5.1. Volba použitých technik Program má mít webové rozhraní. Není proto potřeba vytvářet nějaké samostatné GUI (grafické rozhraní) a má podobu konzole, do které může vypisovat dodatečné informace nebo chybová hlášení. Tato hlášení jsou psána bez diakritiky, protože ta nemusí být v konzole vždy podporována. Vstup dat je možný jen přes internetový prohlížeč. Program existuje ve dvou verzích, lišících se právě v provedení webového rozhraní. Internetová verze komunikuje s internetovými prohlížeči přes internet a druhá lokální verze komunikuje s internetovými prohlížeči jen na lokálním počítači. K dvěma verzím jsem došel následující úvahou: Úkol: Mám program v C++ a potřebuji, aby si vyměňoval data s internetovým prohlížečem. Myšlenka 1: V předmětu X36PKO jsme vytvářeli programy v C++ které si mezi sebou posílaly data pomocí TCP a UDP protokolu, a to jak přes internet, tak i v rámci jednoho počítače. PHP je velmi podobný C++ a proto by neměl být problém udělat totéž i v něm. Závěr 1: Stránka využívající některé funkce PHP pro výměnu dat s generátorem sudoku napsaným v C++. Na tomto principu pracuje internetová verze programu Myšlenka 2: Použití PHP je nepraktické, vyžaduje dodatečné programy jako webový server apod. Vždyť sudoku generátor komunikuje pomocí TCP protokolu a internetový prohlížeč vlastně také, tak proč neobejít PHP a nekomunikovat přímo? Závěr 2: Sudoku generátor čeká přímo na dotaz od internetového prohlížeče a vyměňuje si data přímo s ním. Na tomto principu pracuje lokální verze programu. Obě verze mají jisté výhody a nevýhody a proto jsem se rozhodl je zachovat obě. Společné mají to, že poskytují stejný výsledek, tj. že v internetovém prohlížeči je zobrazena stránka s vygenerovaným sudoku a s popisem, jak ho vyřešit. Pro komunikaci se využívají funkce soketů, jejichž knihovna je již standardní součástí C++ pro všechny platformy, takže by nebyl velký problém program překompilovat pro jiné OS než Windows. Pro spojení se používá TCP protokol, protože nám zaručuje bezchybný přenos a doručení dat v pořadí, v jakém byla odeslána.
20
5.2. Internetové stránky Je jasné, že pokud má mít sudoku generátor webové rozhraní, musí být na konci bez ohledu na verzi, vytvořena internetová stránka zobrazitelná v internetovém prohlížeči. Obě rozhraní používají 3 hlavní internetové stránky. Úvodní stránku pro vstup dat, stránku s výsledky a stránku s nápovědou. Stránky používají podobnou grafickou úpravu a tudíž mají všechny společný externí css soubor s grafickými styly. Jejich základní struktura je také stejná. Vždy se dělí na 3 části. Hlavičku obsahující název stránky, střed, ve kterém je vlastní obsah stránky a patičku, která obsahuje mé jméno a za jakým účelem byla tato práce vytvořena. Stránky s výsledky používají javascript, jehož kód je u obou verzí rozhraní stejný. Jelikož absence jeho podpory ze strany prohlížeče má celkem vysoký vliv na kvalitu výsledné stránky, je zahrnuto varování, které se zobrazí v případě, že javascript nefunguje. To je provedeno tak, že hlášení o nefungujícím javascriptu je ve výchozím stavu normálně zapsáno na stránku a před jejím zobrazením je pomocí javascriptu schováno. Pokud by tedy javascript nefungoval, neschová toto hlášení a uživatel si ho může přečíst. Na úvodních stránkách a stránkách s nápovědou je javascript použit jen minimálně a proto zde žádné takové varování není. Javascript je použit na dvě hlavní věci. Zaprvé na skrytí a zobrazení úplného pole sudoku (to aby případného luštitele nesvádělo pošilhávat na tuto tabulku), což obstarává funkce change(), která slouží jako přepínač viditelnosti. Zadruhé, a to je důležitější, k vygenerování slovního popis postupu řešení z číselného kódu, který jsem obdržel od sudoku generátoru. To dělá funkce make_sol(), která načítá čísla a pomocí logického větvení podle nich vypisuje věty. Jedná li se o oznámení o odebrání nějakých kandidátů, bude tato věta psána modře, aby se usnadnila orientace v textu. Ostatní věty mají standardní oranžovou barvu. Pokud by javascript nefungoval, je alespoň vypsán číselný kód s popisem, co jednotlivá čísla znamenají. To je uděláno stejným principem jako zobrazení varovného hlášení. Kód je na stránku vypsán vždy, ale je pomocí javasriptu schován a nahrazen slovním popisem. Bližší popis každé stránky je vždy uveden na konci kapitol u obou rozhraní. Krom stránky s nápovědou, protože ta je u obou verzí rozhraní naprosto stejná a kromě toho, že obsahuje popis hry sudoku a metod, pomocí kterých lze sudoku úlohu vyřešit, už na ní není co popisovat.
21
5.3. Internetová verze
Obrázek 15 - Schéma práce internetového rozhraní
Využívá kombinaci C++ a PHP. Na počítači je spuštěn generátor sudoku, napsaný v C++, který naslouchá na TCP portu 5528. Funkce pro příjem pracují v blokovacím režimu a pokud žádné spojení nepřichází, program je uspán. V tomto stavu nezatěžuje procesor a po určitém čase zabírá velmi málo operační paměti. Pokud přijde nějaké spojení na jeho port, je program probuzen a spojení obslouží. Dále je na počítači webový server s podporou PHP. Server umožňuje přístup z internetu k úvodní html stránce pro náš sudoku generátor. Úvodní stránka obsahuje formulář pro vstup dat, v našem případě počet děr, které chceme mít ve výsledném poli sudoku. Po odklepnutí tlačítka odeslat se vstupní hodnota pošle následující stránce, která využívá funkce PHP pro komunikaci s naším sudoku generátorem, běžícím na stejném počítači. Sudoku generátor z důvodu bezpečnosti komunikuje jen v rámci lokálního počítače a nelze se na něj tedy napojit zvenčí. Styk s okolními počítači obstarává webový server, který tak přebírá starosti o bezpečnost a také obsluhu více požadavků najednou. Stránka pošle generátoru sudoku počet děr a ten jí po provedení patřičných výpočtů vrátí 4 bloky dat (textu). V prvním bloku pošle informace o generování, kolik děr bylo vytvořeno a kolik se jich vytvořit nepodařilo. V druhém bloku pošle sudoku úlohu a úplné pole sudoku. Ve třetím pak pošle postup řešení a ve čtvrtém bloku se pošle opět sudoku úloha a úplné pole sudoku, avšak ve speciální formě, kterou používají některé programy pro práci se sudoku jako vstup. Probíhají tedy čtyři přenosy a jejich počet a pořadí jsou pevně dány programem. Tyto přenosy naplní daty čtyři PHP proměnné, které můžeme dále zpracovávat. Toto je jedna z výhod, proč jsem se rozhodl zachovat variantu využívající PHP. Jediné co se musí, je provést čtyři příjmy a naplnit tak proměnné. Vše ostatní jako vzhled, nebo jak bude s proměnnými naloženo, záleží na tom, jak je PHP stránka napsána. Tato stránka je přístupná správci webového serveru a lidem, kterým to správce dovolí a dá se editovat v jednoduchém textovém editoru, což přináší značnou dynamiku výstupu bez nutnosti zásahu do kódu sudoku generátoru. Možnost využívat služby programu odkudkoliv z internetu se navíc ukázala užitečná, např. při jejím předvádění vedoucímu práce, kdy nebylo nutné spouštět na jeho počítači žádné exe
22
soubory, ale stačil jen internetový prohlížeč s připojením k internetu a sudoku generátor, běžící na počítači u mě doma. 5.3.1. Přenášené bloky Jak již bylo řečeno, v prvním bloku se posílá čistý text, který nás informuje o výsledku generování. Pokud se povedlo udělat zadaný počet děr, pošle se „Bylo vytvořeno x děr“, jinak se pošle „Dál nelze nic odebrat. Bylo vytvořeno x děr, tudíž y děr se vytvořit nepodařilo.“. Sudoku úloha a úplné pole sudoku, posílané v druhém bloku, obsahují již kompletní html tagy a lze je tudíž přímo vypsat do html stránky. Každé pole je jedna samostatná tabulka, jejíž buňky mají přiřazené třídy pro grafickou úpravu pomocí css. Obě pole (tabulky) jsou nakonec vloženy ještě do jedné tabulky kvůli lepšímu umístění na stránce. Postup řešení, posílaný ve třetím bloku dat, je zakódovaný do posloupnosti čísel. Kódování se provádí z důvodu kompaktnosti. Slovní popis řešení může mít tisíce znaků, a proto je výhodné ho poslat v kompaktní formě a nechat sestavení slovního popisu řešení na internetovém prohlížeči. Čísla vyjadřují kódy metod použitých při řešení a doplňková data. Sudoku generátor si kvůli rychlosti zaznamenává řešení do dvourozměrného pole celých čísel o rozměrech 4x162. Toto pole pak jen vypíše do jedné řady čísel a tu pošle na stránku. Více se o tomto kódování dočtete v kapitole 4.4.6 Funkce bool make_hole_sol() a bool make_clues_sol(int,int) - generující postup řešení. K sestavení slovního popisu řešení je použit javascript. Ten je vhodný, protože ho vykonává až internetový prohlížeč na straně uživatele a dlouhý slovní popis řešení se tudíž nepřenáší a nedochází k takovému zatížení přenosové linky. Nevýhoda je, že někteří uživatelé mohou mít provádění javascriptu zakázané a těm se pak vypíše postup řešení pouze v kódové formě. Takoví uživatelé budou na nefungující javascript a s tím související problémy alespoň upozorněni. Ve čtvrtém bloku se posílá opět úplné pole sudoku, ale jednotlivé řádky jsou zapsány za sebou bez oddělovačů a stejným způsobem je posláno i pole s dírami. Některé programy pro práci se sudoku totiž používají tuto řádkovou formu jako svůj vstup. Uživateli pak stačí jen zkopírovat řádek ze stránky, vložit ho do takového programu a pole sudoku je načteno bez pracného přepisování jednotlivých buněk.
23
5.3.2. Přenos dat - Implementace
Obrázek 16 - Hrubý vývojový diagram zpracování vstupu
Obrázek 17 - Hrubý vývojový diagram výstupních operací
Přenos dat mezi sudoku generátorem a PHP stránkou probíhá oběma směry. Stránka pošle sudoku generátoru vstupní data a ten jí pošle nazpět 4 bloky dat (textu). V praxi to vypadá takto. Nejprve se zavolá funkce server_accept(), která v případě, že je k dispozici příchozí spojení, mu přiřadí nový soket, pomocí kterého bude možné se spojením dále pracovat. V opačném případě se uspí a čeká na příchozí spojení (uspí se tak celý generátor sudoku). V případě selhání této funkce vrátí false, do konzole je vypsáno hlášení „Selhal accept“ a toto kolo generování sudoku úlohy je dále propagováno jako nezdařilé. Při úspěchu se pokračuje zavoláním funkce ReceiveLine(), která načítá znaky ze vstupního proudu na soketu, vytvořeném ve funkci server_accept(), dokud nenarazí na znak konce řádku '\n'. Toto je jediný přenos dat ve směru stránka -> sudoku generátor a posílá se jen jedno číslo, udávající počet děr. Přijatý řetězec je na číslo převeden pomocí funkce int atoi(const char * str), která vrátí celé číslo nebo nulu v případě, že 24
řetězec nelze na číslo převést. Vstupní data sudoku generátoru musí být celé číslo v rozmezí 0 až 81. Jeho správnost je kontrolována jak samotnou stránkou, tak i sudoku generátorem. Pokud chybu vstupních dat zachytí stránka, upozorní na to uživatele a ke komunikaci se sudoku generátorem vůbec nedojde. Po úspěšném testování probíhá vlastní generování, které již s rozhraním nesouvisí a je popsáno v kapitole Implementace. Po dokončení generování sudku úlohy je třeba výstupní data poslat na stránku. Přenos ve směru sudoku generátor -> stránka je již o něco složitější. TCP protokol sice zaručuje, že data budou přijata ve stejném pořadí, jako byla odeslána, ale nijak od sebe jednotlivé přenosy neodděluje. Proto když pošleme dvakrát po sobě blok dat o velikosti 512B, na přijímací straně skončí blok dat o velikosti 1024B. Je tedy třeba jednotlivé přenosy nějak odlišit. Nabízí se nějaký ukončovací znak (popř. posloupnost znaků), který by signalizoval konec jednoho bloku dat. To má nevýhodu, že tento znak se nesmí vyskytovat nikde v přenášených datech a to nelze zcela zaručit. Další nevýhoda je, že musíme testovat každý přenášený znak, jestli není ukončovací. Proto jsem se rozhodl použít variantu, kdy se před vlastním přenosem bloku pošle jeho délka v bytech. Příjemce pak z proudu dat přečte jen daný počet bytů, které náleží danému bloku. Konkrétně: Mezi Sudoku generátorem a internetovou stránkou „je dohoda“ že jako první se začne posílat délka bloku v bajtech ve formě ascii znaků (tj. jedna cifra je jeden byte) a celá posloupnost čísel je zakončená písmenem 'x'. Např. pokud chceme poslat blok dat o velikosti 4587 bytů, tak budou přicházet znaky '4' '5' '8' '7' 'x' a pak už daný blok dat. Stránka přečte po jednom přicházející znaky a sestaví z nich číslo. Teoreticky tedy není žádné omezení délky bloku posílaných dat, ovšem sudoku generátor tuto délku omezuje na 999 999 bytů (znaků), protože posílání delšího textu je značně neefektivní a ukazuje spíš na nějakou chybu. V případě, že by se nějaká metoda pokusila poslat delší text, program ho zkrátí na maximální možnou délku a vypíše do konzole „ Posila se prilis dlouhy retezec a proto bude zkracen“. Druhý problém, který byl třeba vyřešit, souvisel se synchronizací odesilatele (sudoku generátor) a příjemce (stránka s PHP). Funkce pro příjem, kterou používá PHP, má jako vstupní parametr kromě jiných také maximální délku dat v bytech, které se načtou. Problémem bylo, že tato hodnota není zároveň také minimální a stávalo se, že sudoku generátor poslal data o délce 8000B, ovšem do proměnné se načetlo jen 3000B a zbytek zůstal ve vstupním bufferu, takže tato data byla považována za součást dalšího přenosu a nastala chyba. Tento problém byl vyřešen jednoduchým testem na délku přijatých dat a donačtením dat v případě potřeby. Sudoku generátor otestuje, zdali se mu podařilo vytvořit všechny požadované díry a své zjištění pošle na stránku jako první datový blok. To probíhá tak, že do proměnné out typu stringstream se vloží potřebná data a předá se funkci bool vypis_sock(stringstream&), která už se postará o to, aby data byla poslána na stránku. Také vymaže obsah proměnné out a tak po návratu do ní můžeme hned začít ukládat další blok dat. To se provede zavoláním funkce vypis_table(ostream&), která do proměnné typu ostream (můžeme jí tedy předat i referenci na standardní výstup nebo na proměnnou typu stringstream) provede výpis sudoku úlohy a úplného pole sudoku. Jelikož je výstup určen pro internetový prohlížeč, jsou obě pole sudoku zapisována ve formátu html tabulky. Druhou možností by bylo poslat stránce jen čísla a nechat ji, ať je do tabulky poskládá sama. C++ je však rychlejší a nárůst objemu přenášených dat není zase tak velký. Proto je lepší tuto akci provádět v sudku generátoru. Po návratu z funkce vypis_table() je opět zavolána funkce vypis_sock(), která odešle na stánku druhý blok dat. Ve třetím bloku se má posílat postup řešení sudoku úlohy. Proto je zavolána funkce bool make_hole_sol(), která vygeneruje postup řešení. Více o této funkci v kapitole 4.4.6 Funkce bool make_hole_sol() a bool make_clues_sol(int,int) - generující postup řešení. Jen připomenu, že tato funkce zapisuje postup řešení do pole celých čísel solution podle
25
určitého kódu. Pokud vrátí false a zároveň nebyla překročena kapacita pole solution, znamená to, že se řešení nepodařilo sestavit a do pole solution je za poslední záznam zanesen patřičný chybový kód. Pokud je návratová hodnota true nebo byla překročena kapacita pole, je zavolána metoda vypis_solve(ostream&). Ta provede znovu test na překročení pole, a pokud k němu došlo, doplní na poslední místo v poli patřičný chybový kód. Druhým testem zjistí, zdali není pole naopak zcela prázdné. Pokud ano, zapíše na první místo v poli patřičný kód. Poté projde všechny záznamy v poli. Každý záznam se skládá ze 4 celých čísel. Tato čísla jsou zapisována do výstupní proměnné za sebou záznam po záznamu, oddělené čárkami. Nakonec tedy dostaneme proud čísel, ve kterém je zakódován postup řešení sudoku úlohy, který poté opět odešleme na stránku pomocí funkce vypis_sock(). Poslední datový blok, který nám zbývá poslat má obsahovat sudoku úlohu a úplné pole sudoku ve speciální formě. Tu vytvoří funkce vypis_line(ostream&). Ta čte čísla z úplného pole sudoku po řádcích zleva doprava a odshora dolů a zapisuje je za sebe do jednoho řádku bez jakýchkoliv oddělovačů. Pak odřádkuje a stejnou řadu čísel sestaví i pro sudoku úlohu, přičemž díry nahrazuje nulami. A to je vše. Po návratu se opět pošle čtvrtý datový blok na stránku a výstup dat je hotov. 5.3.3. Funkce bool vypis_sock(stringstream&) - Kontrolující a upravující výstupní data před předáním dalším funkcím
Obrázek 18 - Hrubý vývojový diagram funkce vypis_sock()
26
Vstupem této funkce je reference na stringstream. Tento typ proměnné může obsahovat dlouhý textový řetězec včetně speciálních znaků jako odřádkování apod. Pro uchovávání výstupních dat jsem si ji vybral, protože se do ní dá dobře zapisovat operátorem <<. Nejdříve se zkontroluje, zdali není obsah vstupu prázdný. Pokud ano, je do něj vložena mezera. To aby se alespoň něco v pozdější fázi odeslalo. Počet odeslání dat na straně sudoku generátoru a počet příjmů dat na straně stránky je totiž shodný. Proto pokud byla zavolána tato funkce, znamená to, že sudoku generátor chce něco poslat. A i když se třeba nějakým nedopatřením nevytvořila žádná výstupní data k odeslání, musíme něco poslat, aby nebyl počet odeslání menší, než stránka čeká. Dále se určí délka odesílaného textu a provede kontrola, jestli neobsahuje více jak 999 999 znaků. Pokud ano, vypíše se do konzole zpráva „Posila se prilis dlouhy retezec a proto bude zkracen“ a proměnná značící délku textu, se kterým se bude nadále pracovat, je nastavena na 999 999. Je vytvořena proměnná text typu ukazatel na pole znaků, do které je přenesen obsah proměnné typu stringstream, kvůli snadnějšímu zpracování. Poté se zavolá funkce bool server_snd(char *, int), které předáme pole text a jeho délku. Tato funkce odešle daný text na stránku a vrací logickou hodnotu na základě úspěchu. Pokud vrátí false, vracíme i my false, pokud true vracíme true. V obou případech ještě před návratem vymažeme obsah proměnné typu stringstream a také pole text. 5.3.4. Funkce bool server_snd(char *, int) - Posílající data na stránku
Obrázek 19 - Hrubý vývojový diagram funkce server_snd()
Poslední funkce na cestě dat na stránku. Jejím vstupem jsou samotná data a jejich délka. Jako první se musí poslat délka dat v textové podobě. Proto nejdříve převedeme délku doteď uloženou v celočíselném datovém typu na řetězec znaků. Ten pak zakončíme znakem 'x' a pošleme na stránku. Poté už jen stačí poslat samotný text a jsme hotovi. Při
27
obou přenosech kontroluji jejich návratové hodnoty. Pokud dojde k chybě, vracím false. Jinak vracím true. 5.3.5. Internetová stránka index.php Stránka index.php je úvodní stránkou a zároveň slouží pro vstup dat. Obsahuje proto jednoduchý úvod a vstupní formulář. Ten se skládá z jednoho pole pro zadávání dat a tlačítka pro odeslání. Pomocí javascriptu by se měl kurzor automaticky nastavit do tohoto pole, aby mohl uživatel rovnou zadat hodnotu. Uživatel je vyzván, aby do tohoto pole napsal počet děr, které si přeje mít ve výsledné sudoku úloze. Formulář je poté odeslán metodou get na internetovou stránku send.php. Formulář obsahuje jednoduchý kód php, který si pamatuje naposled vyplněnou hodnotu, pokud použijeme odkaz zpět ze stránky send.php. 5.3.6. Internetová stránka send.php Tato stránka hojně využívá funkcí php. Nejdříve pomocí php zkontroluje vstupní data. Pokud jsou mimo rozsah nebo se nejedná o číslo, vypíše se chybové hlášení s odkazem zpět na úvodní stránku pro zadávání dat. Jinak se pokračuje dál. Povolí se PHP modul pro použití soketů php_sockets.dll a vytvoří se TCP soket pro výměnu dat se sudoku generátorem. Poté se pokusíme navázat spojení. Pokud neuspějeme, vypíšeme do stránky chybové hlášení a skončíme. Jinak vezmem vstupní data z formuláře, který jsme dostali od stránky index.php, přidáme za ně znak konce řádku '\n' a pošleme sudoku generátoru. Pokud se odeslání zdařilo, inicializujeme proměnné pro měření času. Poté provedeme první volání funkce recieve($socket), která nám vrátí první blok dat, který nám sudoku genrátor poslal. Pracuje tak, že nejprve přijímá po jednom znaky ze vstupu, dokud nenarazí na znak 'x'. To, co jsme do této doby přijali, udává délku bloku dat v bytech, který nám bude záhy poslán. Přijmáme tedy byty ze vstupu, dokud jich nepřijmeme daný počet. Poté tento blok dat (textu) vrátíme jako návratovou hodnotu. Změříme uplnyulý čas a tak do jisté míry změříme, jak rychlý byl generátor sudoku. (toto měření je jen orientační a není možné ho považovat za spolehlivý test výkonnosti). Poté se zavolá funkce recieve() ještě třikrát a tak obdržíme zbylé tři bloky dat. Nyní už zbývá jen data vypsat na stránku. První, druhý a čtvrtý blok je vypsán tak, jak jsme jej přijali. Na třetí blok je zavolána javasriptová funkce make_sol(), která z obdrženého kódu sestaví slovní popis postupu řešení. Zde bych rád zmínil, jak je uděláno předání proměnné (v našem případě třetího bloku dat) z PHP do javascriptu. Ze začátku mě tento problém totiž zarazil, ačkoliv je jeho řešení velmi jednoduché. PHP je vykonáváno ještě na straně serveru, což je tedy před tím, než se začne vykonávat javascript na straně klienta. Proto stačí, aby PHP zapsalo do stánky deklaraci proměnné v jazyce javascriptu a do této deklarace vypsalo hodnotu svojí proměnné. Dále je přidán odkaz, který funguje jako přepínač a schovává nebo odkrývá tabulku s úplným polem sudoku. Toto pole je na počátku pomocí javascriptu skryto. Nakonec je vypsán odkaz na nápovědu help.html, čas jak dlouho byla sudoku úloha genrována a odkaz zpět na úvodní stránku index.php pro zadávání vstupních dat.
28
5.4. Lokální verze
Obrázek 20 - Schéma práce lokálního rozhraní
Využívá jen C++ a standardní internetový prohlížeč. Tato verze komunikuje pomocí TCP protokolu přímo s internetovým prohlížečem. Funguje vlastně jako malý webový server, který vyřizuje žádosti internetového prohlížeče. To s sebou nese bezpečnostní rizika. Bezpečnost zajišťuje omezení připojení jen na lokální počítač (tj. adresu 127.0.0.1) a proto se k programu nelze připojit z okolních počítačů a využít případných bezpečnostních chyb. 5.4.1. Html žádosti Html žádost posílaná internetovým prohlížečem se skládá z několika řádků a používá různé metody. My však vystačíme jen s metodou GET. Jak název napovídá, jedná se o metodu, kterou internetový prohlížeč říká, že chce něco obdržet. Může vypadat například následovně: Pokud v prohlížeči firefox zadáme adresu našeho sudoku generátoru tj. http://localhost:5528 (popř. http://127.0.0.1:5528) pošle internetový prohlížeč žádost: GET / HTTP/1.1 Host: localhost:5528 User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.8.1.4) Gecko/20070515 Firefox/2.0.0.4 Accept: text/xml,application/xml,application/xhtml+xml,text/html;q=0.9,text/plain ;q=0.8,image/png,*/*;q=0.5 Accept-Language: en-us,en;q=0.5 Accept-Encoding: gzip,deflate Accept-Charset: ISO-8859-1,utf-8;q=0.7,*;q=0.7 Keep-Alive: 300 Connection: keep-alive
Pokud bychom požádali o nějaký soubor např. zadáním http://localhost:5528/soubor.txt bude žádost vypadat: GET /soubor.txt HTTP/1.1 Host: localhost:5528 ... Zbytek dotazu je zhruba stejný.
29
Pokud bychom poslali hodnotu nějaké proměnné metodou get např. zadáním http://localhost:5528/?num=55 bude žádost následující: GET /?num=55 HTTP/1.1 Host: localhost:5528 ... Zbytek dotazu je zhruba stejný.
Jak již bylo řečeno, může internetový prohlížeč používat i další typy žádostí, ovšem pro potřebu našeho rozhraní stačí výše uvedené a v rámci této práce proto nemá smysl studovat komunikaci internetového prohlížeče dopodrobna.
30
5.4.2. Zpracování žádostí
Obrázek 21 - Hrubý vývojový diagram zpracování žádostí
31
Sudoku generátor vstoupí do while cyklu, ve kterém se přijímají a vyřizují některé html žádosti. Nejdříve zavolá funkci bool server_accept(), která uspí celý program, než přijde nějaké spojení na TCP port 5528, na kterém sudoku generátor naslouchá. Pokud při tom dojde k chybě, vrací false, do konzole je vypsána zpráva „Selhal accept“ a jedno kolo generování je označeno za neúspěšné. Pokud bylo spojení přijato a ustaveno bez problémů, vstoupí se do druhého while cyklu pro načítání vstupních dat. Čteme vstupní data po řádcích pomocí funkce string ReceiveLine(), která načítá přijaté znaky, dokud nenarazí na znak konce řádku '\n'. Poté vrátí načtený řetězec. Čtení řádků ukončíme, pokud obdržíme prázdný řádek nebo dvojici znaků NF (new line feed - 0A) a CR (carriage return - 0D). To nám říká, že internetový prohlížeč již odeslal celý požadavek. Během načítání řádků jsme je analyzovali. Z pozorování je zřejmé, že první řádek žádosti GET má podobu GET /x HTTP/1.1, kde /x je část adresy zadané v internetovém prohlížeči, vyskytující se za doménovým jménem. Další řádky obsahují doplňující informace jako adresu, která byla zadána v prohlížeči, identifikaci prohlížeče, typ dat, která prohlížeč očekává a podobně. Jelikož neděláme přímo webový server, ale pouze jednoduché komunikační rozhraní, zajímá nás jen řádek začínající na GET, který nám říká, co prohlížeč chce. Zaměříme se tedy na tento řádek a analyzujeme část mezi 'GET /' a 'HTTP/1.1'. Podle našeho zjištění o jaký požadavek jde, byla nastavena proměnná get_num na patřičné číslo. Po skončení načítání vstupních řádků tedy zkontrolujeme proměnnou get_num, která nám řekne, co máme dále dělat. Pokud je nastavena na -1, znamená to, že žádný z přijatých řádků nezačínal na GET a celá žádost je brána jako neznámá. V takovém případě vypíšeme do konzole zprávu „Neznamy pozadavek“ a znovu vstoupíme do cyklu načítání žádosti. Jestli je get_num nastavena na 0, neobsahovala žádost žádné konkrétní upřesnění, co se žádá (GET / HTTP/1.1), což znamená, že v prohlížeči byla zadána jen samotná adresa sudoku generátoru, a proto prohlížeči pošleme, jak bývá zvykem, úvodní internetovou stránku index.html. Kde tuto stránku vzít? Původní vize byla taková, že stránka bude pevně uložena v programu a na rozdíl od internetové verze rozhraní nebude mít lokální verze prakticky žádnou možnost změny. Toto mi ale později přišlo velmi omezující a rozhodl se přidat více dynamiky. Ve stejném adresáři jako sudoku generátor se proto nachází soubor index.html. V tomto souboru je ona úvodní stránka v html kódu. Jako webový server můžeme internetovému prohlížeči poslat řadu údajů, jako je např. čas, jméno serveru, kód stavu apod. Pro naše skromné potřeby však tyto věci nepotřebujeme a proto se odešle jen kód, udávající jak byla žádost přijata. Nejprve se pokusíme soubor index.html otevřít. Pokud se nám to nepodaří, odešleme na stránku řádek „HTTP/1.1 404 Not Found“, kterým prohlížeči říkáme, že požadovaný soubor nebyl nalezen a poté řádek se zprávou „Soubor se strankou index.html nebyl nalezen“, který se již v prohlížeči zobrazí. Pokud se nám soubor se stránkou otevřít podaří, pošleme internetovému prohlížeči nejprve řádek „HTTP/1.1 202 OK“, který prohlížeči říká, že žádost byla úspěšně přijata a vyřízena. Dále se pošle řádek „Content-Type: text/html“, který vyžadují hlavně starší prohlížeče, aby stránka správně fungovala. Pak se již posílá soubor index.html. Je načítán po řádcích a stejně tak posílán internetovému prohlížeči. Jednotlivé řádky posíláme pomocí funkce bool SendLine(string), jejíž vstupní hodnotou je řetězec obsahující to, co se má poslat. Na konec tohoto řetězce je připojen znak konce řádku '\n' a celý je poslán internetovému prohlížeči. Pokud se přenos nezdaří, vrací false, jinak vrací true. Po přenesení souboru je spojení uzavřeno a internetový prohlížeč zobrazí to, co dostal, tj. kopii stránky index.html. Pokud se za 'GET /' vyskytuje otazník (GET /?num=55 HTTP/1.1), znamená to, že internetový prohlížeč odeslal nějaké proměnné metodou get. Proměnná get_num byla v tomto případě nastavena na 1. Za otazníkem se vyskytuje jméno proměnné a pak rovnítko a její hodnota. Pokud by bylo proměnných více, jsou oddělovány znakem '&'. Sudoku generátor na tomto řádku jednoduše najde první výskyt znaku '=' a poté se načítají
32
následující znaky, dokud se jedná o čísla (ascii hodnoty jsou mezi 48 a 57). Je tedy načtena hodnota první proměnné a je brána jako vstupní hodnota pro sudoku generátor. Na jméně proměnné nezáleží a pokud by byly poslány i další proměnné, budou ignorovány. Pokud máme vstupní data, opustíme cyklus čtení a obsluhování požadavků a provedeme test vstupních dat. Poté sudoku generátor provede patřičné výpočty a je připraven internetovému prohlížeči poslat stránku obsahující výsledky. Proces je podobný jako při přenosu úvodní stránky. Pokud není soubor send.html nalezen, je do konzole poslána zpráva „Soubor se strankou pro vysledek nenalezen“ a internetovému prohlížeči posláno „HTTP/1.1 404 Not Found“ a „Soubor se strankou pro vysledek nebyl nalezen“. V opačném případě se pošlou řádky „HTTP/1.1 202 OK“, „Server: Sudoku Generator“ a „Content-Type: text/html“ a pak se začne po řádcích číst a posílat soubor send.html, který se také nachází v adresáři u sudoku generátoru. Tento soubor však není posílán přesně tak, jak je napsán, protože do něj musíme ještě zapracovat výstupní data. V odesílaném souboru se vyskytují řádky, začínající na klíčové výrazy, které se poté nahradí výstupními daty. Proto můžeme do jisté míry ovládat umístění výstupních dat na stránce a měnit její vzhled, aniž bychom museli zasahovat přímo do generátoru sudoku. Rozpoznávané klíčové výrazy jsou: 'echo info' - nahradí se za výpis informací o generování. Odpovídá prvnímu bloku posílanému v internetové verzi rozhraní. Viz kapitola Přenášené bloky. 'echo tsudoku' - nahradí se za výpis sudoku úlohy i úplného pole sudoku zapsané ve formě html tabulky, což odpovídá druhému bloku. 'echo solution' - nahradí se za kódovaný postup řešení, odpovídající třetímu bloku. Z důvodu následného zpracování stránkou pomocí javascriptu je postup řešení zapsán ve tvaru: var reseni =„kódovaný_postup_řešení“; což ho přiřadí do javascriptové proměnné, se kterou bude možno nadále pracovat. 'echo lsudoku' - nahradí se za speciální výpis sudoku úlohy i úplného pole sudoku, odpovídá čtvrtému bloku. Ke generování výstupních dat a jejich poslání na stránku jsou použity stejné funkce, jako v případě výstupu internetového rozhraní. Tj. vypis_table(ostream&), vypis_line(ostream&), vypis_solve(ostream&) a bool vypis_sock(stringstream&). Ve funkci vypis_sock() je jen jedna změna, a to že po vstupních kontrolách a převodech je zavolána funkce bool SendLine(string) namísto bool server_snd(char *,int), jak tomu bylo u internetového rozhraní. Úvodní stránku index.html i stránku s výsledky send.html si může každý uživatel modifikovat v textovém editoru. To je ovšem jen na vlastní riziko, protože když např. nezkušený uživatel změní úvodní stránku tak, že nebude sudoku generátoru posílat žádná data, pak je jasné že neobdrží uspokojivé výsledky. Pokud žádost není předchozích dvou typů (prázdná nebo posílající proměnnou) je brána jako žádost o soubor a proměnná get_num je nastavena na 2. Jsou načteny všechny znaky za 'GET /'až do výskytu mezery. Načtená posloupnost znaků by pak měl být název (cesta k) souboru, který internetový prohlížeč žádá. Sudoku generátor bere cestu k souboru relativně od svého umístění a pokusí se daný soubor otevřít. Pokud otevírání selže, vypíše do konzole upozornění „Chyba pri otevirani souboru: název_souboru“ a internetovému prohlížeči pošle „HTTP/1.1 404 Not Found“ a zprávu „Chyba pri otevirani souboru“. Pokud se soubor najde, vypíše se do konzole zpráva „Posilam soubor: název_souboru“ a soubor se pošle internetovému prohlížeči. Takovými soubory jsou nejčastěji externí css styly a obrázky. Sudoku generátor nemá žádný seznam souborů, které může posílat, a tudíž se pokusí najít a poslat každý soubor, o který si internetový prohlížeč řekne, což umožňuje uživateli přidávat do stránek nové obrázky a kompletně tak měnit jejich vzhled. Soubory jsou posílány jako binární proud po datových blocích o velikosti, kterou udává konstanta
33
DATA_BUFFSIZE pomocí funkce bool sendBuf(int). Ta posílá byty z globálního bufferu, jejichž počet obdrží jako vstup. Při úspěšném přenosu vrací true, jinak je návratová hodnota false. 5.4.3. Internetová stránka index.html Je v podstatě shodná se stránkou index.php, používanou v internetové verzi. Rozdíl je jen v tom, že formulář neobsahuje žádný PHP kód a je odesílán na adresu http://localhost:5528, na které naslouchá přímo sudoku generátor. 5.4.4. Internetová stránka send.html Hlavní rozdíl oproti internetové verzi je, že u této verze se vůbec nepoužívá PHP. Tato stránka vlastně neutváří sama svůj obsah, ale slouží jen jako šablona pro sudoku generátor, který ji načítá a posílá internetovému prohlížeči. Je tedy na sudoku generátoru, aby do této stránky zakomponoval výstupní údaje. Kam je má přesně vypsat mu říkají pomocné značky, začínající na klíčové slovo echo. Tyto značky jsou pak odstraněny a nahrazeny výstupními daty. Ačkoliv je tedy rozdíl těchto stránek v obou verzích značný, ve výsledku vypadají téměř stejně. Tato verze jen neobsahuje měření času (protože ho zajišťuje PHP a to zde chybí). Využívá ovšem javascript, a tak opět nechybí předělání kódu postupu řešení na slovní popis, ani zobrazování a skrývání úplného pole sudoku.
6. Testování Nejdříve byla testována funkčnost sudoku generátoru na různých prohlížečích. Tento test se týkal hlavně lokální verze, protže u internetové se o spojení s prohlížečem stará webový server. Pro testování programu byly použity 3 v dnešní době nejpoužívanější webové prohlížeče. Internet Explorer 6, Mozilla Firefox 2.0.0.4 a Opera 9.1 a 7.02. Byly tedy zastoupeny jak nejnovější, tak i poněkud starší prohlížeče. Testování jsem prováděl jednak z důvodu ověření, jestli si sudoku generátor v lokální verzi bude dobře rozumět s různými prohlížeči a také abych zkontroloval, jestli je na všech prohlížečích správně zobrazena grafika stránek, utvořená pomocí css. Je totiž známé, že různé prohlížeče si css vykládají každý trochu po svém a jedna věc může na různých prohlížečích vypadat úplně jinak. Při komunikaci mezi sudoku generátorem a výše zmíněnými prohlížeči nebyly zjištěny žádné potíže. Grafika stránek se, jak se dalo očekávat, na různých prohlížečích mírně liší, ale jedná se o drobné detaily (odchylky barvy vnitřních mřížek tabulek apod.), které nijak nenarušují pohodlnou práci se stránkou nebo její funkci. Druhou částí testu byla samotná funkčnost sudoku generátoru, tj. jestli dává smysluplné výsledky v souladu se zadáním. Zadávány byly různé vstupní hodnoty (byly zastoupeny malé, velké i chybné hodnoty). Výstup se vždy ukázal tak jak měl a nedocházelo k žádným potížím. Průběh jednoho testu: Na vstupu bylo zadáno číslo 60. Sudoku generátor vytvořil úlohu s 57 dírami, viz obrázek 22 a 23.
34
1 9 4 8 5 1 7 2 6 3
2 2 7 6 4 3 8 9 5 1
3 5 3 1 9 2 6 8 4 7
4 1 2 4 6 5 3 7 9 8
5 6 5 9 7 8 2 3 1 4
6 3 8 7 1 9 4 5 2 6
7 4 6 2 8 7 5 1 3 9
8 7 9 5 3 4 1 6 8 2
9 8 1 3 2 6 9 4 7 5
1 2 3 4 5 6 7 8 9 1 5 2 2 8 9 3 9 2 3 4 8 5 3 2 7 6 6 4 1 9 7 9 8 5 1 8 5 7 9 3 6 5
1 2 3 4 5 6 7 8 9
Obrázek 22 - Vygenerovaná sudoku úloha
Obrázek 23 - Vygenerované úplné pole sudoku
Dále navrhl tento postup řešení: Buňka v 1. řádku a 1. sloupci nemá ve svém řádku jinou možnost umístění čísla 9, a proto ho musíme zapsat právě sem Buňka v 1. řádku a 2. sloupci nemá ve svém řádku jinou možnost umístění čísla 2, a proto ho musíme zapsat právě sem Ve všech buňkách v 2. boxu a mimo 1. řádek se odstraňuje kandidát 3, protože daný box musí mít tuto hodnotu někde v tomto řádku Buňka v 1. řádku a 9. sloupci nemá ve svém sloupci jinou možnost umístění čísla 8, a proto ho musíme zapsat právě sem Buňka v 2. řádku a 3. sloupci nemá ve svém řádku jinou možnost umístění čísla 3, a proto ho musíme zapsat právě sem Buňka v 2. řádku a 9. sloupci nemá ve svém sloupci jinou možnost umístění čísla 1, a proto ho musíme zapsat právě sem Ve všech buňkách v 3. řádku a mimo 1. box se odstraňuje kandidát 8, protože daný box musí mít tuto hodnotu někde v tomto řádku Buňka v 4. řádku a 3. sloupci nemá ve svém sloupci jinou možnost umístění čísla 9, a proto ho musíme zapsat právě sem Ve všech buňkách v 4. řádku a mimo 6. box se odstraňuje kandidát 2, protože daný box musí mít tuto hodnotu někde v tomto řádku Buňka v 6. řádku a 5. sloupci nemá ve svém řádku jinou možnost umístění čísla 2, a proto ho musíme zapsat právě sem Ve všech buňkách v 7. boxu a mimo 1. sloupec se odstraňuje kandidát 2, protože daný box musí mít tuto hodnotu někde v tomto sloupci Buňka v 8. řádku a 6. sloupci nemá ve svém sloupci jinou možnost umístění čísla 2, a proto ho musíme zapsat právě sem Ve všech buňkách v 8. sloupci a mimo 9. box se odstraňuje kandidát 8, protože daný box musí mít tuto hodnotu někde v tomto sloupci Buňka v 9. řádku a 8. sloupci nemá ve svém řádku jinou možnost umístění čísla 2, a proto ho musíme zapsat právě sem Ve všech buňkách v 2. boxu a mimo 1. řádek se odstraňuje kandidát 1, protože daný box musí mít tuto hodnotu někde v tomto řádku Do buňky v 3. řádku a 6. sloupci byla doplněna hodnota 7, protože je to poslední kandidát Buňka v 4. řádku a 9. sloupci nemá ve svém řádku jinou možnost umístění čísla 2, a proto ho musíme zapsat právě sem Buňka v 5. řádku a 6. sloupci nemá ve svém sloupci jinou možnost umístění čísla 9, a proto ho musíme zapsat právě sem Ve všech buňkách v 8. sloupci a mimo 6. box se odstraňuje kandidát 4, protože daný box musí mít tuto hodnotu někde v tomto sloupci
35
Buňka v 7. řádku a 9. sloupci má ve svém okolí všechny hodnoty kromě 4, a proto tam musí být jen toto číslo Ve všech buňkách v 4. sloupci a mimo 8. box se odstraňuje kandidát 9, protože daný box musí mít tuto hodnotu někde v tomto sloupci Buňka v 8. řádku a 8. sloupci nemá ve svém sloupci jinou možnost umístění čísla 8 a proto ho musíme zapsat právě sem Ve všech buňkách v 8. boxu a mimo 9. řádek se odstraňuje kandidát 8, protože daný box musí mít tuto hodnotu někde v tomto řádku Buňka v 9. řádku a 7. sloupci má ve svém okolí všechny hodnoty kromě 9 a proto tam musí být jen toto číslo Buňka v 1. řádku a 8. sloupci nemá ve svém řádku jinou možnost umístění čísla 7, a proto ho musíme zapsat právě sem Buňka v 7. řádku a 1. sloupci nemá ve svém řádku jinou možnost umístění čísla 2, a proto ho musíme zapsat právě sem Ve všech buňkách v 8. boxu a mimo 7. řádek se odstraňuje kandidát 7, protože daný box musí mít tuto hodnotu někde v tomto řádku Buňka v 7. řádku a 8. sloupci nemá ve svém řádku jinou možnost umístění čísla 6, a proto ho musíme zapsat právě sem Ve všech buňkách v 8. řádku a mimo 7. box se odstraňuje kandidát 6, protože daný box musí mít tuto hodnotu někde v tomto řádku Buňka v 8. řádku a 7. sloupci má ve svém okolí všechny hodnoty kromě 3, a proto tam musí být jen toto číslo Ve všech buňkách v 3. boxu a mimo 7. sloupec se odstraňuje kandidát 6, protože daný box musí mít tuto hodnotu někde v tomto sloupci Do buňky v 3. řádku a 8. sloupci byla doplněna hodnota 5, protože je to poslední kandidát Buňka v 4. řádku a 8. sloupci nemá ve svém sloupci jinou možnost umístění čísla 3, a proto ho musíme zapsat právě sem Ve všech buňkách v 5. boxu a mimo 4. sloupec se odstraňuje kandidát 5, protože daný box musí mít tuto hodnotu někde v tomto sloupci Buňka v 5. řádku a 8. sloupci má ve svém okolí všechny hodnoty kromě 4, a proto tam musí být jen toto číslo Buňka v 6. řádku a 7. sloupci má ve svém okolí všechny hodnoty kromě 5, a proto tam musí být jen toto číslo Ve všech buňkách v 8. boxu a mimo 7. řádek se odstraňuje kandidát 3, protože daný box musí mít tuto hodnotu někde v tomto řádku Buňka v 8. řádku a 4. sloupci nemá ve svém řádku jinou možnost umístění čísla 9, a proto ho musíme zapsat právě sem Buňka v 2. řádku a 5. sloupci nemá ve svém sloupci jinou možnost umístění čísla 5, a proto ho musíme zapsat právě sem Ve všech buňkách v 4. boxu a mimo 4. řádek se odstraňuje kandidát 4, protože daný box musí mít tuto hodnotu někde v tomto řádku Buňka v 4. řádku a 6. sloupci má ve svém okolí všechny hodnoty kromě 1 a proto tam musí být jen toto číslo Buňka v 5. řádku a 5. sloupci má ve svém okolí všechny hodnoty kromě 8 a proto tam musí být jen toto číslo Buňka v 6. řádku a 4. sloupci nemá ve svém řádku jinou možnost umístění čísla 3, a proto ho musíme zapsat právě sem Buňka v 7. řádku a 4. sloupci má ve svém okolí všechny hodnoty kromě 7, a proto tam musí být jen toto číslo Buňka v 7. řádku a 5. sloupci má ve svém okolí všechny hodnoty kromě 3, a proto tam musí být jen toto číslo Buňka v 1. řádku a 6. sloupci má ve svém okolí všechny hodnoty kromě 3, a proto tam musí být jen toto číslo Ve všech buňkách v 4. řádku a mimo 5. box se odstraňuje kandidát 6, protože daný box musí mít tuto hodnotu někde v tomto řádku Buňka v 4. řádku a 5. sloupci nemá ve svém sloupci jinou možnost umístění čísla 7, a proto ho musíme zapsat právě sem Buňka v 5. řádku a 1. sloupci nemá ve svém řádku jinou možnost umístění čísla 1, a proto ho musíme zapsat právě sem Buňka v 5. řádku a 4. sloupci má ve svém okolí všechny hodnoty kromě 5, a proto tam musí být jen toto číslo Ve všech buňkách v 4. boxu a mimo 6. řádek se odstraňuje kandidát 7, protože daný box musí mít tuto hodnotu někde v tomto řádku Do buňky v 4. řádku a 2. sloupci byla doplněna hodnota 4, protože je to poslední kandidát Buňka v 9. řádku a 4. sloupci nemá ve svém řádku jinou možnost umístění čísla 8, a proto ho musíme zapsat právě sem Ve všech buňkách v 5. sloupci a mimo 8. box se odstraňuje kandidát 4, protože daný box musí mít tuto hodnotu někde v tomto sloupci Buňka v 1. řádku a 4. sloupci nemá ve svém sloupci jinou možnost umístění čísla 1, a proto ho musíme zapsat právě sem
36
V buňce v 1. řádku a 5. sloupci byly kvůli buňkám v jejím okolí odstraněny všechny zbylé kandidáty až na číslo 6, a proto tam musí být jen toto číslo Buňka v 1. řádku a 7. sloupci má ve svém okolí všechny hodnoty kromě 4, a proto tam musí být jen toto číslo Buňka v 2. řádku a 7. sloupci má ve svém okolí všechny hodnoty kromě 6, a proto tam musí být jen toto číslo Buňka v 3. řádku a 4. sloupci má ve svém okolí všechny hodnoty kromě 4, a proto tam musí být jen toto číslo V buňce v 4. řádku a 1. sloupci byly kvůli buňkám v jejím okolí odstraněny všechny zbylé kandidáty až na číslo 5, a proto tam musí být jen toto číslo Buňka v 4. řádku a 4. sloupci má ve svém okolí všechny hodnoty kromě 6, a proto tam musí být jen toto číslo Buňka v 2. řádku a 1. sloupci nemá ve svém řádku jinou možnost umístění čísla 4, a proto ho musíme zapsat právě sem Buňka v 2. řádku a 2. sloupci má ve svém okolí všechny hodnoty kromě 7, a proto tam musí být jen toto číslo Buňka v 6. řádku a 1. sloupci nemá ve svém sloupci jinou možnost umístění čísla 7, a proto ho musíme zapsat právě sem Buňka v 6. řádku a 2. sloupci nemá ve svém řádku jinou možnost umístění čísla 8, a proto ho musíme zapsat právě sem Buňka v 6. řádku a 3. sloupci má ve svém okolí všechny hodnoty kromě 6, a proto tam musí být jen toto číslo Buňka v 8. řádku a 1. sloupci má ve svém okolí všechny hodnoty kromě 6, a proto tam musí být jen toto číslo Buňka v 9. řádku a 2. sloupci má ve svém okolí všechny hodnoty kromě 1, a proto tam musí být jen toto číslo Buňka v 9. řádku a 3. sloupci nemá ve svém řádku jinou možnost umístění čísla 7, a proto ho musíme zapsat právě sem Buňka v 9. řádku a 5. sloupci má ve svém okolí všechny hodnoty kromě 4, a proto tam musí být jen toto číslo Buňka v 3. řádku a 1. sloupci má ve svém okolí všechny hodnoty kromě 8, a proto tam musí být jen toto číslo Buňka v 3. řádku a 2. sloupci má ve svém okolí všechny hodnoty kromě 6, a proto tam musí být jen toto číslo Buňka v 3. řádku a 3. sloupci má ve svém okolí všechny hodnoty kromě 1, a proto tam musí být jen toto číslo Buňka v 8. řádku a 3. sloupci má ve svém okolí všechny hodnoty kromě 4, a proto tam musí být jen toto číslo Buňka v 8. řádku a 5. sloupci má ve svém okolí všechny hodnoty kromě 1, a proto tam musí být jen toto číslo
Jak je vidět z tohoto řešení, každá buňka byla doplněna a její hodnota byla vždy logicky odvozena podle pravidel hry sudoku jako jediná možná. Proto je také zaručeno jednoznačné řešení této úlohy. Obdobně probíhaly ostatní zkoušky, a proto mohu celý test označit za úspěšný. Z několika spuštění programu je dále vidět, že nejpoužívanější metodou je Cross Hatching a po ní Forced Digit. Locked Candidates X jsou použity jen zřídka a ke zvýšení možného počtu děr, které je program schopen udělat, moc nepřispívají. Měřením bylo dále zjištěno, že pomocí těchto metod je sudoku generátor schopen udělat průměrně 56 děr. Jelikož se nejedná o příliš složité metody, mohou být vygenerované sudoku úlohy označeny jako středně těžké.
7. Závěr Cílem této práce bylo seznámit se s různými metodami generování a řešení sudoku úlohy. O těchto metodách píši v kapitole 4.1 Volba algoritmů. Na základě těchto studií jsem pak měl vytvořit program pro generování sudoku úlohy s jedinečným řešením. Program generující sudoku úlohu jsem vytvořil, jak se ostatně lze přesvědčit na 43. To, jak je zaručeno, že výsledná sudoku úloha má jednoznačné řešení, je vysvětleno v Popis algoritmů. Proto, pokud jsem neudělal chybu při implementaci těchto algoritmů, mělo by být toto zadání splněno. Kromě úplné sudoku úlohy vytváří sudoku generátor také možný postup řešení, vedoucí k jejímu vyluštění. Jako programovací jazyk byl zvolen C++ a programovacím nástrojem Microsoft Visual Studio 2005. Generátor sudoku byl vyvíjen pod operačním systémem Microsoft Windows XP a je tudíž kompilován pro windowsovou platformu. Posledním úkolem bylo vytvořit webové rozhraní. Toto rozhraní nakonec existuje ve dvou verzích a tudíž i celý sudoku generátor se dělí na verzi lokální a internetovou. Jelikož
37
si jsou obě verze podobné, jsou obě umístěny do jednoho souboru se zdrojovým kódem. Jaká verze se bude kompilovat, určuje definice konstanty SERVER. Je li definována, bude výsledná verze internetová, v opačném případě se bude jednat o verzi lokální. Další program, použitý při vývoji, byl webový server Apache 2.2.4 s podporou PHP 5.2.1. Sudoku generátor je ale koncipován tak, aby pracoval s libovolným webovým serverem s podporou PHP páté řady a s intnernetovým prohlížečem podporujícím css 2.1. Podpora javascriptu není nutným požadavkem, ale přináší doplňkové funkce, které webové rozhraní zpříjemňují, a proto je doporučena. V budoucnu by bylo dobré doplnit podporu dalších řešících metod a zvýšit tak obtížnost výsledných sudoku úloh. Do rozhraní by se dalo přidat ještě více interaktivity pomocí javascriptu, aby bylo např. možné luštit sudoku přímo v internetovém prohlížeči.
38
8. Seznam použité literatury [1] Sudoku Solving Guide (http://www.sudocue.net/guide.php) [2] Wikipedia, the free encyclopedia (http://en.wikipedia.org) [3] Sudoku Programmers forum (http://www.setbb.com/phpbb/index.php?sid=7dcc0f60cf56ec10fce35cca2fa82289&mforu m=sudoku) [4] C/C++ Reference (http://www.cppreference.com/) [5] The C++ Resources Network (http://www.cplusplus.com/)
39
40
A) Uživatelská příručka Sudoku generátor je program pro generování sudoku úlohy a možného postupu, jak ji vyřešit. Existuje ve dvou verzích. Internetová verze, kterou můžete umístit na svůj server a poskytovat uživatelům služby generování sudoku úloh, nebo lokální verze, která je určena pro domácí užití. A.1 Instalace a spuštění Jelikož byly programy kompilovány v programu Microsoft Visual Studio 2005, je někdy nutné pro jejich spuštění nainstalovat Microsoft Visual C++ 2005 Redistributable Package. Jeho verzi pro procesory x86 naleznete například zde http://www.microsoft.com/downloads/details.aspx?FamilyID=32bc1bee-a3f9-4c13-9c99220b62a191ee&DisplayLang=en A.1.1 Internetová verze Tato instalace je složitější a vyžaduje jistou míru znalostí. Pokud jste normální uživatel a chcete používat sudoku generátor jen pro své potřeby, přeskočte na návod spuštění lokální verze. Pro internetovou verzi je třeba mít webový server. Je jedno jaký. Hlavní je, aby byl správně nakonfigurován. Potřebné internetové stránky se nacházejí na přiloženém CD v adresáři \exe\1-Internet\web_files\. Webový server je tedy nutné nastavit tak, aby soubory v tomto adresáři byly přístupné uživatelům, kteří se k nim budou snažit přistoupit ze sítě internet. Dále je na tomto serveru třeba mít nainstalováno PHP páté řady nebo vyšší a zapnutu podporu modulu pro komunikaci pomocí soketů (tj. extension=php_sockets.dll). Poté již stačí spustit program, který je umístěný na CD v \exe\1-Internet\sudokuinternet.exe a vše je připraveno. Jakou adresu musí uživatelé zadat do internetového prohlížeče, aby se jim zobrazila úvodní stránka, záleží na nastavení vašeho webového serveru. A.1.2 Lokální verze Tato verze nevyžaduje žádnou speciální instalaci. Stačí jen spustit program umístěný na CD v \exe\2-Local\sudoku-local.exe a do internetového prohlížeče zadat adresu http://localhost:5528/ (popřípadě http://127.0.0.1:5528/ ). Poté se již zobrazí úvodní stránka a s programem je možné dále pracovat. A.2 Obsluha Obě verze programu jsou z hlediska obsluhy téměř totožné, a proto je nebudu popisovat zvlášť. Práce s nimi je velice jednoduchá. Na úvodní stránce jste vyzváni, abyste zadali maximální počet děr, které má výsledná sudoku úloha mít. Hodnoty zadávejte celými čísly v rozsahu 0 až 81. Poté klepněte na tlačítko odeslat. Za okamžik by se měla objevit stránka
41
s výsledky. Ta obsahuje tabulku se sudoku úlohou a druhou tabulku s vyřešenou úlohou, která ale není vidět. Pro její zobrazení stačí klepnout na odkaz „ Klikni pro zobrazení/skrytí vyplněného pole sudoku“ pod tabulkou se sudoku úlohou. Jak název odkazu napovídá, po opětovném kliknutí je vyřešená sudoku úloha opět skryta. Poté je vypsán možný postup řešení. Řádky psané oranžově informují o odebrání buňky. Modré říkají, že byly odstraněny nějaké kandidáty. Pod výpisem řešení je umístěn odkaz na nápovědu, kde se dozvíte, jak se sudoku úloha vlastně luští a jakými metodami toho můžete dosáhnout. Dále jsou na stránce ještě dva souvislé řádky čísel. Ty nejsou nic jiného, než sudoku úloha a vyplněná sudoku úloha, zapsané do řádkové formy, která je přenositelná do některých programů. Nakonec je zobrazen odkaz Zpět, který nás vrátí na úvodní stránku. U internetové verze je ještě vypsán údaj, jak dlouho generování sudoku úlohy trvalo. Aby fungovaly věci jako je schovávání vyřešené sudoku úlohy nebo generování postupu řešení, je nutné mít v internetovém prohlížeči povoleno používání javascriptu. Ovšem i bez něj jsou stránky sice ochuzené, ale funkční.
42
B) Obsah přiloženého CD CD obsahuje tyto adresáře: /exe/ - Adresář obsahující obě verze programu ve spustitelné podobě /1-Internet/ - Adresář s internetovou verzí /web_files/ - Adresář se soubory pro webové rozhraní. Nutné nastavit webový server tak, aby byl tento adresář přístupný z internetu /data/ - Obsahuje externí css styl a obrázky používané na všech stránkách / help_soubory/ - Obsahuje obrázky používáné na stránce s nápovědou /2-Local/ - Adresář s lokální verzí /data/ - Obsahuje externí css styl a obrázky používané na všech stránkách /help_soubory/ - Obsahuje obrázky používáné na stránce s nápovědou /src/ - Obsahuje celý projekt (tj. zdrojové kódy). Jedná se o projekt programu Microsoft Visual Studio 2005. /html/ - Adresář obsahující data pro stránku index.html /index.html – Soubor obsahující odkazy na obsah tohoto CD /masekj3_bc.pdf - Soubor obsahující tuto práci ve formátu pdf /masekj3_bc.doc - Soubor obsahující tuto práci ve formátu pro Microsoft Word
43
