VYSOKÉ UČENÍ TECHNICKÉ V BRNĚ BRNO UNIVERSITY OF TECHNOLOGY
FAKULTA ELEKTROTECHNIKY A KOMUNIKAČNÍCH TECHNOLOGIÍ ÚSTAV BIOMEDICÍNSKÉHO INŽENÝRSTVÍ FACULTY OF ELECTRICAL ENGINEERING AND COMMUNICATION DEPARTMENT OF BIOMEDICAL ENGINEERING
SUDOKU - ALGORITMIZACE ŘEŠENÍ
BAKALÁŘSKÁ PRÁCE BACHELOR'S THESIS
AUTOR PRÁCE AUTHOR
BRNO 2013
MARTIN BUCHTA
VYSOKÉ UČENÍ TECHNICKÉ V BRNĚ BRNO UNIVERSITY OF TECHNOLOGY
FAKULTA ELEKTROTECHNIKY A KOMUNIKAČNÍCH TECHNOLOGIÍ ÚSTAV BIOMEDICÍNSKÉHO INŽENÝRSTVÍ FACULTY OF ELECTRICAL ENGINEERING AND COMMUNICATION DEPARTMENT OF BIOMEDICAL ENGINEERING
SUDOKU - ALGORITMIZACE ŘEŠENÍ SUDOKU - ALGORITHMIZATION OF SOLUTION
BAKALÁŘSKÁ PRÁCE BACHELOR'S THESIS
AUTOR PRÁCE
MARTIN BUCHTA
AUTHOR
VEDOUCÍ PRÁCE SUPERVISOR
BRNO 2013
Ing. MARTIN MÉZL
VYSOKÉ UČENÍ TECHNICKÉ V BRNĚ Fakulta elektrotechniky a komunikačních technologií Ústav biomedicínského inženýrství
Bakalářská práce bakalářský studijní obor Biomedicínská technika a bioinformatika Student: Ročník:
Martin Buchta 3
ID: 136463 Akademický rok: 2012/2013
NÁZEV TÉMATU:
Sudoku - algoritmizace řešení POKYNY PRO VYPRACOVÁNÍ: 1) Seznamte se s principem a zadáním úlohy Sudoku. 2) Proveďte literární rešerši různých metod pro řešení této úlohy. 3) V programovém prostředí Matlab implementujte vybrané algoritmy pro řešení této úlohy. 4) Navrhněte vhodné grafické rozhraní pro zadávání úloh a grafický výstup řešení, popř. mapování řešení v jednotlivých iteracích. 5) Úlohu doplňte o možnost zadání úlohy s využitím webkamery. Pro obsluhu webkamery použijte Image Acquisition Toolbox v Matlabu. Metodu pro rozpoznání čísel v tabulce zvolte po domluvě s vedoucím. 6) Proveďte srovnání implementovaných metod s metodou úplného prohledávání - brute force. DOPORUČENÁ LITERATURA: [1] CROOK, J.F. A Pencil-and-Paper Algorithm for Solving Sudoku Puzzles. Notice of the AMS, 2009, vol. 56, no. 4, s. 460-468. [2] FIALA, Petr. Operační výzkum: nové trendy. 1. vyd. Praha: Professional Publishing, 2010, 239 s. ISBN 978-80-7431-036-2. Termín zadání:
11.2.2013
Termín odevzdání:
31.5.2013
Vedoucí práce: Ing. Martin Mézl Konzultanti bakalářské práce:
prof. Ing. Ivo Provazník, Ph.D. Předseda oborové rady UPOZORNĚNÍ: Autor bakalářské práce nesmí při vytváření bakalářské práce porušit autorská práva třetích osob, zejména nesmí zasahovat nedovoleným způsobem do cizích autorských práv osobnostních a musí si být plně vědom následků porušení ustanovení § 11 a následujících autorského zákona č. 121/2000 Sb., včetně možných trestněprávních důsledků vyplývajících z ustanovení části druhé, hlavy VI. díl 4 Trestního zákoníku č.40/2009 Sb.
ABSTRAKT V této práci se nachází přehled lidmi použitelných technik pro řešení logické hry Sudoku. Jednotlivé algoritmy zde byly teoreticky popsány na reálných zadáních a na tomto základě byly implementovány do vhodného grafického rozhraní navrženého v prostředí Matlab s možností načítání zadání pomocí webkamery.
KLÍČOVÁ SLOVA Sudoku, Algoritmus, Kandidát, Webkamera, Grafické uživatelské rozhraní
ABSTRACT In this paper, we present an overview of techniques that can be used by people to solve a Sudoku Puzzle. The individual algorithms were theoretically described using real tasks and were implemented on this basis to appropriate graphical user interface in Matlab with the possibility of webcam task loading.
KEYWORDS Sudoku, Algorithm, Candidate, Webcam, Graphical user interface
BUCHTA, Martin Sudoku - algoritmizace řešení: bakalářská práce. V Brně: Vysoké učení technické v Brně, Fakulta elektrotechniky a komunikačních technologií, Ústav biomedicínského inženýrství, 2013. 46 s. Vedoucí práce byl Ing. Martin Mézl
PROHLÁŠENÍ Prohlašuji, že svou bakalářskou práci na téma „Sudoku - algoritmizace řešení“ jsem vypracoval samostatně pod vedením vedoucího bakalářské práce a s použitím odborné literatury a dalších informačních zdrojů, které jsou všechny citovány v práci a uvedeny v seznamu literatury na konci práce. Jako autor uvedené bakalářské práce dále prohlašuji, že v souvislosti s vytvořením této bakalářské práce jsem neporušil autorská práva třetích osob, zejména jsem nezasáhl nedovoleným způsobem do cizích autorských práv osobnostních a/nebo majetkových a jsem si plně vědom následků porušení ustanovení S 11 a následujících autorského 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), ve znění pozdějších předpisů, včetně možných trestněprávních důsledků vyplývajících z ustanovení části druhé, hlavy VI. díl 4 Trestního zákoníku č. 40/2009 Sb.
V Brně
...............
.................................. (podpis autora)
PODĚKOVÁNÍ Rád bych poděkoval vedoucímu semestrálního projektu panu Ing. Martinu Mézlovi za odborné vedení, konzultace, trpělivost a cenné rady.
V Brně
...............
.................................. (podpis autora)
OBSAH Úvod
9
1 Sudoku 10 1.1 Základní pravidla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2 Zadání . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2 Algoritmy 2.1 Kandidáti . . . . . . . . . . . . . . . . 2.1.1 Realizace v prostředí Matlab . . 2.2 Vazby a odkazy (Chains and Links) . . 2.3 Lidské dosazovací algoritmy . . . . . . 2.3.1 Algoritmus Singles . . . . . . . 2.3.2 Algoritmus Hidden singles . . . 2.4 Lidské eliminační algoritmy . . . . . . 2.4.1 Algoritmus Naked candidates . 2.4.2 Algoritmus Hidden candidates . 2.4.3 Algoritmus Pointing candidates 2.4.4 Algoritmus Box/Line reduction 2.4.5 Algoritmus X-Wing . . . . . . . 2.4.6 Algoritmus Y-Wing . . . . . . . 2.5 Rekurzivní algoritmy . . . . . . . . . . 2.5.1 Algoritmus Brute force . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
. . . . . . . . . . . . . . .
12 12 12 13 15 15 16 16 16 19 20 20 21 22 23 24
3 Hardware a software
26
4 Zpracování obrazu 4.1 Detekce Sudoku mřížky . . . . . . . . 4.1.1 Prahování obrazu . . . . . . . 4.1.2 Pozice Sudoku . . . . . . . . . 4.2 Transformace obrazu . . . . . . . . . 4.2.1 Projektivní transformace . . . 4.2.2 Segmentace a příprava obrazu 4.3 Detekce čísel . . . . . . . . . . . . . . 4.3.1 Eulerovo číslo . . . . . . . . . 4.4 Ideální podmínky . . . . . . . . . . .
27 27 27 29 29 29 30 31 32 33
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
. . . . . . . . .
5 Grafické prostředí 5.1 Hrací plocha . . . . . . . . . . 5.2 Nastavení zdroje videosignálu 5.3 Načítání z obrazu . . . . . . . 5.4 Menu . . . . . . . . . . . . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
35 35 36 37 37
6 Dosažené výsledky
39
7 Závěr
40
Literatura
41
Seznam příloh
43
A Elektronická část bakalářské práce A.1 Funkce naprogramované v prostředí A.1.1 Algoritmy . . . . . . . . . . A.1.2 Grafické prostředí . . . . . A.1.3 Zpracování obrazu . . . . . A.1.4 Ostatní pomocné funkce . . A.2 Elektronická verze bakalářské práce
44 44 44 44 44 44 45
B Návod ke grafickému prostředí
Matlab . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
46
SEZNAM OBRÁZKŮ 1.1 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 2.10 2.11 2.12 2.13 2.14 4.1 4.2 4.3 4.4 4.5 4.6 4.7 5.1 5.2 5.3 5.4 B.1
Zadání sudoku s rozdělením na jednotlivé bloky a jeho řešení. . . Zadání Sudoku se zobrazenými kandidáty a způsob jejich uložení matici. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Bi-Location a Bi-Value odkazy. . . . . . . . . . . . . . . . . . . . Druhy vazeb mezi odkazy. . . . . . . . . . . . . . . . . . . . . . . Vztah buď a nebo. . . . . . . . . . . . . . . . . . . . . . . . . . . Algoritmus Singles. . . . . . . . . . . . . . . . . . . . . . . . . . . Algoritmus Hidden singles. . . . . . . . . . . . . . . . . . . . . . . Algoritmus Naked pairs. . . . . . . . . . . . . . . . . . . . . . . . Algoritmus Naked triples. . . . . . . . . . . . . . . . . . . . . . . Algoritmus Hidden pairs. . . . . . . . . . . . . . . . . . . . . . . . Algoritmus Pointing candidates. . . . . . . . . . . . . . . . . . . . Algoritmus Box/Line reduction. . . . . . . . . . . . . . . . . . . . Algoritmus X-Wing. . . . . . . . . . . . . . . . . . . . . . . . . . Algoritmus Y-Wing. . . . . . . . . . . . . . . . . . . . . . . . . . Vývojový diagram algoritmu Brute force. . . . . . . . . . . . . . . Vývojový diagram zpracování obrazu. . . . . . . . . . . . . . . . . Převod na černobílý obrázek. . . . . . . . . . . . . . . . . . . . . Detekce rohů mřížky Sudoku. . . . . . . . . . . . . . . . . . . . . Projektivní transformace. . . . . . . . . . . . . . . . . . . . . . . . Morfologická oprava. . . . . . . . . . . . . . . . . . . . . . . . . . Vzory čísel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ideální podmínky. . . . . . . . . . . . . . . . . . . . . . . . . . . . Schéma grafického prostředí. . . . . . . . . . . . . . . . . . . . . . Hrací plocha. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Nastavení zdroje videosignálu. . . . . . . . . . . . . . . . . . . . . Načítání z obrazu. . . . . . . . . . . . . . . . . . . . . . . . . . . Návod ke grafickému prostředí. . . . . . . . . . . . . . . . . . . .
. v . . . . . . . . . . . . . . . . . . . . . . . . . .
. 11 . . . . . . . . . . . . . . . . . . . . . . . . . .
13 14 14 15 15 16 17 18 19 20 21 22 23 25 28 29 30 31 31 32 34 35 36 36 37 46
ÚVOD Sudoku je logická doplňovací hra, která je v současné době pro svá nepříliš složitá pravidla a mnoho stupňů obtížnosti velmi oblíbená u velkého množství lidí. Cílem této práce bylo vytvořit některé z algoritmů pro řešení úlohy Sudoku v programovém prostředí Matlab. Pro realizaci byly zvoleny algoritmy, které napodobují lidské myšlení. Práce se nejprve věnuje obecnému popisu úlohy Sudoku, základním pravidlům a podmínkám, které musí Sudoku splňovat. Následuje krátké zamyšlení ohledně výběru algoritmů a poté popis principu funkčnosti. Algoritmy jsou zobrazeny a vysvětleny na skutečných zadáních. Vybrané části realizovaných algoritmů, jež se jeví z programovacího hlediska zajímavé, jsou v této práci taktéž zmíněny. Vše je zapracováno do vhodného grafického prostředí, které umožňuje přehledné procházení různých zadání Sudoku a jejich postupného, či úplného řešení pomocí vybraných algoritmů. Práce je dále doplněna o možnost načítání zadání Sudoku pomocí webkamery.
9
1
SUDOKU
Veškerá zadání Sudoku byla čerpána ze [4], ale v rámci ukázky některých algoritmů byla částečně upravena. Sudoku je původem z Ameriky. Vymyslel je a publikoval Howard Garns v roce 1979. Opravdového rozšíření se dočkalo až v posledních letech v Evropě, kam se dostalo z Japonska. Původní název hry Number Place byl později nahrazen japonskou zkratkou slov Suuji wa dokushin ni kagiru, což by se dalo přeložit jako každé číslo pouze jednou [6].
1.1
Základní pravidla
Základem Sudoku je 81 hracích polí uspořádaných do tabulky o rozměrech 9 x 9 políček, která se dále dělí na jednotlivé sloupce (červená), řádky (modrá) a 9 čtverců (zelená), tzv. regionů, každý o velikosti 3 x 3 políčka. Tato tabulka je vyplněna množinou čísel 1 - 9, viz Obr. 1.1 vlevo. Cílem hry je doplnit do prázdných buněk tabulky zbývající čísla, aniž by porušovala tato pravidla [5]: • • • •
Každá buňka hrací plochy musí obsahovat právě jedno číslo z intervalu 1 - 9. Každý řádek musí obsahovat každé číslo z intervalu 1 - 9 právě jednou. Každý sloupec musí obsahovat každé číslo z intervalu 1 - 9 právě jednou. Každý region musí obsahovat každé číslo z intervalu 1 - 9 právě jednou.
Pouze dodržováním těchto pravidel lze dojít ke správnému řešení, viz Obr. 1.1 vpravo, proto jsou tato pravidla základem všech algoritmů pro řešení Sudoku.
1.2
Zadání
Ne každou nevyplněnou tabulku lze považovat za plnohodnotné zadání. Celkově existuje přibližně 6, 7 · 1021 možných vyřešených Sudoku [1], ale možných zadání existuje mnohem více, uvážíme-li jako možná zadání jejich různá stádia, která vedou ke stejnému řešení.
10
1
5
6 1 3 2 9 7 5 4 8
1 4 6 7 8 2 4 6 3 7 1 9 3 1 9 5 2 7 2 8 2 6 3 5 4 9
7 4 8 6 5 1 9 2 3
2 5 9 3 8 4 7 6 1
1 9 7 5 6 3 2 8 4
4 8 6 7 2 9 3 1 5
5 3 2 4 1 8 6 7 9
3 6 4 8 7 5 1 9 2
9 7 5 1 4 2 8 3 6
8 2 1 9 3 6 4 5 7
Obr. 1.1: Zadání sudoku s rozdělením na jednotlivé bloky a jeho řešení. Přestože to není pravidlem, mělo by správné zadání Sudoku dodržovat tyto standardy [2]: • Každé zadání by mělo vést pouze k jednomu řešení. Tento pravděpodobně nejdůležitější standard bývá velmi často porušován, z důvodu pomalého generování zadání. • Každé zadání by mělo být řešitelné za pomoci lidmi použitelných metod bez hádání. Tento standard je velmi těžce ověřitelný, neboť by se musely k ověření využít všechny známé techniky. Navíc lidé neustále vymýšlejí další nové techniky, tudíž zadání, které do této kategorie nespadá, s novou technikou může. Zpochybnitelné je taktéž hádání, protože ve skutečnosti se jedná o nedeterministický algoritmus. • Každé zadání by mělo být minimální. To znamená, že ze zadání již nemohu odstranit žádnou číslici, aniž by Sudoku mělo stále jedno řešení. Z těchto standardů vyplývá, že musí existovat určitý minimální počet číslic v zadání Sudoku, při kterém ještě existuje pouze jedno řešení. Tento minimální počet číslic je 17, což bylo tento rok experimentálně ověřeno týmem z University College Dublin [1]. Obtížnost ovšem není dána pouze počtem předvyplněných políček v zadání, ale na první pohled neviditelnými vazbami mezi nimi. Zpravidla se určuje na základě počtu kroků řešícího algoritmu.
11
2
ALGORITMY
Informace k této kapitole byly čerpány ze [3]. Algoritmy pro řešení Sudoku lze rozdělit do dvou velkých skupin: • Lidské algoritmy. Tyto algoritmy napodobují lidské myšlení a doplňují čísla na základě dedukcí. • Rekurzivní algoritmy. Tyto algoritmy na základě různých pravidel zkouší dosazovat čísla, dokud nenaleznou řešení. Tato práce se zabývá algoritmy, které napodobují lidské myšlení. Jejich nespornou výhodou je, že při vhodné sekvenci lze u konkrétního zadání nalézt řešení mnohem rychleji, než s využitím rekurzivních algoritmů, které musí ověřit všechny možnosti. Náročnost na výpočet jednoho čísla ovšem může být mnohonásobně vyšší. Pomocí jednoho typu algoritmu navíc většinou nelze vyřešit libovolné zadání, musí být použita kombinace několika z nich.
2.1
Kandidáti
Veškeré lidské základní algoritmy na řešení Sudoku pracují s tzv. kandidáty. Kandidát je číslo, které může být na dané políčko dosazeno, aniž by porušovalo základní pravidla, viz Obr. 2.1 vlevo. Obecně platí, že kandidát je řešením daného pole, je-li v rámci jedno řádku, sloupce, nebo regionu jedinečný. Na vyhledávání těchto osamocených kandidátů se zaměřuje jedna skupina algoritmů. Druhá skupina se zabývá jejich eliminací, tedy vyřazováním určitých kandidátů na základě určitých pravidel.
2.1.1
Realizace v prostředí Matlab
V této části je zajímávé samotné ukládání kandidátů pro jednotlivá políčka. Jako nejjednodušší řešení se jeví ukládání do buňkového pole. Tento způsob byl ovšem zavržen, neboť v jednotlivých algoritmech je nutné se všemi kandidáty provádět různé matematické operace, což s poli není možné. Další uvažovaný způsob byl uložit kandidáty pro dané políčko jako binární vektor a ten následně převést na dekadickou formu. Tuto formu bylo ale nutné u každého algoritmu vždy převést zpět, což zbytečně prodlužovalo výpočetní čas. Nakonec byl vybrán způsob využívající
12
matici s rozměry 9 x 9, což odpovídá velikosti hrací plochy, s devíti dimenzemi. Dané číslo je tedy reprezentováno jako logická jednička v dané dimenzi na odpovídající pozici, viz Obr. 2.1 vpravo. 1. dimenze
367
137
136 79
156 79
567 9
237
134 7
147
7
8 6 4 8 2 9 7 3 1 8 4 1 7 2 4 1 3 8 5 2 8 9 5 3 6 5 4 5 1
37
367
2 4 9 5
379
137 8
135 6
136 7
137 2
26
369
6
269
16
167
379
138
137 89
346 79
368
6
379
567 9
5
26
58
469
456 9
267 9
47
237
237
234 7
569
267 9
167
127 9
179
267 9
679
267 89
1 1 1 0 0 0 0 1 1
0 0 0 1 0 0 0 0 1 1
0 0 0 1 1 0 1 0 0 1 0
0 0 1 0 1 0 0 0 0 1 1
0 0 1 1 1 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 0 0
2. dimenze
3. dimenze
0 0 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 1 0 0 1
0 0 0 0 0 0 0 0 0
Obr. 2.1: Zadání Sudoku se zobrazenými kandidáty a způsob jejich uložení v matici.
2.2
Vazby a odkazy (Chains and Links)
U složitějších zadání již nestačí pouze jednoduchá redukce kandidátů, ale musí se hledat na první pohled neviditelné vazby mezi nimi. Nejdříve musí být definovány termíny odkazy a vazby. Odkazy jsou určitá políčka s kandidáty, zatímco vazby jsou pomyslné spojnice mezi jednotlivými odkazy. Odkazy se dělí na tyto dvě skupiny: • Bi-Location. Jeden typ kandidáta se vyskytuje pouze dvakrát v rámci řádky, sloupce, nebo regionu, viz Obr. 2.2 vlevo. • Bi-Value. Na daném políčku se vyskytují pouze dva kandidáti, viz Obr. 2.2 vpravo. Jelikož se vždy jedná o dvojici kandidátů, ať už pozicí nebo počtem, jde o tzv.buď a nebo vztah. Tedy jeden kandidát svým dosazením vylučuje druhého.
13
1
1
1
46
1
1
469
235
23
235
269
269
24
1
24
1 1
24
46
1 1
469
46
26
1
1
469
1 2 3 5 5 8 1 7 2 9 8 7 1 5 1 8 4 3 9 7 5 6 7 8 1 9 7 6 8 5 3 8 1 7 8 1 7 3
1
1
234 5
29
29
49
469
346
346
234
234 5
469
8 3 6 7 1 2 9 4 5
7 9 4 3 8 5 1 6 2
Obr. 2.2: Bi-Location a Bi-Value odkazy.
Linearní vazby
Síťové vazby
Obr. 2.3: Druhy vazeb mezi odkazy.
Mnohem důležitější jsou ovšem vazby, které musí jednotlivé odkazy spojovat tak, že když dojte ke zvolení kandidáta v jednom odkazu, bude to mít efekt na všechny ostatní odkazy. V zásadě lze vazby dělit na dva typy: • Lineární vazby, kde platí, že každý odkaz má vazbu na maximálně dva další odkazy, viz Obr. 2.3. • Síťové vazby, kde každý odkaz může ovlivnit více než další dva odkazy, viz Obr. 2.3. Na obrázku jsou zobrazeny buď a nebo vztahy mezi odkazy červenou a zelenou barvou. Tedy změníme-li jednoho kandidáta z obrázku Obr. 2.3, všechny ostatní se změní podle něj, viz Obr. 2.4.
14
Obr. 2.4: Vztah buď a nebo.
2.3
Lidské dosazovací algoritmy
Existuje pouze jeden způsob, jak správně doplnit číslo do Sudoku, a to najít kandidáta, který je svým způsobem jedinečný. Pro tento účel jsou využívány dva následující algoritmy.
2.3.1
Algoritmus Singles
Tento algoritmus je založen na vyhledávání políček, jež obsahují pouze jednoho kandidáta. Jelikož žádný jiný kandidát na políčku není, musí být toto číslo řešením onoho políčka, viz Obr. 2.5. 236 7
37
2
25
1 389
348
38
5
238 9
9
38
289
289
1 4 6 7 8 9 6 2 4 6 3 7 1 9 3 1 9 5 2 7 2 8 2 6 3 5 4 9
357
37
245 8
58
57
478
345
245 8
568
48
368
359
48
358
78
35
158
5
124 58
48
89
146 78
78
489
46
346 78
467 8
135
136
19
18
178
179
135 8
127
Obr. 2.5: Algoritmus Singles.
15
1
146 9
6
126 78
2.3.2
Algoritmus Hidden singles
Tento algoritmus vyhledává kandidáty, kteří jsou unikátní v rámci řádku, sloupce, nebo regionu. Tudíž i když v políčku není kandidát osamocen, tak dle základních pravidel musí být řešením daného políčka, viz Obr. 2.6. 347 89
238 9
347 8
238
378 9
245 78
245 78
267
247 8
267
123 68
146 78
124 67
467 8
246 7
1 9 5 5 6 3 1 9 1 6 4 2 8 4 7 2 7 4 3 4 6 8 3 5 2 5 9 78
359
368 9
359
357 9
379
125 8
235 89
123 9
568 9
158
589
79
127
358 9
79
367 8
138
367 89
135 89
27
356 789
28
247
156
16
169
156
12
147
347
124 7
234 79
123 79
126 8
146 78
146 7
146 78
124 67
Obr. 2.6: Algoritmus Hidden singles.
V zadání lze vidět tři příklady skrytých osamocených kandidátů. Kandidát č. 4 je unikátní pouze ve svém řádku, naproti tomu kandidáti č. 3 a 9 jsou unikátní nejen v naznačeném sloupci a regionu, ale i v dalších skupinách.
2.4
Lidské eliminační algoritmy
Jsou-li dosazovací algoritmy neúčinné, je to proto, že se v hracím poli již nevyskytují osamocení kandidáti a je třeba je určitým způsobem eliminovat. K tomu slouží celá řada algoritmů od základních, jež eliminují kandidáty podle základních pravidel, až po ty nejsložitější, jež využívají vazeb a odkazů.
2.4.1
Algoritmus Naked candidates
Tento algoritmus se snaží vyhledávat stejné kandidáty v rámci několika políček v jednom řádku, sloupci, nebo regionu. V zásadě se velmi podobá algoritmu Singles,
16
tedy na daném políčku musí být pouze kandidát, kterého hledáme a žádný jiný. V tomto případě se ovšem nejedná pouze o jednoho kandidáta, ale o dva a více. Algoritmus může být aplikován prakticky až na osm políček. Již při použití více políček než tří je realizace tohoto algoritmu poměrně náročná a v praxi se příliš často nevyskytuje. Naked pairs Tento algoritmus je nejjednodušším případem algoritmu Naked candidates. V zadání jsou hledána políčka, která obsahují pouze dva stejné kandidáty v rámci jednoho sloupce, řádku, nebo regionu, viz Obr. 2.7.
1 457 8 347
38
9 357
478
567 8
78
2 9 67
347
1 6 578
378
4 2 78
478
3 9
78
26
468
146 78
147 8
5
146 7
248 9
248
348
248
124 78
134 578
124
69
167
135 7
19
248
246
4
156
57
169
79
3 2 8 5 7
1 3 9 248
256
124
239
6
8
39
245 6
25
48
6 9 5 7 3 1 2 3 1 7 5 6 8 49
49
Obr. 2.7: Algoritmus Naked pairs.
Jsou-li nalezena taková políčka, je zřejmé, že kandidáti v nich musí být řešením těchto políček, neboť tato políčka již jiné kandidáty neobsahují. Proto je možno tyto kandidáty v rámci daného řádku, sloupce, nebo regionu z ostatních políček vyškrtnout, viz Obr. 2.7. Naked triples U třech kandidátů již nastává problém s detekcí, neboť zde neplatí, že musí být všechna 3 čísla ve všech třech buňkách, ale jsou možné tyto kombinace:
17
• Všichni kandidáti ve všech buňkách, viz Obr. 2.8 sloupec č. 1. • Všichni kandidáti ve dvou buňkách a dva z kandidátů v té poslední, viz Obr. 2.8 sloupec č. 6. • Všichni kandidáti v jedné buňce a ve zbylých dvou buňkách všichni tři kandidáti tak, aby v každé buňce byly pouze dva, viz Obr. 2.8 sloupec č. 3. • Všichni kandidáti se v rámci tří buněk vyskytují pouze dvakrát, viz Obr. 2.8 řádek č. 6.
478 9
289
347 8
238
789
245 78
245 78
267
247 8
267
3 5
167 8
126 7
678
267
1 9 5 6 3 1 9 4 1 6 4 2 8 4 7 9 2 7 4 3 4 6 8 3 5 2 5 9 78
359
368
359
357 9
379
125 8
235 8
123
568 9
158
589
79
12
358
79
368
138
368
135 8
27
356 8
28
156
16
15
12
147
347
124 7
234 79
123 79
126 8
146 78
167
146 78
126 7
Obr. 2.8: Algoritmus Naked triples.
Tento algoritmus je analogický pro více kandidátů, ale kombinací možných obsazení jednotlivých buněk je mnohonásobně více. Realizace v prostředí Matlab Přestože se podle počtu hledaných kandidátů od sebe algoritmy zdánlivě liší, mají jednu věc společnou. Na políčcích se vyskytují pouze hledaní kandidáti a žádní jiní. Tohoto předpokladu bylo při programování využito, kdy pomocí funkce combnk, která generuje všechny kombinace zadaných čísel, byli generováni všichni kandidáti kromě těch, kteří byli v danou chvíli hledáni, a byla vyhledávána políčka, která je neobsahovala. Pokud se těchto políček v jednom řádku, sloupci, nebo regionu nachází stejný počet, jako je počet hledaných kandidátů, tak se jedná o případ, jež
18
má algoritmus detekovat a je nutno z ostatních políček v detekované skupině dané kandidáty odstranit. Díky této podobnosti bylo možno implementovat tento algoritmus až pro n kandidátů do jediné funkce. Z důvodu zkrácení výpočetního času bylo ovšem vyhledávání omezeno na maximálně čtyři kandidáty.
2.4.2
Algoritmus Hidden candidates
Podobně jako v předchozím případě je tento algoritmus principiálně podobný algoritmu Hidden singles, ale jsou hledány dva a více unikátních kandidátů v rámci řádku, sloupce, nebo regionu. Políčka, která tomu odpovídají, obsahují kromě hledaných kandidátů i další. Protože jsou ovšem hledaní kandidáti v rámci skupiny unikátní, musí být řešením těchto políček, a ostatní kandidáti z těchto políček musí být eliminováni. Hidden pairs Jedná se o nejjednodušší případ algoritmu Hidden candidates. V zadání jsou hledána políčka, která v rámci řádku, sloupce, nebo regionu obsahují dva unikátní kandidáty, viz Obr. 2.9. 136
13
679
169
367 9
49
156 9
69
67
16
156
49
49
4 5 2 8 7 8 3 2 9 8 4 5 9 6 1 2 7 3 8 4 1 8 7 3 2 5 6 4 5 6 8 7 1 9 8 4 5 3 8 1 8 9 5 4 156
123 56
23
14
123 5
37
23
123 9
267
17
246 7
47
26
256 7
259
236
123 67
123
16
69
236 79 267 9 236 7
Obr. 2.9: Algoritmus Hidden pairs.
19
37
Realizace v prostředí Matlab V políčku se nevyskytují pouze kandidáti, kteří jsou hledáni, neexistuje tedy spojitost mezi jednotlivými algoritmy pro různý počet kandidátů. Implementace algoritmu se pro více než dva kandidáty, kde existuje více než jedna kombinace políček, zdála příliš složitá a vzhledem k dlouhému výpočetnímu času neefektivní.
2.4.3
Algoritmus Pointing candidates
Tento algoritmus vyhledává regiony, které obsahují určitého kandidáta pouze v rámci jednoho řádku nebo sloupce. Jelikož tohoto kandidáta v rámci regionu nelze umístit jinam než v tomto řádku nebo sloupci, musí být ze zbytku řádku nebo sloupce tento kandidát eliminován, viz Obr. 2.10.
7
56
56
9 2 1 4 8 3 9 5 6 8 5 8 4 5 3 7 6 7 8 5 7 4 3 2 7 8 7 1 9 5
123 4
134
123 4
134
129
123 469
146 9
478
346 7
467
12
134 69 136 9
146 9
36
347 8
16
269
168
268 9
123 9
268
467 8
246 78
126 9
368
346 8
468
126
145 6
127
129
127 9
123 59
125 9
129
26
145 69
12
46
236
129
125 9
124 589
135 9
145 89
23
24
Obr. 2.10: Algoritmus Pointing candidates.
2.4.4
Algoritmus Box/Line reduction
Tento algoritmus pracuje přesně naopak než algoritmus Pointing candidates. Vyskytujeli se nějaký kandidát v rámci jednoho řádku nebo sloupce pouze v jednom regionu, nemůže se už kandidát ve zbytku regionu objevit a proto může být eliminován, viz Obr. 2.11.
20
25
4 9 7 1 6 1 3 8 7 4 9 6 4 1 7 1 9 6 8 5 9 6 4 2 3 6 9 4 5 3 25
38
38
2
37
58
258
258
37
58
57
157
28
128
235 8
58
235 8
6 9 4 5 1 6 9 4 2 1 3 6 9 2 3 1 7 8 7 9 6 257
257
58
58
47
47
358
358
24
15
24
18
Obr. 2.11: Algoritmus Box/Line reduction.
2.4.5
Algoritmus X-Wing
Tento algoritmus je prvním z pokročilých algoritmů, který využívá principu vazeb a odkazů. Princip tohoto algoritmu vyplývá z odkazů Bi-Location, do jejichž skupiny patří. Vyhledává políčka, na kterých se daný kandidát v rámci řádku nebo sloupce vyskytuje přesně dvakrát. Najde-li algoritmus takové řádky nebo sloupce dva a políčka v nich nalezená leží přesně pod sebou nebo vedle sebe tak, že tato čtyři políčka tvoří čtverec nebo obdélník, jedná se o případ, který má tento algoritmus za úkol detekovat. Jelikož se jedná o lineární vazbu, může být daný kandidát pouze na jedné z úhlopříček čtyřúhelníku. V každém případě tento algoritmus vylučuje daného kandidáta ze všech řádků a sloupců, které procházejí kterýmkoliv ze všech čtyř políček, viz Obr. 2.12.
21
127 8 257 8 125 7
9 3 6 4 578
157
17
12
278
579
259
278
9 3 4 5 6 6 3 1 4 4 6 8 3 8 1 3 4 5 4 7 2 8 6 9 5 5 2 7 4 8 6 2 8 9 4 1 2 9 8 3 58
17
125
267
19
137
37
15
58
27
9
27
267
19
135
356 9
79
267
156
17
67
1 3 57
256 7
4
Obr. 2.12: Algoritmus X-Wing.
Na obrázku Obr. 2.12 lze vidět příklad pro kandidáta č. 5, který je přítomný dvakrát v řádku č. 3 a 9. Jelikož jsou tato políčka pod sebou, lze tohoto kandidáta odstranit ze zbytků sloupců, které těmi políčky procházejí, protože i když bude kandidát řešením políček pouze na jedné z úhlopříček, vždy bude již ve sloupci obsažen.
2.4.6
Algoritmus Y-Wing
Algoritmus Y-Wing je pokročilý, velmi efektivní algoritmus, který svou funkčností spadá do kategorie odkazů Bi-Value. Principiálně je velmi podobný algoritmu XWing. Algoritmus nejdříve vyhledá políčko pouze se dvěma kandidáty, tzv. počáteční bod Y. Následuje operace, kdy na herní ploše musí být nalezena 2 políčka, tzv. křídla Y, se dvěma kandidáty, z nichž jeden je společný s počátečním bodem a druhý mají křídla společný mezi sebou. Zároveň musí být splněna podmínka, že pozice obou křídel musí být v oblasti vlivu počátečního bodu Y a obě křídla nesmí být kompletně identická. Nakonec algoritmus vyhledá průsečík oblastí vlivů obou křídel a v této oblasti může být eliminován kandidát, který je oběma křídlům společný.
22
I v případě tohoto algoritmu se jedná o lineární vazbu, kde ať už bude dosazen do počátečního bodu Y libovolný z obou kandidátů, tak bude vždy na jednom z křídel dosazen kandidát, který je oběma křídlům společný. Potom se tento kandidát nemůže dle základních pravidel vyskytovat v průsečíku oblastí vlivů obou křídel, viz Obr. 2.13.
9 478
136 78 146 8 148
38
5 2 9 48
134 68
7 6 5 1 2
48
34
136 8
137 8
48
78
2 4 6 9 5 7 2 9 3 5 2 9 2 7 9 7 8 6
136 8
18
145 68
134 568
137 8
16
48
16
145
348
48
14
57
58
2 3 9 3 2 6 9 7 6
47
48
134 5
145
1 468
458
148
7
145 8
458
145 8
34
568
45
3 2 9
Obr. 2.13: Algoritmus Y-Wing.
Na obrázku Obr. 2.13 lze vidět počáteční bod Y v prvním řádku a druhém sloupci. V oblasti vlivu tohoto počátečního bodu byla nalezena 2 křídla, kde kandidáti společní s počátečním bodem byli označeni zeleně a kandidáti společní oběma křídlům, číslo 4, oranžově. Průsečík oblastí vlivů obou křídel byl na hrací ploše označen zeleně a v něm kandidát číslo 4 eliminován.
2.5
Rekurzivní algoritmy
V této práci byla naprogramována pouze část z existujících lidských algoritmů a to nestačí k vyřešení každého zadání Sudoku. Rekurzivní algoritmy jsou naproti tomu schopny vyřešit libovolné zadání, neboť postupně projdou všechny kombinace, dokud nenarazí na řešení neodporující základním podmínkám.
23
2.5.1
Algoritmus Brute force
Tento algoritmus v obecné formě systematicky prochází všechny možné kombinace čísel, dokud nenarazí na tu správnou. Jelikož je ve své základní formě algoritmus velmi neefektivní, byl modifikován pomocí dvou úprav: • Využitím generování kandidátů. Algoritmus dosazuje pouze čísla, která neporušují základní pravidla Sudoku. Tím je počet všech kombinací výrazně snížen. • Minimalizací počáteční chyby. Políčka jsou vyplňována v pořadí závislém na počtu kandidátů. Jsou-li nejdříve vyplněna políčka s nejnižším počtem kandidátů, pravděpodobnost vložení špatného čísla se tím sníží a tím se sníží i počet všech kombinací. Algoritmus se tak stal velmi efektivní, neboť funkce pro generování kandidátů byla vektorizována, efektivně naprogramována pomocí vnitřních funkcí prostředí Matlab, a jeden výpočet kandidátů trval na testovací sestavě pod 5 ms, viz kapitola 3. Realizace v prostředí Matlab U algoritmu bylo využito rekurzivního volání funkce. Na obrázku Obr. 2.14 lze vidět, že funkce nejdříve vyhledá políčka, která obsahují nejmenší počet kandidátů. Dále si zálohuje kandidáty, neboť jsou ukládáni v globální proměnné a ta není ovlivňována jednotlivými rekurzemi funkce. Do prvního z nalezených políček je vložen kandidát s nejnižší hodnotou a jsou vygenerováni noví kandidáti. Jestliže ještě existují nějací kandidáti, je funkce rekurzivně zavolána znovu a celý proces se opakuje. V případě, že již žádní kandidáti nejsou, funkce ověří, jestli již náhodou Sudoku není vyřešeno. Jestliže není, funkce zvolila do posledního políčka špatného kandidáta k dosazení a je třeba obnovit předcházející kandidáty a zkusit dosadit další číslo v pořadí na dané políčko. Po vyčerpání všech možností v daném políčku bez nalezení řešení, lze předpokládat, že chyba nastala již v předchozích rekurzích a algoritmus se proto vrátí o rekurzi zpět.
24
START
Načtení globálních proměnných
Výběr políčka s nejmenším počtem kandidátů
for BoxCandidates = Všichni kandidáti na daném políčku
Záloha čísel a vložení nového čísla dle dostupných kandidátů
Generování nových kandidátů
if Jsou ještě kandidáti?
Rekurze
if Jsou všechna
Obnova
políčka plná?
zálohy
END
Obr. 2.14: Vývojový diagram algoritmu Brute force.
25
3
HARDWARE A SOFTWARE
Celý projekt byl vyvinut, naprogramován a testován za použití následujícího hardware a software: • Notebook Compaq Presario CQ61. • Webkamera neznámý typ s maximálním rozlišením 640 x 480 px. • Prostředí Matlab ve verzi Matlab 2010a. Z toho vyplývá, že veškeré dosažené výsledky v této práci jsou přímo závislé na použitých prostředcích, a jejich změnou se mohou některé z uvedených věcí lišit. Základní funkčnost programu by ovšem měla zůstat zachována. Přestože byl program napsán s ohledem na kompatibilitu, bylo nutno použít dva toolboxy, a to Image Acquisition Toolbox (IAT) a Image Processing Toolbox. U těchto toolboxů se již vyskytují malé rozdíly mezi verzemi, hlavně u IAT. Při testování v prostředí Matlab ve verzi Matlab 2012b byly detekovány neznámé problémy s některými typy kamer. Proto by měl být tento toolbox použit ve verzi v. 3.5, jako v případě testování.
26
4
ZPRACOVÁNÍ OBRAZU
Tato kapitola vychází z [12]. Součástí této práce bylo načítání zadání Sudoku z obrazu pomocí webkamery obsluhované z Image Acquisition Toolbox. Tuto úlohu lze rozdělit 3 dílčí kroky, viz Obr. B.1: • Detekce Sudoku mřížky. Lokace Sudoku mřížky ve snímaném obrazu a detekce okrajových bodů. • Transformace obrazu. Korekce projektivního zkreslení a následná segmentace obrazu. • Detekce čísel. Rozpoznání čísla v segmentovaném obrazu na základě korelace se vzorem.
4.1
Detekce Sudoku mřížky
Detekce Sudoku mřížky vychází z prostého předpokladu, že mřížka by měla být největší spojitý objekt ve snímaném obrazu. Tento předpoklad lze naplnit pouze v případě, že se v obrazu nebude vyskytovat další velký objekt s vysokým kontrastem vůči pozadí. Po správném prahování a převodu obrazu na černobílý bylo nutné nalézt tuto největší spojitou skupinu pixelů a nakonec lokalizovat souřadnice vnějších rohů mřížky.
4.1.1
Prahování obrazu
Na prahování obrazu závisí samotná úspěšnost detekce obrazu. Pro vstupní obraz ve stupních šedi bylo nutné stanovit práh, dle kterého byl obraz převeden do černobílého. Prahování lze rozdělit na dva typy: • Globální prahování. Každý pixel obrazu používá stejnou prahovou hodnotu. • Lokální prahování. Každý pixel obrazu používá unikátní prahovou hodnotu. Globální prahování se ukázalo být nevhodné, neboť v případě oblastí se sníženým kontrastem na vstupním obrazu byl použitý práh příliš nízký nebo vysoký a část obrazu se tak znehodnotila. Proto bylo zvoleno lokální prahování, viz Obr. 4.2,
27
Detekce Sudoku mřížky
Detekce Prahování
největší
obrazu
skupiny
Detekce rohů
Transformace obrazu
Vyřazení Projektivní
Segmentace
transformace
obrazu
prázdných políček
Detekce čísel
Vzájemná
Eulerovo
korelace
číslo
Obr. 4.1: Vývojový diagram zpracování obrazu.
které počítá prahovou hodnotu pro každý pixel na základě průměrné hodnoty jeho bezprostředního okolí, osmi okolních pixelů, a je tak mnohem méně náchylné na chyby způsobené kontrastem. Realizace v prostředí Matlab Procházet v obrázku pixel po pixelu a počítat jeho lokální práh se projevilo jako časově velmi náročný problém. Tento problém se naštěstí podařilo vektorizovat. Proměnná s obrázkem byla zkopírována do matice stejných rozměrů, ovšem s devíti dimenzemi. Každá dimenze potom byla posunuta o jeden prvek každým z osmi směrů. Matice je následně sečtena v ose z a podělena devíti. Pro každý pixel tak byla efektivně spočtena průměrná hodnota jasu jeho bezprostředního okolí.
28
Obraz
Průměrná hodnota
Průměrná hodnota
Průměrná hodnota
Průměrná hodnota
Obr. 4.2: Převod na černobílý obrázek.
4.1.2
Pozice Sudoku
Po výběru pixelů, které reprezentují mřížku, bylo nutno zjistit souřadnice vnějších rohů mřížky, pro další zpracování obrazu. Rohy mřížky lze definovat jako pixely, jenž jsou svou pozicí nejblíže pozicím rohů obrazu, viz Obr. 4.3. Souřadnice tedy byly vypočteny pomocí Pythagorovy věty, kdy byly hledány souřadnice, jejichž vzdálenost byla vůči některému z rohů obrazu minimální.
4.2
Transformace obrazu
Ve velice málo případech se podaří sejmout obraz se zadáním Sudoku takovým způsobem, aby zadání mělo dokonale čtvercový tvar. Obvykle je zkresleno, protože se snímací kamera nenachází přesně nad zadaním nebo je nakloněna pod určitým úhlem. Proto bylo nutné obraz transformovat na správný tvar, vhodný k následné segmentaci hrací plochy na jednotlivá políčka.
4.2.1
Projektivní transformace
Projektivní transformace se používá v případech, zdá-li se obraz nakloněný. To může být zapříčiněno relativním posunem středu kamery, od středu obrazu. Pro transfor-
29
Obraz
in
m in
m
Sudoku mřížka
m
in
in
m
Obr. 4.3: Detekce rohů mřížky Sudoku.
maci jsou nutné minimálně 4 souřadnice bodů [7], přičemž je nutné znát jak souřadnice z původního obrazu, viz Obr. 4.4 vlevo, tak z obrazu po transformaci, viz Obr. 4.4 vpravo. Podle rozdílu souřadnic mezi těmito body je následně obraz transformován. Transformaci bylo nutné provést na šedotónovém obrázku a poté jej znovu převést na černobílý, protože při transformaci přímo s černobílým obrazem dochází k výraznému zkreslení obrazových dat.
4.2.2
Segmentace a příprava obrazu
Segmentace vychází z předpokladu, že Sudoku mřížka má pravidelný čtvercový tvar. Jsou-li známy rohové souřadnice, potom každé políčko bude mít délku odpovídající 1 rozdílu mezi rohovými souřadnicemi. 9 Jelikož je nutné segmentovaný obraz dále připravit pro detekci čísel, a tyto přípravy jsou výpočetně náročně, byla zavedena podmínka, která určuje, zda-li se ve vybraném výřezu vyskytuje nějaký znak k detekci. Z každého výřezu se porovná průměrná jasová hodnota centrální části výřezu a celého výřezu. Jestliže je nižší, lze předpokládat, že se v políčku nachází znak k detekci. Výřez byl poté převeden na černobílý obraz a morfologicky opraven, což je důležité pro rozpoznání čísla.
30
Obraz
Obraz
Sudoku mřížka
Sudoku mřížka
Obr. 4.4: Projektivní transformace.
Morfologická operace uzavření spočívá ve sbližování tvarů dvou objektů [8]. V tomto případě byla využita k opravě malých mezer pomocí malého kruhového objektu v obrazu, které vznikly v důsledku převodu šedotónového obrazu na černobílý, viz Obr. 4.5.
Obr. 4.5: Morfologická oprava.
4.3
Detekce čísel
Detekce čísel je založena na tzv. 2D vzájemné korelaci, která porovnává 2 obrazy mezi sebou. Prostředí Matlab již disponuje funkcí xcorr2 pro tuto korelaci. Zjednodušeně se jedná o konvoluci dvou obrazů, z nichž jeden časově překlopen, viz rovnice 4.1.
31
(𝑀 𝑎−1) (𝑁 𝑎−1)
𝐶(𝑖, 𝑗) =
∑︁
∑︁
𝑚=0
𝑛=0
𝐴(𝑚, 𝑛) · 𝑐𝑜𝑛𝑗(𝐵(𝑚 + 𝑖, 𝑛 + 𝑗))
(4.1)
Výhoda této korelace spočívá v tom, že obrazy nemusí mít vůči sobě stejnou polohu, neboť funkce vyzkouší všechny vzájemné polohy mezi obrazy a najde maximální možnou shodu [9]. Z náhodných zadání byly extrahovány vzory čísel, od každého čísla 5 vzorů, viz Obr. 4.6, se kterými byl každý výřez korelován pro identifikaci čísla.
4.3.1
Eulerovo číslo
Některá čísla, např. 3, 6 a 8, mezi sebou vykazují velkou podobnost a jejich správné rozlišení se tak stává obtížnější. Proto bylo nutné do detekce zavést další rozlišovací znaky. Eulerovo číslo pro černobílý obraz je definováno jako rozdíl mezi počtem objektů v obrazu, což je pro každé číslo rovno 1, neboť každé tiskací číslo je jeden celistvý symbol, a počtem uzavřených mezer v objektu [10]. Pro číslici 8 tedy bude Eulerovo číslo rovno -1, neboť osmička obsahuje 2 uzavřené prostory. Na základě tohoto rozhodovacího pravidla již bylo možné rozlišit nejpodobnější číslice.
Obr. 4.6: Vzory čísel.
32
4.4
Ideální podmínky
Detekční algoritmus bude pracovat na 100 % pouze za jistých idealizovaných podmínek. Jakákoliv odchylka se projeví sníženou úspěšností detekce. Tyto podmínky byly zjištěny experimentálně a jsou následující: • Dobrý kontrastní poměr. Velký rozdíl mezi jasovou hodnotou detekovaných částí a pozadí. • Vyplněná snímací plocha. Zadání Sudoku k detekci by mělo vyplňovat kolem 80 % ze snímané plochy. • Jednolité pozadí. Pozadí snímaného zadání by mělo být pokud možno podobné v celé části snímané plochy, bez rušivých elementů. • Rovná snímaná plocha. Zadání by mělo být rozloženo na rovné ploše, např. stůl, neboť pokřivení v ose z se projeví zkreslením obrazu při transformaci. • Dobré světelné podmínky. Snímaná plocha by měla být rovnoměrně a bez stínů osvětlena pod takovým úhlem, aby nevznikaly nežádoucí odlesky. Zároveň je nutno dbát i na použitý hardware, viz kapitola 3, kdy program byl nejvíce optimalizován pro rozlišení 640 x 480 px a bude takto dosahovat nejlepších výsledků, i když si poradí i s jiným rozlišením. Příklad optimálních podmínek lze vidět níže, viz Obr. 4.7
33
Obr. 4.7: Ideální podmínky.
34
5
GRAFICKÉ PROSTŘEDÍ
Grafické prostředí se skládá ze 3 hlavních obrazovek, viz Obr. 5.1, mezi kterými lze pomocí menu libovolně přecházet. Celý program používá dvoupanelové rozdělení, ve kterých se podle vybrané nabídky vykreslují příslušné grafické prvky.
Hrací plocha
Nastavení zdroje signálu
Načítání z obrazu
Obr. 5.1: Schéma grafického prostředí.
5.1
Hrací plocha
V této nabídce se odehrává hlavní část hry. V levém panelu se nachází políčka hrací plochy, kde šedá políčka označují zadání, a do bílých lze vepisovat čísla. Každé políčko dokáže kontrolovat zadaný znak a v případě, že jím není číslo 1 - 9, je znak vyřazen. Také je zavedena kontrola základních pravidel, která v případě jejich porušení označí nevyhovující políčka. V pravém panelu jsou potom ovládací prvky hry pro kontrolu použitých algoritmů a textový záznam hry, viz Obr. 5.2. Z algoritmů pro řešení Sudoku jsou na výběr buď rekurzivní nebo lidské algoritmy, které navíc mohou být spouštěny krok po kroku. Dále si lze nechat napovědět číslo k doplnění. Toto číslo je vygenerováno na základě lidských algoritmů a zobrazeno na krátký časový okamžik.
35
Obr. 5.2: Hrací plocha.
5.2
Nastavení zdroje videosignálu
Nabídka slouží pro výběr zdroje signálu a nastavení některých jeho parametrů. V levé části je zobrazen živý přenos z vybraného zdroje videosignálu. V pravém panelu lze zvolit zdroj signálu a jeho rozlišení, dále je možno nastavit jas a kontrast, viz Obr. 5.3. Seznam zdrojů videosignálu je aktualizován vždy při vyvolání této nabídky.
Obr. 5.3: Nastavení zdroje videosignálu.
36
5.3
Načítání z obrazu
Tato obrazovka slouží pro načítání zadání Sudoku ze zdroje videosignálu. V pravém panelu je zobrazen náhled z video vstupu, který zároveň slouží i jako ovládací prvek. Je-li ve snímaném poli zadání Sudoku, detekce se spustí kliknutím levého tlačítka myši na obraz. Detekované zadání je následně ohraničeno modrým mnohoúhelníkem a v této oblasti proběhne detekce čísel. V případě, že byla oblast vybrána špatně, lze ji pomocí tahem myši za rohy polygonu upravit. Sejmutí dalšího obrazu se provede opětovným kliknutím levého tlačítka myši na obraz. Vše je doplněno informačním popiskem, viz Obr. 5.4. V levém panelu se nachází políčka hrací plochy, do kterých se vykreslují detekovaná čísla. Tlačítko mezi panely potom slouží pro návrat na obrazovku herní plochy.
Obr. 5.4: Načítání z obrazu.
5.4
Menu
Menu slouží k přepínání mezi jednotlivými nabídkami grafického prostředí a v základu obsahuje dvě volby: • Hra. Obsahuje volby pro otevření nebo uložení hry, či zadání, dále pak možnosti pro přechod na obrazovku Načítání z obrazu a ukončení programu.
37
• Možnosti. Tato nabídka obsahuje pouze odkaz na obrazovku Nastavení zdroje videosignálu. Rozdíl mezi hrou a zadáním spočívá pouze v uložených číslech, kdy hra může obsahovat kromě čísel zadání i další uživatelem doplněná čísla. Program je při jejich ukládání a načítání rozlišuje dle rozdílného základního umístění souboru. Zadání jsou umístěna ve složce Tasks a rozehrané hry ve složce Games.
38
6
DOSAŽENÉ VÝSLEDKY
Program byl testován na mnoha zadáních, pro ukázku bylo zvoleno 6 zadání ([4] [11] [13]), na kterých lze dobře pozorovat vlastnosti jednotlivých algoritmů. Přes rozdílný postup, mají obě skupiny algoritmů podobný základ. Obě skupiny dosazují čísla do zadání na základě kandidátů, tudíž není třeba ověřovat, zda dosazená čísla neporušují základní podmínky. U rekurzivních algoritmů je výhodná jejich jednoduchost, kdy se využívá obrovského výkonu procesoru, za cenu většího množství kombinací. Lidské algoritmy naproti tomu jen jednoduše nezkouší dosazovat různá čísla náhodně, ale deterministicky, což je výpočetně mnohem náročnější. Z uvedeného vyplývá, že rekurzivní algoritmus by měl být vždy efektivnější. Přesné výsledné časy budou vždy závislé na použitých prostředcích, viz kapitola 3, ale relativní rychlostní rozdíl mezi algoritmy by měl být stále stejný. Zadání Task_001 a Task_002 potvrzují výše uvedený předpoklad o efektivitě rekurzivních algoritmů. Implementované lidské algoritmy na rozdíl od rekurzivních nedokážou některá velmi obtížná zadání vyřešit, jako například zadání Task_004, které by mělo být jedním z nejsložitějších vůbec. U tohoto zadání lidské algoritmy nedokázaly doplnit ani jednu číslici a jeho vyřešení by pravděpodobně vyžadovalo implementaci mnohem pokročilejších technik. I přes uvedené nevýhody lidských algoritmů existují případy, kdy je jejich použití výhodnější. Veškeré eliminace a dosazování kandidátů u těchto algoritmů probíhá v rámci celé herní plochy, což částečně kompenzuje jejich výpočetní náročnost. U obtížných zadání, jež na začátku obsahují velké množství kandidátů na každém políčku, jako zadání Task_003, mohou být rekurzivní algoritmy pomalejší, neboť musí projít více možností.
39
7
ZÁVĚR
Cílem této práce bylo seznámit se s principem hry Sudoku a implementovat vybrané algoritmy pro její řešení v prostředí Matlab. K řešení byly zvoleny algoritmy, které napodobují lidské myšlení. Jejich hlavní nevýhodou je fakt, že k vyřešení libovolného zadání je potřeba kombinace několika těchto algoritmů. Pro srovnání byl také naprogramován rekurzivní algoritmus, jež předchozí nevýhodu eliminuje, ale efektivnější je pouze pro jednoduchá až středně těžká zadání. Lidské algoritmy jsou efektivnější pro složitější zadání, která jsou ještě schopna vyřešit. Jejich pořadí je řízeno na základě výpočetní náročnosti každého z nich, od nejjednodušších po ty nejsložitější. Další části programu bylo načítání zadání Sudoku pomocí webkamery. Pro její obsluhu byl využit Image Acquisition Toolbox z prostředí Matlab. Samotná detekce byla rozdělena do dvou částí a to na detekci Sudoku mřížky a rozpoznání čísel v jednotlivých políčcích. Detekce mřížky vychází z předpokladu, že mřížka by měla být největší objekt ve snímaném obrazu, což platí pro většinu případů, ale je umožněno i manuální zaměření. Rozpoznání čísel je založeno na vzájemné korelaci se vzory čísel, kdy hledá nejlepší shodu. U podobných znaků je rozlišení dosaženo na základě Eulerova čísla binárního obrazu. Při dodržení ideálních podmínek byla detekce ve většině případů úspěšná nad 90%. K otestování účinnosti algoritmů na různých zadáních bylo navrženo grafické prostředí s ohledem na maximální jednoduchost. Prostředí umožňuje načítání a ukládání zadání a rozehraných her. Dále disponuje kontrolou vložených čísel proti porušení základních podmínek a nápovědou čísel k dosazení pomocí lidských algoritmů. Z dostupných algoritmů lze jednoduše zvolit typ použitý k vyřešení zadání. Důležité výstupy, jako čas potřebný k vyřešení Sudoku nebo seznam použitých lidských algoritmů, prostředí taktéž vypisuje. Kromě samotného načítání pomocí webkamery, program umožňuje i základní nastavení některých parametrů zdroje videosignálu.
40
LITERATURA [1] McGuire, G. There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem [online]. 2012, poslední aktualizace 2012-01-01 [cit.2012-1129]. Dostupné z URL:
. [2] STUART, A. Sudoku Creation and Grading [online]. 2007, poslední aktualizace 2012-01 [cit.2012-11-29]. Dostupné z URL: . [3] STUART, A. Strategy Families. SudokuWiki [online]. 2008, poslední aktualizace 2012-10-25 [cit.2012-11-27]. Dostupné z URL: . [4] STUART, A. Sudoku Solver. SudokuWiki [online]. 2005, poslední aktualizace 2012-10-22 [cit.2012-12-06]. Dostupné z URL: . [5] CROOK, J.F. A Pencil-and-Paper Algorithm for Solving Sudoku Puzzles. Notice of the AMS, 2009, vol. 56, no. 4, s. 460-468. [6] SMITH, D. So you thought Sudoku came from the Land of the Rising Sun ... The Observer [online]. 2005, poslední aktualizace 2005-05-15 [cit.2012-1207]. Dostupné z URL: . [7] The MathWorks, Inc. Infer spatial transformation from control point pairs [online]. 1994, poslední aktualizace 2013 [cit.2013-05-22]. Dostupné z URL: . [8] The MathWorks, Inc. Morphologically close image [online]. 1994, poslední aktualizace 2013 [cit.2013-05-22]. Dostupné z URL: . [9] The MathWorks, Inc. 2–D cross-correlation [online]. 1994, poslední aktualizace 2013 [cit.2013-05-22]. Dostupné z URL: . [10] The MathWorks, Inc. Euler number of binary image [online]. 1994, poslední aktualizace 2013 [cit.2013-05-22]. Dostupné z URL: . [11] COLLINS, N. World’s hardest sudoku: can you crack it? [online]. 2004, poslední aktualizace 2012-06-28 [cit.2013-05-24]. Dostupné z URL:
41
. [12] CHRIS IPHONE SUDOKU GRAB [online]. 2009, poslední aktualizace 200907-19 [cit.2013-05-24]. Dostupné z URL: . [13] LONGO, F. Mensa - Absolutně kruté sudoku - obtížnost 1, 2, 3, 4. Praha: BB/art, 2009. ISBN 859-40-675-2808-6.
42
SEZNAM PŘÍLOH A Elektronická část bakalářské práce A.1 Funkce naprogramované v prostředí A.1.1 Algoritmy . . . . . . . . . . A.1.2 Grafické prostředí . . . . . A.1.3 Zpracování obrazu . . . . . A.1.4 Ostatní pomocné funkce . . A.2 Elektronická verze bakalářské práce B Návod ke grafickému prostředí
Matlab . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
44 44 44 44 44 44 45 46
43
A
ELEKTRONICKÁ ČÁST BAKALÁŘSKÉ PRÁCE
A.1 A.1.1 • • • • • • • • •
Zpracování obrazu
Creating_video_input.m Image_transformation.m Number_recognition.m Sudoku_focusing.m
A.1.4 • • • • • • •
Grafické prostředí
Camera_opening.m Camera_settings.m Game_board.m Initial_distribution.m Sudoku.m
A.1.3 • • • •
Algoritmy
Box_line_reduction_algorithm.m Brute_force_algorithm.m Hidden_pairs_algorithm.m Hidden_singles_algorithm.m Naked_candidates_algorithm.m Pointing_candidates_algorithm.m Singles_algorithm.m X_Wing_algorithm.m Y_Wing_algorithm.m
A.1.2 • • • • •
Funkce naprogramované v prostředí Matlab
Ostatní pomocné funkce
Basic_condition.m Control_algorithms.m Erase_game_board.m Generating_candidates.m Help.m Insert_number.m Move_object.m
44
• Opening.m • Saving.m
A.2
Elektronická verze bakalářské práce
• Martin_Buchta_BP.pdf
45
B
NÁVOD KE GRAFICKÉMU PROSTŘEDÍ
Obr. B.1: Návod ke grafickému prostředí.
46
