UNIVERZITA PALACKÉHO V OLOMOUCI
PŘÍRODOVĚDECKÁ FAKULTA KATEDRA MATEMATICKÉ ANALÝZY A APLIKACÍ MATEMATIKY
DIPLOMOVÁ PRÁCE
Matematika Sudoku
Vedoucí diplomové práce:
Vypracovala:
RNDr. Tomáš Fürst, Ph.D.
Bc. Lucie Pešková
Rok odevzdání: 2011
AME, II. ročník
Prohlášení Prohlašuji, že jsem diplomovou práci zpracovala samostatně pod vedením pana Tomáše Fürsta a všechny použité zdroje jsem uvedla.
V Olomouci dne 30. března 2011
-2-
Poděkování Ráda bych na tomto místě poděkovala svému vedoucímu diplomové práce panu Tomáši Fürstovi za odbornou pomoc, připomínky a hlavně čas, který mi při konzultacích věnoval. Dále bych chtěla poděkovat mé rodině, která mě při studiu vždy podporovala. -3-
Obsah: Úvod 1
6 Sudoku
7
1.1
Úvod k Sudoku
7
1.2
Historie Sudoku
7
1.3
Magické čtverce
8
1.4
Latinské čtverce
9
1.5
Princip Sudoku
12
1.6
Terminologie
13
1.7
Popularita Sudoku
16
1.8
Varianty Sudoku
18
1.8.1 Sudoku s nápovědou (neboli Number Place Sudoku)
18
1.8.2 Klasické Sudoku (neboli Classic Sudoku)
19
1.8.3 X Sudoku (neboli Diagonal Sudoku)
19
1.8.4 Sudá/Lichá Sudoku (neboli Odd/Even Sudoku)
19
1.8.5 Sudoku s netypickými oblastmi (neboli Extra-Regions Sudoku)
20
1.8.6 Menší/Větší Sudoku (neboli Sudoku < >)
20
1.8.7 Šipkové Sudoku (neboli Arrow Sudoku)
20
1.8.8 Početní Sudoku (neboli Calcudoku)
21
1.8.9 Kruhové Sudoku (neboli Circle Sudoku)
21
1.8.10 Samurajské Sudoku (neboli Samurai Sudoku)
21
Matematika Sudoku
22
1.9.1 Všechny možnosti Sudoku
22
1.9.2 Počet vyplněných polí v Sudoku
25
Metody pro řešení Sudoku
26
1.10.1 Metody určující přímo čísla
27
1.9
1.10
1.10.1.1 Jediné ve skupině
27
1.10.1.2 Jediná možnost
28
1.10.2 Metody omezující počet kandidátů
29
1.10.2.1 Průsečíky skupin
29
1.10.2.2 Holé množiny
31
1.10.2.3 Zobecněné dvojice
33
-4-
2
1.10.2.4 XY – křížení
38
1.10.2.5 Vedoucí prvek
39
1.10.2.6 Prázdný čtverec
41
MATLAB
43
2.1
Magické čtverce v MATLABu
43
2.2
Latinské čtverce v MATLABu
48
2.2.1
48
Vytvoření latinského čtverce pomocí magického čtverce
2.2.2 Vytvoření latinského čtverce pomocí rekurzivního algoritmu
49
2.3
Algoritmy řešící Sudoku
53
2.4
Algoritmy vytvářející zadání Sudoku
57
Závěr
62
Zdroje
63
-5-
Úvod Cílem mé diplomové práce je seznámit čtenáře s dnes velmi populární hrou Sudoku. A to hned ze dvou pohledů. První pohled a také první kapitola se bude zabývat hrou samotnou, kdy se kouknu na její historii, s tím souvisejí magické a latinské čtverce. Dále vysvětlím princip této hry a ukážu nějaké méně známé varianty Sudoku. Velkou část této kapitoly budu věnovat souvislosti matematiky a Sudoku a to ze dvou pohledů. První pohled se bude zabývat tím, kolik je všech možností Sudoku a druhý pohled, kolik musí být předvylněno číslic v zadání, aby bylo Sudoku řešitelné. A v závěru této kapitoly se pokusím vysvětlit různé metody pro řešení, které ukážu názorně na příkladech, aby bylo čtenáři jasné, jak Sudoku luštit a sám zvládl vyluštit jakékoliv zadání. Druhý pohled a zároveň druhá kapitola se podívá na Sudoku z hlediska programátorského. Také krátce seznámím čtenáře s matematickým programem MATLAB, ve kterém budu všechno vytvářet. Prvně se opět podívám na magické a latinské čtverce a jak je lze vytvořit v MATLABu. Dále se pokusím vytvořit algoritmus, který bude jakékoliv Sudoku řešit a v případě, že bude více správných řešení, tak aby to poznal a vypsal je. Pak se také pokusím vytvořit algoritmus, který bude Sudoku zadávat, aby si čtenář mohl kdykoliv nějaké zadání vygenerovat a poté si jej vyřešit a zkontrolovat.
-6-
1
Sudoku
1.1
Úvod k Sudoku Sudoku je bezesporu jedna z nejoblíbenějších logických her, kterou hrají denně
statisíce lidí po celém světě. Jde totiž o jedinečný hlavolam, který vyplňují lidé všech věkových kategorií bez ohledu na vzdělání a společenské postavení. Krása Sudoku tkví v jeho „jednoduchosti“ a téměř nevyčerpatelném množství herních kombinací. Sudoku zcela potvrzuje starou a dobře známou poučku o tom, že v jednoduchosti je krása. K luštění totiž zcela postačí papír a tužka. Rébus Sudoku dnes najdeme dokonce i v některých světových denících. Píší se o něm knihy a spousta lidí si nedovede představit, že by tuto hru nenašla ve svém mobilním telefonu. Novozélanďan Wayne Gould řekl: „Nejsem si jistý, proč je Sudoku tak návyková. Akorát vím, že to tak je!“ [18]. Číselné rébusy založené na doplňování čísel zná lidstvo už odpradávna. Nejprve to byly magické čtverce, které vysvětlím později, jejichž původ sahá přinejmenším do roku 2000 před naším letopočtem. V 18. Století to byly populární rébusy švýcarského matematika a astronoma Leonharda Eulera, o kterých se také zmíním později [9].
1.2
Historie Sudoku Sudoku je logická hra, která vznikla v Americe. Sudoku v podobě, jak jej známe
dnes, vytvořil v roce 1979 Howard Garns a publikoval jej pod názvem „Number Place“ v časopise Dell Pencil Puzzle & Games [9] jako jednu z mnoha logických úloh určenou pro zábavu. A právě z tohoto časopisu ji o sedm let později převzali a vydali japonští vydavatelé magazínu Nikoli, kde Sudoku vycházelo pod názvem „Súdži wa dokušin ni kagiru“, což velmi volně přeloženo do češtiny znamená „vlož každé číslo na určené místo“. A právě z tohoto názvu vznikl dnešní název Sudoku. Kromě dnešního názvu Sudoku se také objevily názvy jako „Su Doku“, nebo „Nanpure“ [10].
-7-
Ale až v roce 2005 se Sudoku stalo mezinárodním hitem a zasloužil se o to Novozélanďan Wayne Gould, který vymyslel speciální počítačový program, který dokázal vygenerovat obrovské množství mřížek s předvyplněnými některými číslicemi. Tento program bezplatně poskytnul londýnskému listu The Times, který začal pravidelně tento rébus vydávat jako přílohu ve svých novinách. Ostatní země nechtěly zůstat pozadu, a proto dnes Sudoku můžete najít v mnoha novinách a časopisech [18].
1.3
Magické čtverce V úvodu jsem se zmínila o magických čtvercích, jejichž původ sahá přinejmenším
do roku 2000 před naším letopočtem. Podle čínské legendy zemi tehdy zachvátila potopa. Přívaly vody neustávaly, ačkoli lidé bez přestání konali oběti. Pak si jedno dítě všimlo, že se z řeky Lo vynořila želva, na jejímž hřbetě byly tečky odpovídající číslicím 1 až 9. Byly uspořádány do tří řad a tří sloupců tak, že součtem čísel vodorovně, svisle i šikmo bylo vždy číslo 15. Tomuto číslu se někdy říká magická konstanta. Lidé pochopili, že musí vykonat patnáct obětí, jak jim ukázaly číslice. Když tak učinili, vody začaly ustupovat. První magický čtverec byl podle místa svého původu nazván Lo Šu [9]. Magickým čtvercem se rozumí čtverec, který má n řádků, n sloupců a n2 políček, do kterých jsou vepsána čísla 1, 2, 3, …, n2 tak, aby součet čísel v každém řádku, sloupci a na obou úhlopříčkách byl stejný. Což si můžete ověřit na následujícím příkladu:
7
12
1
14
2
13
8
11
16
3
10
5
9
6
15
4
Magickým číslem se označuje
konstantní číslo, které dostaneme součtem
jednotlivých řádků, sloupců a úhlopříček. Toto číslo se dá jednoduše vypočítat podle následujícího vzorce: -8-
M
n(n 2 1) 2
pro n 1.
[13]
Nejstarším a nejznámějším dokladem o znalosti magických čtverců ve střední Evropě je mědirytina německého malíře Albrechta Dürera s názvem Melancholie, která se datuje do roku 1514. Jak si můžete všimnout tento letopočet lze nalézt v posledním řádku uprostřed. Další zajímavostí je fakt, že magické číslo 34 nedostaneme pouze po součtu řádků, sloupců a úhlopříček, ale dokonce i po součtu čísel ve čtvercích 2 x 2 a čísel v rozích čtverce.
Dá se říci, že Sudoku je méně náročnou variantou těchto magických čtverců [12].
1.4
Latinské čtverce V roce 1783 vymyslel geniální švýcarský matematik, fyzik a astronom
Leonhard Euler nový typ magických čtverců, tzv. latinské čtverce. Jejich název byl odvozen od písmen latinské abecedy, které byly použity místo čísel. Tyto čtverce se
-9-
podobali dnešnímu Sudoku tím, že každé písmeno se mohlo objevit pouze jednou v každém řádku i sloupci. Dále to budu vysvětlovat na číslech. Latinským čtvercem se rozumí čtverec, který má n řádků a n sloupců, do kterých jsou vepsána čísla 1, 2, 3, …, n tak, aby v každém řádku a sloupci bylo právě každé číslo od 1, …, n [15]. Tak jak je vidět na následujícím obrázku.
1
2
3
4
2
3
4
1
3
4
1
2
4
1
2
3
Dále Leonhard Euler objevil překvapivou souvislost magických a latinských čtverců. Odvodil, že když se sestrojí čtverec lichého řádu vhodným způsobem, dostaneme z něj magický a po úpravě i latinský čtverec. Za vhodný způsob uvažujeme tento postup: vepíšeme číslo 1 doprostřed prvního řádku. Číslo 2 zapíšeme o jeden řádek výše a o jeden sloupec doprava. Nad prvním řádkem je poslední řádek a vpravo od posledního sloupce je první sloupec. Může se stát, že máme napsat číslo na již obsazené pole, v tomto případě napíšeme dané číslo pod číslo předcházející. Takto postupujeme tak dlouho, dokud čtverec nemáme celý obsazený [14]. Například magický čtverec 5. Řádu vypadá následovně:
17
24
1
8
15
23
5
7
14
16
4
6
13
20
22
10
12
19
21
3
11
18
25
2
9
Teď z tohoto magického čtverce uděláme latinský čtverec. To znamená, že v našem případě budeme vpisovat pouze čísla 1, 2, 3, 4 a 5 ve stejném pořadí jako čísla předtím. Pak latinský čtverec vypadá následovně.
- 10 -
2
4
1
3
5
3
5
2
4
1
4
1
3
5
2
5
2
4
1
3
1
3
5
2
4
Sestavit magický čtverce se sudým počtem polí je o něco těžší než u čtverce s lichým počtem polí. Existuje mnoho metod, jak se dají sestrojit. Ukážu to na čtverci 4 x 4. Začneme tak, že vepíšeme číslo 1 do horního levého rohu. Číslo 2 napravo od čísla 1. Pak následuje trojka a čtverka. Tím je horní řada vyplněná. Do druhé řady vyplňuji analogicky čísla 5 až 8, do třetí řady čísla 9 až 12 a v poslední řadě 13 až 16. Čtverec vypadá následovně 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Nyní musíme, vyjmou prostřední dvě čísla ve vnějších řádcích a sloupcích. To znamená v horní řadě čísla 2 a 3, ve spodní řadě čísla 14 a 15, v levém sloupci čísla 5 a 9 a nakonec v levém sloupci čísla 8 a 12. Tyto dvojice čísel mezi sebou proházíme. Vždycky v dané dvojici nejprve čísla mezi sebou prohodíme a prohodíme je z dvojicí naproti. Tzn. Dvojici 2 a 3 mezi sebou prohodíme na dvojici 3 a 2 a dosadíme do spodní řady místo čísel 14 a 15. To samé naopak. Do horní řady dosadíme 15 a 14. Analogicky bychom to provedli pro sloupce. A dostali bychom takový magický čtverec. 1
15
14
4
12
6
7
9
8
10
11
5
13
3
2
16
- 11 -
Leonhard Euler se také zabýval otázkou, zda může šachovnicový kůň postupně projít všechna pole na šachovnici tak, aby na každé pole vstoupil právě jednou. Na typické šachovnici 8 x 8 polí existuje obrovské množství řešení. Ale Leonhard Euler objevil jedno speciální řešení, který vypadá následovně.
1
48
31
50
33
16
63
18
30
51
46
3
62
19
14
35
47
2
49
32
15
34
17
64
52
29
4
45
20
61
36
13
5
44
25
56
9
40
21
60
28
53
8
41
24
57
12
37
43
6
55
26
39
10
59
22
54
27
42
7
58
23
38
11
Tento čtverec popisuje nejen cestu šachového koně, ale dokonce se jedná o polomagický čtverec, protože součet řádků i sloupců je roven číslu 260, ale neplatí to pro úhlopříčky [14]. Až do roku 2003 se matematici snažili najít dokonalý magický čtverec založený na jezdcových tazích, ale bylo dokázané, že takovýto čtverec nemůže existovat. Pokud by ale bylo možné šachovnici zvětšit na 12 x 12 a větší počet polí, který by byl navíc dělitelný 4 tzn. 12 x 12, 16 x 16, 20 x 20 atd. je možné dokonalý magický čtverec najít [18].
1.5
Princip Sudoku Nyní vysvětlím pravidla klasického Sudoku. Na začátku máme hrací plochu, která
je rozdělena na 9 x 9 čtverečků. Zároveň čtvercový hrací plán je rozdělen na 9 menších čtverců (3 x 3). Každé pole má tedy 9 čtverečků (3 x 3). V některých čtverečcích jsou předvyplněna čísla z intervalu <1 – 9> (o jejich zadávání se zmíním později). Úkolem hráče je doplnit tabulku tak, aby v každém sloupci, řádku i malém čtverci (3 x 3) byla - 12 -
všechna čísla od 1 do 9 (libovolně poskládána, žádné se nesmí opakovat). Na následujícím obrázku můžete vidět příklad, jak může být Sudoku zadaná.
1
9
8
2
6 3
1 2
4 1 3
9 7 5
1.6
3
7
2
1
5 8
2
9 6
8 1
8
6
9
Terminologie Zde vysvětlím některé důležité pojmy, které dále budu používat a které nemusí být
vždy jasné.
Pole Polem myslím každé z 81 míst čtvercové sítě, kam ve hře Sudoku zapisujeme čísla.
Souřadnice Jednotlivá pole budu označovat dvojicí čísel v závorkách (řádek, sloupec), počítáno shora dolů a zleva doprava.
- 13 -
Řádek Odpovídá intuitivně chápanému pojmu řádku.
Sloupec Odpovídá intuitivně chápanému pojmu sloupec.
Blok Blokem myslím skupinu 3 x 3 polí v silně orámovaném čtverci. Na hracím poli je celkem 9 takových bloků a budeme je označovat po řádcích čísly 1-9 – viz obrázek.
Skupina Skupinou rozumím kterýkoliv z pojmů řádek, sloupec nebo blok.
Kandidát Pokud je více možností, jaké číslo lze na pole umístit, mluvím o kandidátech. Dále budu kandidáty zobrazovat tak, jak je na obrázku (malými modrými čísly v horní části pole).
- 14 -
479
1479
14579
489
19
1489
12457
6
123458 9
469
8
2
7
169
3
145
15
1459
4679
3
1479
2
169
5
147
178
1489
2478
47
478
4568
567
4678
3
9
124568
1
5
6
3489
379
4789
247
278
248
4789
479
34789
1
35679
2
4567
578
4568
469
1469
149
3569
123569
169
8
1235
7
5
1679
1789
369
4
1679
126
123
1236
3
2
17
56
8
167
9
4
156
Vázaná dvojice Při řešení úloh budu v celé řadě metod používat pojem „vázaná dvojice“. Tím myslím situace, kdy ve skupině (řádku, sloupci nebo bloku) se vyskytnou právě dvě pole, obsahující nějaké konkrétní číslo jako kandidáta. Jejich význam tkví v tom, že vždy musí platit buď jeden, nebo druhý prvek z dvojice. Ukážu tuto situaci na konkrétním příkladě na následujícím obrázku (vybrala jsem jen nějaké vázané dvojice, protože jich existuje celá řada). Např. číslo 8 se v konečném řešení objeví buď na pozici (1,4) nebo na pozici (1,6), nikde jinde se nemůže ve druhém bloku objevit. To samé platí pro další dvě označené vázané dvojice. Tzn. číslo 6 se v 7. řádku objeví na pozici (6,7) nebo (8,7). A poslední označená dvojice čísla 7 označuje, že se číslo 7 objeví v posledním řádku na pozici (9,3) nebo na pozici (9,6).
- 15 -
1.7
Popularita Sudoku Velmi populárním se Sudoku stalo na konci roku 2004 ve Velké Británii a postupně
se rozšiřuje do celé Evropy. Rychlost, jakou se Sudoku šíří světem je způsobeno hlavně internetem, protože dnes existuje okolo 30 miliónů internetových stránek, které se o Sudoku alespoň zmiňují. Ale podstatnou úlohu sehrála i média, která tento rébus začala ve velkém tisknout do mnoha novin a časopisů. Sudoku bývá často označováno jako „hra roku 2005“ či „nejpopulárnější hlavolam současnosti“ [11]. Řešení Sudoku je věcí logického myšlení ne matematickou úlohou, jak se může na první pohled zdát. A na oblibě ji přidává i fakt, že není závislá na žádném jazyce, z čehož vyplývá, že nevyžaduje žádnou slovní zásobu ani žádné vědomosti.
- 16 -
Číslice v řádku, sloupci a blocích jsou všude ve světě stejné, proto je možné je nahradit jakýmikoliv devíti symboly. Sudoku se dá hrát například s písmenky, obrázky nebo barvami. Rovněž počet polí je měnitelný. Pro děti je možné mít Sudoku jen třeba o 4 x 4 polích a naopak pro profesionály a velmi dobré hráče třeba Sudoku o rozměrech 16 x 16 polí. Na obrázkcích jsou nějaké ukázky.
Další výhodou může být fakt, že existuje obrovské množství různých zadání. Pokud se totiž na Sudoku podíváme z matematického hlediska, tak nám vyjde, že je přesně 6 670 903 752 021 072 936 960 (přibližně 6,67 triliard) možností, ke kterým se vrátím ještě později. Jinak řečeno. Za předpokladu, že byste začali luštit v den svého narození a dožili se stovky let, tak byste museli každou sekundu vyluštit přibližně 2 113 881 838 930 Sudoku což je nemožné [5]. O popularitě Sudoku svědčí i to, že se v březnu roku 2006 konalo v italském městě Lucca první oficiální mistrovství světa v Sudoku, které překvapivě vyhrála Češka Jana Tylová. Když porazila všech 87 soupeřů z 22 zemí světa. Druhé mistrovství světa se konalo od 28. 3. do 1. 4. 2007 v Praze a mistrem světa se stal Američan Thomas Snyder [11]. Vůbec poprvé na světě vypravily České dráhy 10. 11. 2007 na koleje „sudokuvlak“. Šlo o pendolino na trase Praha-Brno a zpět. V rámci společné akce železnice, Českého rozhlasu Online a knihkupectví Kanzelsberger tehdy proběhl dětský turnaj v Sudoku [11]. - 17 -
Někteří dokonce hovoří o tom, že tento hlavolam se stal stejně populárním jako před lety Rubikova kostka, se kterou má Sudoku mnoho společného. Protože kostka se dá otáčet třemi směry a každá z její strany se skládá z 3 x 3 čtverečků. Sudoku má taky 3 dimenze: řádky, sloupce a bloky. V Sudoku je také 3 x 3 čtverců a každý z nich má 3 x 3 políček. Jelikož je omezený počet postupů při řešení, dá se očekávat, že této hře časem odvane popularita.
1.8
Varianty Sudoku [8] Bylo vymyšleno obrovské množství různých Sudoku. A tady jsou ukázky jen
některých z nich:
1.8.1 Sudoku s nápovědou (neboli Number 1
Place Sudoku)
9
8
2
6
Takto vypadalo původní zadání Sudoku,
3
které vymyslel Howard Garns. Pravidla pro řešení
1
jsou stejná jako u normální Sudoku, jen je tu malá
2
9
čísla, která jsou potřeba doplnit do kroužků v zadání. Čísla můžeme doplňovat v libovolném pořadí, protože do každého kroužku padne pouze 1 číslo z nabídky.
4 1 3
nápověda na začátek. Pod tabulkou jsou uvedena 7 5
3
1
5 8
2
9 6
8
6
1249
- 18 -
2
1 8
7
9
1
9
8
2
6 3
1 2
4 1 3
9
3
2
Klasické Sudoku, jak je znáte z většiny
1
novin a časopisů.
5 8
2
9 6
8
7 5
1.8.2 Klasické Sudoku (neboli Classic Sudoku)
7
1 8
6
9
1.8.3 X Sudoku (neboli Diagonal Sudoku)
1 2
Liší se od klasického Sudoku tím, že se
6
9
4
3
čísla 1 – 9 musí objevit i na diagonále.
2 7
6
5
5
8 7 5
4
8
7 2 3 6
6
9
(neboli
Odd/Even
Pravidla jsou podobná jako při klasickém
9 8
3
Sudoku jen s tím rozdílem, že na šedých polích
5 8
7 9
8
9
7 9
8
Sudoku
1
Sudoku)
4
7
1.8.4 Sudá/Lichá
7 5
9
8
3
7
4
můžou být jen sudá čísla a na bílých polích jen lichá 1
čísla.
4 8
3
5
- 19 -
1.8.5 Sudoku s netypickými oblastmi (neboli Extra-Regions Sudoku) Čísla od 1 do 9 se navíc objeví i na stejně barevných polích.
1.8.6 Menší/Větší Sudoku (neboli Sudoku < >) U tohoto typu Sudoku musí platit matematická znaménka > (menší než) a < (větší než) pro doplněná čísla podle konkrétního zadání.
1.8.7 Šipkové Sudoku (neboli Arrow Sudoku) Další velice zajímavá možnost Sudoku. Princip spočívá v tom, že číslo, které se objeví v kolečku, se musí rovnat součtu všech čísel, kterými prochází daná šipka za dodržení všech základních pravidel.
- 20 -
1.8.8 Početní Sudoku (neboli Calcudoku) U tohoto Sudoku doplňujeme jen číslice od 1 do 6 a musí platit, že v každém řádku a sloupci se vyskytne právě jedna z těchto číslic. A druhou podmínkou je, že v označeném bloku se musí objevit taková čísla, aby součet, rozdíl, součin či podíl se rovnal číslu v zadání. U podílu vždycky dělíme menší číslo od většího. Např. v pravém horním rohu, kde vidíme matematickou operaci 6+ pro 2 políčka, se mohou objevit tyto kombinace čísel: 1+5, 2+4.
1.8.9 Kruhové
Sudoku
(neboli
Circle
Sudoku) Do tohoto Sudoku doplňujeme čísla od 1 do 12. Musí platit, že v každém ze 6 kruhů se musí objevit každé číslo jen jednou. A v barevně odlišných kruhových výsečích se rovněž musí objevit všechna čísla 1 – 12.
1.8.10 Samurajské
Sudoku
(neboli
Samurai Sudoku) Toto Samurajské Sudoku se liší od klasického Sudoku jen tím, že je zde spojeno více klasických Sudoku do jedné větší Sudoku.
- 21 -
1.9
Matematika Sudoku Sudoku je velmi zajímavá nejen pro luštitele, ale také pro matematiky.
Matematickou analýzu Sudoku můžeme rozdělit do dvou oblastí. První z nich se zaměřuje na počet všech možných Sudoku a druhá se zaměřuje na počet vyplněných polí.
1.9.1 Všechny možnosti Sudoku
Prvně si musíme uvědomit, že Sudoku je zvláštním případem latinských čtverců, které byly vysvětleny výše. Výpočet latinských čtverců je sám o sobě složitým úkolem, protože není znám žádný obecný vzorec. Je známo, že počet latinských čtverců rozměru 9 x 9 je N1 = 5 524 751 496 156 892 842 531 225 600 5,525 10 27 V Sudoku jsou další omezující podmínky, takže toto číslo bude o něco menší a to přesně N0 = 6 670 903 752 021 072 936 960 6,671 10 21 všech možností [16]. Nyní naznačím, jak lze k tomuto číslu dojít. Budu uvažovat blok 1 v tomto tvaru:
Tato N1 =
úvaha
mi
sníží
1
2
3
4
5
6
7
8
9
počet
možností
o
9!
=
362 880.
Dostáváme
N0 1,838 1016 , což je počet možností Sudoku, které mají blok 1 v uvažovaném 9!
tvaru. - 22 -
Teď musím zvážit všechny možné způsoby jak vyplnit blok 2 a blok 3. Začnu prvním řádkem bloku 2 a 3. Je jasné, že tento řádek budou tvořit čísla z 2. a 3. řádku bloku 1 v libovolných kombinacích. Nyní vypíši všechny možné trojice čísel pro první řádek 2. a 3. bloku, pro které platí, že číslice v trojici jdou vzestupně. {4, 5, 6}{7, 8, 9}
{5, 6, 7}{4, 8, 9}
{4, 5, 7}{6, 8, 9}
{5, 6, 8}{4, 7, 9}
{4, 5, 8}{6, 7, 9}
{5, 6, 9}{4, 7, 8}
{4, 5, 9}{6, 7, 8}
{5, 7, 8}{4, 6, 9}
{4, 6, 7}{5, 8, 9}
{5, 7, 9}{4, 6, 8}
{4, 6, 8}{5, 7, 9}
{5, 8, 9}{4, 6, 7}
{4, 6, 9}{5, 7, 8}
{6, 7, 8}{4, 5, 9}
{4, 7, 8}{5, 6, 9}
{6, 7, 9}{4, 5, 8}
{4, 7, 9}{5, 6, 8}
{6, 8, 9}{4, 5, 7}
{4, 8, 9}{5, 6, 7}
{7, 8, 9}{4, 5, 6}
Když si teď vezmu nejlehčí možnost, kdy jsou čísla vzestupně, tzn. {4, 5, 6}{7, 8, 9}. Lze lehce ukázat, že trojice čísel {4, 5, 6} i {7, 8, 9} lze napsat v šesti různých kombinacích. {4, 5, 6} {4, 6, 5}{5, 4, 6}{5, 6, 4}{6, 4, 5}{6, 5, 4} {7, 8, 9} {7, 9, 8}{8, 9, 7}{8, 7, 9}{9, 7, 8}{9, 8, 7} Tzn. 2 (3!) 6 93 312 možností kombinací pro doplnění 2. a 3. bloku s trojicí čísel {4, 5, 6} {7, 8, 9}. Další případy doplnění 2. a 3. bloku, kdy čísla horní řady mohou být v libovolných kombinacích už jsou složitější, ale stále rychle spočitatelné. Vezmu zase příklad, kdy do 1. řádku 2. a 3. bloku doplním smíšené trojice {5, 7, 9} a {4, 6, 8}.
- 23 -
1
2
3
5
7
9
4
6
8
4
5
6
8
X
Y
7
9
Z
7
8
9
4
6
Z
5
X
Y
Do dalších řádků jsem doplnila 1 z mnoha možností, která se tam může objevit a písmena X, Y a Z jsou doplněna místo číslic 1, 2 a 3. Protože tyto čísla se můžou libovolně na písmenech umístit. Máme tedy 3 možnosti pro 3 číslice na 6 pozicích. Když to zapíšu matematicky, tak dostávám: 3 (3!) 6 . Stejně můžu postupovat i pro dalších 17 polí v bloku 2 a 3. Celkový počet možností vyplnění bloků 2 a 3 při pevně uvažovaném bloku 1 je: 2 (3!) 6 18 3 (3!) 6 56 (3!) 6 2612736. Vypsat všechny možnosti vyplnění bloku 2 a 3 by nám trvalo strašně dlouho, abychom pomocí toho mohli spočítat všechny možnosti Sudoku, budeme se proto snažit toto číslo co nejvíce snížit. Naštěstí existuje hned několik možností. První možností je obměňování sloupců v bloku 2 a 3. Podobně jako výše, těchto možností je 2 6 2 72. Snížením celkového čísla dostáváme
2612736 36288. 72
Ve skutečnosti jsme nevyčerpali ještě úplně všechny možnosti. Protože první blok uvažujeme pořád stejný. Ale téměř analogicky bychom to mohli udělat i s blokem 1, že bychom měnili jeho sloupce. Takto bychom znova snížili číslo pro vyplnění bloku 2 a 3 na 2051 možností [16]. Další možností je obměňovat úplně analogicky řádky. Tím se nám sníží možnosti pro blok 2 a 3 na 416 [16]. Další snížení docílíme tím, když se zaměříme na zdvojená čísla. Ukážu to na příkladě.
- 24 -
1
2
3
4
5
8
6
7
9
4
5
6
1
7
9
2
3
8
7
8
9
2
3
6
1
4
5
Když se podívám na dvojici čísel {1,4}, {5,8},{6,9} a {3,7}, tak je vidět, že ve sloupcích, když tyto čísla proměním, tak se nic nestane.
1
2
3
4
5
8
6
7
9
4
5
6
1
7
9
2
3
8
7
8
9
2
3
6
1
4
5
Při použití tohoto omezení se nám počet sníží jen na 71 možností [16]. Hodně podobně jako pro blok 2 a 3 bychom mohli postupovat pro blok 4 a 7. Postup, který jsem popisovala až doteď, se dále znatelně komplikuje, proto ho dále nebudu uvádět. Zmíním, že na celkový počet všech možností byl vymyšlen počítačový program Bertramem Felgenhaurem a Frazerem Jarvisem v roce 2005, který dokáže spočítat všechny možné kombinace, a který je z velké části naprogramován pomocí postupu, který jsem uváděla [17]. Je známo, že celkový počet všech možných kombinací je 9! 72 2 2 7 27704267971 6 670 903 752 021 072 936 960 6,671 10 21 . [16]
1.9.2 Počet vyplněných polí v Sudoku
Nyní se budu zabývat tím, jaký minimální počet polí musí být předvyplněn, aby Sudoku bylo řešitelné. Ale nejprve vysvětlím, kdy je Sudoku řešitelné a kdy ne. Dostáváme dvě možnosti řešení: řešitelné přímou logickou cestou = jediná možnost řešení neřešitelné o více správných řešení
zkouším dosazovat náhodně čísla, protože je nelze dosadit podle žádných logických pravidel, jen dodržuji základní pravidlo Sudoku, - 25 -
takže se může stát, že do políčka můžu umístit více různých čísel a dostanu správné řešení
příkladem může být úplně prázdná mřížka, do které doplním libovolně čísla, aby bylo dodrženo základní pravidlo Sudoku
o špatně předvyplněná čísla
jako příklad může být Sudoku, která bude mít v prvním řádku předvyplněno dvakrát číslo 1
Je dokázáno, že musí být zadáno minimálně 17 čísel, aby bylo Sudoku řešitelné s jediným správným řešením [10]. Neznamená to však, že Sudoku, které má vyplněné více čísel, je jednodušší. Obtížnost záleží na tom, jak jsou čísla rozmístěna a na jejích vzájemných vazbách, které na první pohled nejsou vidět. Můžeme tedy rozdělovat Sudoku podle obtížnosti do dvou skupin: lehké – průměrnému hráči zabere jen pár minut těžké – průměrnému hráči může trvat i několik desítek minut, než dojde ke správnému řešení Je dokázáno, že Sudoku je neřešitelné, pokud nemá zadáno ani jedno číslo v prvních 3 řadách, i kdyby byly všechny zbývající číslice doplněny. Složité jsou právě ty úlohy, kde existují prázdné velké plochy, například dva čtverce 3 x 3 naproti sobě na diagonále. Sudoku, které by v zadání mělo úplně prázdné 3 čtverce 3 x 3, tak by se nedalo vyluštit logickým postupem. Dobré Sudoku musí jít vždy vyluštit logicky a ne tak, že tipujeme čísla a jakmile se dostaneme do slepé uličky, tak číslo vygumujeme a zkoušíme znova [18].
1.10 Metody pro řešení Sudoku Při řešení lehkých Sudoku si ve většině případů vystačíme se základními metodami řešení, kterými jsou doplnění jediné možné číslice pro určité pole nebo jediné možné
- 26 -
umístění číslice v některém řádku, sloupci či bloku 3 x 3. U těžších úloh již tomu tak není. Zde je potřeba si pomoci ještě dalšími, složitějšími metodami či technikami řešení. Metody řešení můžeme rozdělit do dvou oblastí: metody určující přímo čísla o jediné ve skupině o jediná možnost metody omezující počet kandidátů o průsečíky skupin o holé množiny o zobecněné dvojice o XY – křížení o vedoucí prvek o prázdný čtverec V následujících kapitolách všechny tyto metody vysvětlím
1.10.1 Metody určující přímo čísla 1.10.1.1 Jediné ve skupině
Tato velmi jednoduchá metoda vychází ze základního pravidla Sudoku, které říká, že se ve skupině může každé číslo vyskytovat právě jednou. Hledám tedy takové pole, na které můžu umístit číslo, abych neporušila základní pravidlo. Tuto metodu objasním na příkladě a to konkrétně pro číslo 1.
- 27 -
Na prvním obrázku je výchozí situace. Napravo od něj jsou žlutě vybarvena pole, na kterých se jednička vyskytuje anebo pole, na které přichází jednička v úvahu. Vidíme, že v bloku 2, 6 a 7 je vždy pouze jedno pole, kam můžeme jedničku umístit. Když na tyto pole jedničku umístíme (jak je vidět na obrázku 3), zůstane nám v bloku 9 pouze jedno pole místo čtyř původních, kam můžeme jedničku vložit. Na posledním obrázku jsou doplněny všechny jedničky na správných pozicích. Toto je podstata této metody.
1.10.1.2 Jediná možnost
Druhou jednoduchou metodou, která vychází ze základního pravidla Sudoku, a která umožňuje určit číslo, které má být do pole zapsáno, je metoda „jediná možnost“. Tato metoda, spočívá v tom, že hledám pole, na které můžu umístit jen jediné číslo, aniž bych měla v řádku, sloupci či bloku duplikátní číslo. Pro lepší pochopení uvedu názorný příklad.
- 28 -
Na obrázku jsou dvě pole vybarvena žlutě. Pokud projdu všechny možnosti, jaké číslo lze na tyto pole zapsat, zůstane mi pouze jediná možnost pro obě pole a to číslo čtyři. Na tomto principu funguje celá metoda „jediné možnosti“.
1.10.2 Metody omezující počet kandidátů 1.10.2.1 Průsečíky skupin Přesněji bych měla psát průsečíky bloku s řádkem nebo sloupcem. Představte si následující situaci. Budu uvažovat průsečík řádku s blokem. Pole řádku jsou na obrázku označena zeleně, pole bloku modře a jejich průsečík žlutě. Předpokládám, že se v průsečíku na žlutě označených polích vyskytují buď dvě, nebo tři stejné číslice jako kandidáti. Pak mohou nastat dvě situace.
První varianta nastává v případě, pokud se číslo z průsečíku nevyskytuje již nikde jinde v řádku (na zelených polích), ale vyskytuje se na některých modrých polích v bloku. Z toho plyne, že nutně musí být číslice umístěna na některém ze žlutých polí (aby byla - 29 -
dodržena podmínka, že se číslice musí na řádku vyskytnout právě jednou) a jednak fakt, že se tedy nemůže vyskytnout na žádném z modrých polí (aby byla dodržena podmínka, že se číslice v bloku musí objevit právě jednou) a proto ji můžeme bez obav vyškrtnout ze všech modrých polí, kde se vyskytuje jako kandidát. Na konkrétním příkladě to bude vypadat následovně. 2346
1
456
9
56
4
345
8
7
3489
3457
45789
2
1578
47
345
345
6
4689
4567
45678
4567
5678
3
2
1
459
9 3689
367
1
67
4
5
378
237
238
346
34567
2
1
67
8
9
3457
345
489
457
45789
3
2
79
6
457
1458
1246
9
3
8
57
247
1457
24567
1245
7
246
46
45
359
1
3458
23456
23458
5
8
4
47
379
6
1347
9
1234
V průsečíku bloku 4 a řádku 4 je jedna devítka. Vzhledem k tomu, že je to jediná devítka v řádku, je jasné, že nemůže být na jiné pozici, proto ji můžu z bloku 4 vyškrtnout ze všech kandidátů, to znamená na pozici (6,1) a (6,3). Druhá varianta nastává v případě, že se kromě průsečíku vyskytuje číslo ještě na některém z polí v řádku a nevyskytuje se ve zbylé části bloku (tzn. na modrých polích). Pokud má být opět dodržena podmínka, že se v bloku má vyskytnout právě jedna číslice, znamená to, že musí být na některém ze žlutých polí a nemůže tedy být na žádném ze zelených polí. Bez obav ji můžeme na všech zelených polích v řádku vymazat ze seznamu kandidátů. Opět ukázka na konkrétním příkladě.
- 30 -
2346
1
456
9
56
4
345
8
7
3489
3457
45789
2
1578
47
345
345
6
4689
4567
45678
4567
5678
3
2
1
459
9 3689
367
1
67
4
5
378
237
238
346
34567
2
1
67
8
9
3457
345
489
457
45789
3
2
79
6
457
1458
1246
9
3
8
57
247
1457
24567
1245
7
246
46
45
359
1
3458
23456
23458
5
8
4
47
379
6
1347
9
1234
Je vidět, že v průsečíku bloku 8 a řádku 7 je jedna dvojka. Vzhledem k tomu, že je to jediná dvojka v bloku, je jasné, že nemůže být na jiné pozici, proto můžu ze zbytku řádku eliminovat zbylé kandidáty na číslo 2 označené malými modrými čísly.
1.10.2.2 Holé množiny Tato metoda je velmi jednoduchá a většinou není problém příslušná pole s holou množinou nalézt. Podstatou metody je situace, kdy se v jedné skupině vyskytuje N polí, která obsahují právě N kandidátů. Vyjdu z nejjednodušší varianty – dvě pole a dva kandidáti. Představte si situaci, kdy máme na dvou polích ve skupině právě dva kandidáty, například A a B. Je jasné, že tato dvě pole se v konečném výsledku podělí o tato dvě čísla, a tím pádem lze tato dvě čísla vymazat ze všech kandidátů v ostatních polích skupiny. „Obrazně“ znázorním tuto situaci pro dvě čísla v řádku.
- 31 -
Na žlutých polích jsou pouze dva kandidáti A a B a na zbývajících polích v řádku mohou být libovolní kandidáti (včetně A i B). Z toho vyplývá, že v konečném řešení nastane právě jedna z těchto dvou možností, žádná jiná:
nebo
To znamená, že na všech zbývajících polích v řádku můžeme případné kandidáty A a B vymazat. Stejné pravidlo platí i pro sloupce a bloky. Uvedená situace platí pro 2 čísla na dvou polích. Ale úplně stejně by to platilo pro 3 čísla na třech polích, 4 čísla na 4 polích atd. Holé množiny se při řešení vyskytují velmi často, občas i ve velkém množství. Na dalším obrázku jsem zvýraznila holou množinu čísel 3, 4 a 5 v bloku 3. 2346
1
456
9
56
4
345
8
7
3489
3457
45789
2
1578
47
345
345
6
4689
4567
45678
4567
5678
3
2
1
459
9 3689
367
1
67
4
5
378
237
238
346
34567
2
1
67
8
9
3457
345
489
457
45789
3
2
79
6
457
1458
1246
9
3
8
57
247
1457
24567
1245
7
246
46
45
359
1
3458
23456
23458
5
8
4
47
379
6
1347
9
1234
Po aplikaci metody bych na zbývajícím poli v bloku 3 mohla vymazat kandidáta 4 a 5 a zbylo by tu jen jediné číslo 9, které bych hned mohla dosadit. - 32 -
1.10.2.3 Zobecněné dvojice Realizace a princip této metody je jednodušší a názornější než většina výše uvedených metod, vyhledávající příliš konkrétní kombinace. Začneme definicí.
Definice: Předpokládejme, že máme dvě vázané dvojice (d1 a d2) čísla n, které mají svůj konec ve stejné skupině (řádek, sloupec, blok). Označme A množinu všech polí, na které vidí začátek dvojice d1 a B množinu všech polí, na které vidí začátek dvojice d2. Jestliže v průniku A a B se vyskytuje pole, obsahující jako kandidáta číslici n, můžeme ji z tohoto pole vymazat.
Nyní ukážu, jak to vypadá názorně. Připomínám však, že vázaná dvojice je dvojicí čísel, které se vyskytují jako kandidáti ve skupině (řádku, sloupci nebo bloku). Na obrázku jsou znázorněny dvě vázané dvojice nějakého čísla (označeného hvězdičkou). Vazba je znázorněna modrou čárou. Konec z každé dvojice musí končit podle definice ve stejné skupině, v našem případě je to blok 7, vybarvený zelenou barvou.
Začátek druhé dvojice d2
Konec první dvojice d1
Konec druhé dvojice d2
Začátek první dvojice d1
Na následujícím obrázku jsou barevně zobrazena pole, na která „vidí“ začátky dvojic. U první dvojice je množina polí A znázorněna modrou barvou, u druhé dvojice je množina B znázorněna žlutou barvou a oranžově je znázorněn průnik těchto dvou množin. Pokud se na oranžově zvýrazněném poli vyskytuje jako kandidát číslice, ze které jsou složeny vázané dvojice, pak můžeme tuto číslici ze seznamu kandidátů na oranžovém poli vymazat.
- 33 -
Nyní podrobněji vysvětlím, jak tato metoda funguje. Platí, že ve vázané dvojici jedna z číslic musí platit. Z toho vyplývá, že pro každou dvojici mám 2 možnosti. Nejprve budeme uvažovat dvojici d2. Předpokládám, že platí číslice na poli (2, 2). Pak je jasné, že nemůže platit číslice na oranžovém poli. Ve druhém případě uvažuji, že platí číslice na poli (7, 2), z toho plyne, že nemůže platit číslice na poli (9, 3) a musí platit číslice na poli (9, 7). A z toho opět vyplývá, že nemůže platit číslice na oranžovém poli. Pro dvojici d1 by byl postup analogický. Zajímavé je i to, že na polích označených křížkem se klidně mohou vyskytovat jako kandidáti stejné číslice, jako ve dvojicích aniž bychom narušili princip této metody. Tím jsme ale ještě nevyčerpali všechny možnosti této metody. Platí totiž další pravidlo, které říká:
Pravidlo 1: Jestliže máme N vázaných dvojic takových, že tyto dvojice mají v sekvenci vždy jeden konec umístěn ve společné skupině, pak pro koncové body takové sekvence platí stejný důsledek jako pro výše zmíněné dvě dvojice.
Ukážu opět názorné zobrazení (viz. Následující obrázek) pro tři vázané dvojice d1, d2 a d3. Konec první dvojice na pozici (9, 9) sdílí společný řádek 9 se začátkem druhé dvojice na pozici (9, 6) a konec této druhé dvojice na pozici (8, 4) sdílí společný řádek 8 se začátkem třetí dvojice na pozici (8, 1). Začátek první dvojice na pozici (2, 9) „vidí“ na pole znázorněna modrou barvou, konec třetí dvojice na pozici (3, 1) „vidí“ na pole znázorněna žlutou barvou a oba konce společně „vidí“ na pole znázorněna oranžovou barvou. Opět jednoduše odvodíme platnost výše zmíněného tvrzení. Platí-li číslo na pozici (2, 9) nemohou platit kandidáti stejného čísla na oranžových polích. Pokud ale číslo na této pozici neplatí, musí tudíž platit číslo na (9, 9), z toho plyne, že nemůže platit toto samé číslo na pozici (9, 6), ale musí z druhé dvojice platit číslo na pozici (8, 4), a to samé - 34 -
pro třetí dvojici. Nemůže platit číslo na pozici (8, 1), ale platí na pozici (3, 1). Z toho je opět zřejmé, že se nemůžou na oranžových polích vyskytnout kandidáti daného čísla. Začátek první dvojice d1
Konec třetí dvojice d3
Začátek druhé dvojice d2 Konec druhé dvojice d2
Začátek třetí dvojice d3
Konec první dvojice d1
V těchto úvahách můžeme pokračovat ještě dále. Když se na předchozí obrázek podíváme podrobněji, vidíme, že naše tři dvojice můžeme rozdělit na dvě dvojice. První dvojici tvoří dvojice d1 a d2 a druhou dvojice d2 a d3. Nyní můžeme použít výše zmíněné pravidlo 1 pro dvě vázané dvojice. Dostáváme, že konce první dvojice společně „vidí“ na pole (2,4). A obdobně pro druhou dvojici, která „vidí“ na pole (3,6), na obrázku jsou tyto pole znázorněna světle oranžovou barvou. To však znamená, že na těchto dvou polích můžeme rovněž vymazat případné kandidáty a vyslovit další pravidlo.
Pravidlo 2: Jestliže máme N vázaných dvojic takových, že tyto dvojice mají v sekvenci vždy jeden konec umístěn ve společné skupině, pak pro koncové body takové sekvence platí stejný, výše zmíněný důsledek pro každou souvislou podsekvenci složenou z nejméně dvou vázaných dvojic.
- 35 -
To znamená, že pokud budeme mít v sekvenci například pět dvojic, označím je d1 – d5, nehledáme kandidáty na vyškrtnutí pouze pro koncové body celé sekvence, ale pro všechny koncové body následujících sekvencí: d1 – d2, d2 – d3, d3 – d4, d4 – d5, d1 – d2 – d3, d2 – d3 – d4, d3 – d4 – d5, d1 – d2 – d3 – d4, d2 – d3 – d4 – d5, d1 – d2 – d3 – d4 – d5. A abych vyčerpala všechny možnosti až do dna, můžu poslední pravidlo ještě trochu vylepšit.
Pravidlo 2: Tvoří-li sekvence dvojic uzavřený cyklus (první a poslední dvojice mají jeden svůj konec ve společné skupině), pak platí výše zmíněné důsledky pro každou podsekvenci cyklu, složenou z nejméně dvou dvojic.
Pro výše uvedený výčet by to znamenalo, že bych mohla přidat ještě podsekvence, které procházejí přes spojnici d1 – d5 (čili například d4 – d5 – d1 nebo d5 – d1 – d2). Nyní ukážu konkrétní příklad. Zpočátku je možné řešit každou Sudoku jednoduššími metodami, které jsem popsala na začátku, aby se nám Sudoku zjednodušilo. Teď ale chci ukázat, jak se dá použít pouze poslední zmíněná metoda na příkladě, proto se jinými metodami nebudu zabývat. Pokud si zobrazíme kandidáty, dostaneme zobrazení, které je vidět na následujícím obrázku a na kterém jsem už zvýraznila i některé možnosti pro tuto metodu.
- 36 -
2346
1
456
9
56
4
345
8
7
3489
3457
45789
2
1578
47
345
345
6
4689
4567
45678
4567
5678
3
2
1
459
9 3689
367
1
67
4
5
378
237
238
346
34567
2
1
67
8
9
3457
345
489
457
45789
3
2
79
6
457
1458
1246
9
3
8
57
247
1457
24567
1245
7
246
46
45
359
1
3458
23456
23458
5
8
4
47
379
6
1347
9
1234
Vidíme zde sekvenci třech silně vázaných dvojic kandidáta 3: (4,2) – (2,2), (1,1) – (1,7) a (8,7) – (8,9). Koncové body (4,2) a (8,9) „vidí“ společně na pole (4,9), které taky obsahuje kandidáta číslici 3 a tudíž můžeme trojku z tohoto pole vypustit. Výše jsem zmínila pravidlo, které tvrdilo, že je možné v sekvenci většího počtu dvojic vyzkoušet i kratší sekvence. 2346
1
456
9
56
4
345
8
7
3489
3457
45789
2
1578
47
345
345
6
4689
4567
45678
4567
5678
3
2
1
459
9 3689
367
1
67
4
5
378
237
238
346
34567
2
1
67
8
9
3457
345
489
457
45789
3
2
79
6
457
1458
1246
9
3
8
57
247
1457
24567
1245
7
246
46
45
359
1
3458
23456
23458
5
8
4
47
379
6
1347
9
1234
- 37 -
Pokud budeme uvažovat jen první dvě dvojice, čili (4,2) – (2,2) a (1,1) – (1,7), pak jejich koncová pole „vidí“ na pole (4,7), které taky obsahuje kandidáta 3, kterého zde můžu opět eliminovat.
1.10.2.4 XY – křížení Tato metoda nám může pomoci v situacích, kdy si myslíme, že již nelze pokračovat. Často se nám podaří jediným tahem odblokovat zdánlivě těžko řešitelnou situaci. Při této metodě musíme vždy vycházet z vedoucího pole, na kterém se vyskytují dva kandidáti na řešení. Toto pole musí „vidět“ na další dvě pole, které obsahují opět dvojici kandidátů, přičemž jeden z kandidátů je totožný s jedním z kandidátů na vedoucím poli a druhý kandidát musí být pro obě pole společný. Vypadá to složitě, ale z obrázku to bude jasnější.
Žlutě je znázorněno vedoucí pole, které obsahuje dvojici kandidátů X a Y. Růžově jsou znázorněna pomocná pole, na která vedoucí pole „vidí“. Na těchto polích se musí vyskytovat vždy jeden z kandidátů z původního pole (v našem případě X nebo Y) a jeden nový společný kandidát označený C. Tato pomocná pole mají svou množinu polí, na které „vidí“. Pro pole YC jsem množinu polí označila zelenou barvou a pro pole XC modrou barvou. Průsečík těchto dvou množin jsem znázornila oranžově. Pokud se na těchto polích vyskytuje v seznamu kandidátů číslo C, můžeme je ze seznamu vyškrtnout. A teď objasním, jak to funguje. Na žlutém vedoucím poli bude v konečném řešení buď X nebo Y, nic jiného se tam objevit nemůže. Pokud budu uvažovat, že zde bude X, pak na poli s kandidáty XC může být jen C a na oranžově označených polích být tedy C - 38 -
nemůže. Pokud budu uvažovat druhou možnost, že na vedoucím poli bude Y, pak na poli s kandidáty YC musí být C a opět na oranžovém poli být C nemůže. A nyní ukázka na konkrétním zadání Sudoku. Žlutě je zvýrazněno vedoucí pole (9,4) a růžově znázorněny zbylé prvky XY – křížení. Oranžovou barvou jsou pak znázorněna pole, z nichž můžeme odebrat kandidáta číslice 5. 2346
1
456
9
56
4
345
8
7
3489
3457
45789
2
1578
47
345
345
6
4689
4567
45678
4567
5678
3
2
1
459
9 3689
367
1
67
4
5
378
237
238
346
34567
2
1
67
8
9
3457
345
489
457
45789
3
2
79
6
457
1458
1246
9
3
8
57
247
1457
24567
1245
7
246
46
45
359
1
3458
23456
23458
5
8
4
47
379
6
1347
9
1234
1.10.2.5 Vedoucí prvek Tato metoda se hodně podobá předchozí metodě XY – křížení s tím rozdílem, že nemusíme mít pouze dva kandidáty. Ale zase je větší problém tuto situaci při řešení najít. V této metodě se vždy jedná o dvojici blok + řádek a blok + sloupec. Ve srovnání s metodou XY – křížení se může na vedoucím poli (označeno žlutou barvou) vyskytnout více kandidátů, včetně kandidáta na odstranění. To samozřejmě vyžaduje, aby se na polích, na která vedoucí prvek v této kombinaci „vidí“, vyskytly všechny kombinace kandidáta na odstranění se všemi ostatními kandidáty na vedoucím poli. Tím se omezí množina prvků, ze kterých můžeme kandidáta C vyškrtnout. Protože všechna dotyčná pole musí na tyto pole „vidět“. Na následujícím obrázku je názorná ukázka. Společnou podmnožinu všech barevných polí s kandidáty jsem označila oranžovou. - 39 -
Teď trošku jak to funguje. Pokud bude v konečném řešení na vedoucím poli některý z kandidátů A – F mimo C, zbylí kandidáti se rozmístí na pole zvýrazněna růžovou barvou a místo kandidáta, který se umístil na žlutém poli, bude v růžovém poli kandidát C. Z toho vyplývá, že na oranžovém poli už být kandidát C nemůže a stejně tak v opačném případě, pokud kandidát C by byl na žlutém vedoucím poli. Počet kandidátů na vedoucím poli může být 2 a více. Ale každému kandidátovi musí odpovídat pole znázorněná v našem případě růžovou barvou s dvojicí kandidátů. Jeden musí být z vedoucího pole a druhý, kterého chceme odstranit, který se objeví na všech námi uvažovaných polích. Pokud by nastala situace, že by se všechna růžová pole umístila pouze v řádku, sloupci či bloku, zredukovala by se nám metoda na metodu holé množiny.Na následujícím obrázku je reálný příklad. 236
1
5
9
6
4
35
8
7
89
345
89
2
18
7
345
345
6
4689
4567
45789
67
68
3
2
1
59
3689
367
1
6
4
5
38
237
238
346
34567
2
1
67
8
9
3457
35
48
457
4578
3
2
9
6
457
158
1
9
3
8
5
2
7
6
4
7
2
6
4
39
1
358
35
358
5
8
4
7
39
6
13
9
123
- 40 -
Vedoucí prvek jsem zvýraznila žlutě, pomocné prvky jsou zvýrazněny růžově. Při aplikaci metody vedoucího prvku můžeme z pole (9,7) vyškrtnout kandidáta číslice 3.
1.10.2.6 Prázdný čtverec Tato poslední metoda opět patří ke skupině obtížnějších, protože není na první pohled vidět. Ale pokud ji použijeme, často se nám podaří odblokovat těžko řešitelnou pozici. Na následujícím obrázku, jsem ve druhém sloupci znázornila silně vázanou dvojici nějakého kandidáta n. V bloku 9, jsou na polích vybarvených růžovou barvou buď vyřešená čísla, nebo jsou to pole, na kterých není číslo n kandidátem. Naopak na polích označených C se může číslo n jako kandidát vyskytovat. Ale na alespoň jednom z modrých polích v bloku 9 se kandidát n vyskytovat musí. Pokud se v takovémto schématu vyskytne na oranžovém poli kandidát n, můžeme jej vyškrtnout.
Nyní nastíním, na jakém principu tato metoda funguje. Jeden z bodů vázané dvojice bude v konečném řešení kandidáta n obsahovat. Bude-li to na poli označených písmenem A, pak určitě nebude kandidát n na poli označených B a ani na poli oranžové barvy. Ve druhém případě, bude kandidát n na poli B, z čehož vyplývá, že nebude na poli A ani na žádném z polí zeleného řádku. To znamená, že v bloku 9 bude muset být kandidát n na některém z modrých polích označených písmenem C. Odtud je opět vidět, že se kandidát n také nemůže objevit na poli oranžové barvy. Na následujícím obrázku je ukázka reálného příkladu s použitím této metody.
- 41 -
479
1479
14579
489
19
1489
12457
6
12345
3
145
15
1459
89
469
8
2
7
169
4679
3
1479
2
169
5
147
178
1489
2478
47
478
4568
567
4678
3
9
12456
379
4789
247
278
248
8
1
5
6
3489
4789
479
34789
1
35679
2
4567
578
4568
469
1469
149
3569
12356
169
8
1235
7
9
5
1679
1789
369
4
1679
126
123
1236
3
2
17
56
8
169
9
4
156
V prvním sloupci jsem našla vázanou dvojici kandidáta 9. V bloku 2 odpovídají zelená pole polím označených písmenem C z předchozího schématu. Po aplikaci metody prázdného čtverce podle výše zmíněných pravidel, můžeme z pole (7, 5) kandidáta číslo 9 vyškrtnout.
- 42 -
2
MATLAB MATLAB je programové prostředí pro numerické výpočty, modelování, počítačové
simulace, analýzu a prezentaci dat, vizualizaci dat a mnoho dalších podobných věcí. MATLAB umožňuje provádět výpočetně náročné úlohy celkem rychle, proto jeden z důvodů, proč jsem si vybrala právě tento program je rychlost. A druhý důvod je vysvětlen v následujícím odstavci a souvisí s maticemi, které budu hodně využívat. Krátce bych se zmínila o tom, jak vznikl název MATLAB. Vznikl zkrácením dvou slov - MATrix a LABoratory, což volně přeloženo do češtiny znamená „laboratoř s maticemi“. Proto matice jsou klíčovou datovou strukturou tohoto programu. Jak bude vidět v následujících kapitolách, matice budu hrát důležitou roli i pro nás. V dílčích částích této kapitoly se budu věnovat tomu, jak lze naprogramovat v MATLABu magické čtverce, latinské čtverce, řešení jakéhokoliv zadání Sudoku a pak také generování různých zadání Sudoku.
2.1
Magické čtverce v MATLABu V této kapitole se vrátím k již zmíněným magickým čtvercům, které byly
vysvětleny podrobněji v kapitole 1.3. Tady ukážu, jak lze tento čtverec vytvořit v MATLABu. Není to nic složitého, protože základní magický čtverec má MATLAB už předdefinovaný příkazem magic(n) a tudíž lze zadat jen číslo n, které určuje, jakého řádu má výsledný magický čtverec být. Jak tento předdefinovaný algoritmus vypadá a jak ho chápat, tak tomu věnuji následující část. Nejprve se podíváme, jak tento algoritmus vypadá. Což můžete vidět hned na následujících řádcích
- 43 -
fuction M = magic(n) n = floor(real(double(n(1)))); if mod(n,2) == 1 [J,I] = meshgrid(1:n); A = mod(I+J-(n+3)/2,n); B = mod(I+2*J-2,n); M = n*A + B + 1; elseif mod(n,4) == 0 [J,I] = meshgrid(1:n); K = fix(mod(I,4)/2) == fix(mod(J,4)/2); M = reshape(1:n*n,n,n)‘; M(K) = n*n+1 – M(K); else p = n/2; M = magic(p); M = [M M+2*p^2; M+3*p^2 M+p^2]; if n == 2, return, end i = (1:p)‘; k = (n-2)/4; j = [1:k (n-k+2):n]; M([i; i+p],j) = M([i+p; i],j); i = k+1; j = [1 i]; M([i; i+p],j) = M([i+p; i],j); end Jak je vidět, tak algoritmus se rozděluje do čtyř částí, které nyní objasním. Na prvním řádku je nadefinovaná funkce M = magic(n), pomocí které se celý algoritmus spouští. Dále je nadefinováno, že se mají doplňovat čísla 1 až dvojnásobek zadaného čísla n. Tzn. pokud zadáme, že číslo n = 3, pak se do čtverce 3 x 3 doplní čísla 1, 2, 3,…, 9. Analogicky pro libovolné číslo n. První podmínka if mod(n,2) == 1 [J,I] = meshgrid(1:n); A = mod(I+J-(n+3)/2,n); B = mod(I+2*J-2,n); M = n*A + B + 1; platí pro n liché. V našem případě n = 3.
Řádek [J,I] = meshgrid(1:n)
znamená, že se vygeneruje matice J a I v následujícím tvaru
- 44 -
J = 1 1 1
2 2 2
3 3 3
1 2 3
1 2 3
1 2 3
I =
Až máme vygenerované tyto dvě matice, tak můžeme pokračovat v algoritmu, tzn. vypočítat matici A a B, podle nadefinovaného předpisu A = mod(I+J-(n+3)/2,n); B = mod(I+2*J-2,n); Dostaneme matici A =
2
0
1
0
1
2
1
2
0
1
0
2
2
1
0
0
2
1
a matici B =
A teď už nám stačí pouze dopočítat matici M, která už bude námi požadovaným magickým čtvercem, podle následujícího předpisu M = n*A + B + 1 Výsledná matice M vypadá takto
- 45 -
M =
8
1
6
3
5
7
4
9
2
Úplně na stejném principu je vytvořena druhá a třetí podmínka algoritmu. Rozdíl je jen v tom, že pokud zadáme sudé číslo, první podmínku pro lichá čísla nám to přeskočí a číslo n se otestuje, zda je dělitelné 4 nebo není. Pokud je číslo n dělitelné 4, provede se druhá podmínka. Pokud číslo n je sudé, ale není dělitelné 4, provede se třetí podmínka. Výsledkem je vždy správný magický čtverec. Z toho nám plyne, že funkce M = magic(n), dokáže vytvořit magický čtverec jakéhokoliv řádu. Ukážu magický čtverec desátého řádu M =
92
99
1
8
15
67
74
51
58
40
98
80
7
14
16
73
55
57
64
41
4
81
88
20
22
54
56
63
70
47
85
87
19
21
3
60
62
69
71
28
86
93
25
2
9
61
68
75
52
34
17
24
76
83
90
42
49
26
33
65
23
5
82
89
91
48
30
32
39
66
79
6
13
95
97
29
31
38
45
72
10
12
94
96
78
35
37
44
46
53
11
18
100
77
84
36
43
50
27
59
V následující tabulce ukážu, jak dlouho MATLABu trvá vytvořit magické čtverce různých rozměrů. Čas v tabulce je průměrný čas několika pokusů. Tabulka vypadá následovně
- 46 -
Rozměr
Čas (s)
3x3
0.000001
5x5
0.000005
10 x 10
0.000009
50 x 50
0.0706
100 x 100
0.1312
500 x 500
4.2208
1000 x 1000
16.9372
Jak je vidět, vytvoření magického čtverce rozměru 100 x 100 trvá pouze asi jednu desetinu sekundy, což je opravdu velmi rychlé. Menší čtverce zaberou ještě méně. Naopak větší rozměry například čtverec rozměru 1000 x 1000 trvá skoro dvacet sekund. Závislost času na rozměru magického čtverce ukážu na následujícím grafu
Jak je názorně vidět z grafu, do rozměru magického čtverce 100 x 100 je čas vygenerování magického čtverce zanedbatelný. Dále s rostoucím rozměrem magického čtverce roste i výsledný čas generování.
- 47 -
2.2
Latinské čtverce v MATLABu Tuto kapitolu budu věnovat latinským čtvercům, a jak se dají vytvořit
v MATLABu. Bude to o něco těžší, protože MATLAB nemá předdefinovaný žádný algoritmus pro tyto čtverce, jak tomu bylo u magických čtverců v předchozí kapitole. Ale můžeme magické čtverce využít tak, jak jsem psala už dříve v kapitole 1.4 zabývající se latinskými čtverci. Z toho vyplývá, že latinské čtverce můžu vytvořit dvěma způsoby, kterým se teď budu věnovat.
2.2.1 Vytvoření latinského čtverce pomocí magického čtverce
První způsob je s využitím magických čtverců a je jednodušší. Nejprve ale musím vytvořit magický čtverec libovolného řádu a pak do něj místo čísel 1 až n2 dosadit pouze čísla 1 až n. Ukážu to na konkrétním příkladu. Vytvořím magický čtverec pátého řádu pomocí příkazu A = magic(5). A =
17
24
1
8
15
23
5
7
14
16
4
6
13
20
22
10
12
19
21
3
11
18
25
2
9
A teď použiji příkaz B = mod(A,n)+1, který jsem používala už u magických čtverců. V našem případě, kdy n = 5, dostanu po provedení tohoto příkazu latinský čtverec, kde čísla 1 až 5 zůstávají na stejných pozicích a nahrazuju čísla, která jsou větší jak 5. V tomto případě to bude vypadat následovně číslo 6 = 1, 7 = 2, …, 10 = 5, 11 = 1,…, 25 = 5. Když to provedu, dostanu latinský čtverec následujícího tvaru
- 48 -
B =
3
5
2
4
1
4
1
3
5
2
5
2
4
1
3
1
3
5
2
4
2
4
1
3
5
Analogicky lze tímto způsobem vytvořit latinský čtverec libovolný řádu.
2.2.2 Vytvoření latinského čtverce pomocí rekurzivního algoritmu
Tento druhý způsob je o něco těžší, ale zase nám pomůže lépe pochopit výsledný algoritmus pro řešení Sudoku. Což je mým hlavním úkolem této práce. Použiju tedy rekurzivní algoritmus, který nejprve ukážu, jak vypadá, a pak následně jednotlivé kroky vysvětlím. Algoritmus vypadá takto function s = latin(m,s) global delej if ~delej return end n=length(m); if ~exist('s') s = zeros([size(m),0]); end krok = min(find(m(:)==0)); if isempty(krok) s(:,:,size(s,3)+1) = m; delej = false; else [i,j] = ind2sub([n,n],krok); for k = randperm(n) if sum(m(i,:)==k)==0 && sum(m(:,j)==k)==0 m(i,j) = k; s = latin(m,s); end end end - 49 -
Na prvním řádku je opět nadefinovaná funkce pro spouštění. Na druhém řádku nadefinovaná globální proměnná delej, která se při spouštění musí zadat a slouží k tomu, aby vypsala první správné řešení, které najde. Podmínka if ~delej return end říká, že pokud neexistuje proměnná delej, tak se vrať zpátky do algoritmu. Na následujícím řádku je nadefinováno n, takto n=length(m); a znamená to, že číslo n bude stejného rozměru jako zadaná matice m. Řádek obsahující krok = min(find(m(:)==0)) znamená, že se hledá první pozice v matici m obsahující nulu. Může se stát, že se v matici m žádné nuly nevyskytují, proto je tam podmínka if isempty(krok) s(:,:,size(s,3)+1) = m; která říká, že pokud se v matici m nevyskytují žádné nuly, tak máme výsledné řešení, které se má uložit do matice s. Ve druhém případě, kdy se v matici m vyskytují nuly, proběhnou kroky, které následují na dalších řádcích else [i,j] = ind2sub([n,n],krok); for k = randperm(n) if sum(m(i,:)==k)==0 && sum(m(:,j)==k)==0 m(i,j) = k; s = latin(m,s); end end end a tyto řádky obsahují rekurzivní kroky, které se provádějí následujícím způsobem. Dosazuji na nulové pozice matice m postupně čísla k, která jsou náhodně vygenerovanou - 50 -
posloupností zadané posloupnosti čísel. Například pro n = 5, máme posloupnost čísel 1, 2, 3, 4, 5. A když tuto posloupnost čísel náhodně vygenerujeme, můžeme dostat např. k = 5, 3, 1, 4, 2. Tyto čísla postupně dosazuji na pozici obsahující 0 a testuji přitom podmínku, že dané číslo se smí objevit v každém řádku i sloupci jednou. V mém případě najdu první pozici s 0 a zkusím číslo 5, pokud toto číslo nesplňuje danou podmínku, tak zkouším další číslo v pořadí, dokud není splněna zadaná podmínka. Jak najdu první číslo, které splňuje podmínku, tak toto číslo uložím do matice m a jdu hledat znovu další číslo. Pokud nastane situace, že žádné číslo na dané pole není správné, vracím se o krok výše a změním předchozí doplněné číslo na jiné, které vyhovuje. Tento postup opakujeme tak dlouho, až v matici m nejsou žádné nuly. Tento algoritmus nám vypíše první správné řešení, které najde, protože správných řešení může být i více. Teďka ukážu konkrétní příklad na tento algoritmus, který musím mít v MATLABu uložený, aby fungoval. Protože pro spuštění tohoto algoritmu je nutné zadat 4 vstupní argumenty, je lepší si je opět uložit do M-filu, v kterém pak stačí měnit jen číslo n. Tento M-file se vstupníma hodnotami vypadá následovně global delej delej = true; m= zeros(5); s = latin(m) po spuštění tohoto M-filu vidíme hned výsledek. V mém případě, kdy jsem zvolila n = 5, vypadal výsledek následovně. s =
1
2
4
3
5
3
1
2
5
4
5
4
1
2
3
4
3
5
1
2
2
5
3
4
1
Tento výsledek je náhodně vybraný ze všech možností pro daný rozměr. To znamená, že pokud bych M-file spustila znovu, tak je velmi malá pravděpodobnost, že
- 51 -
dostanu úplně stejný latinský čtverec. Kolik je všech možností pro daný rozměr latinského čtverce ukazuje následující tabulka [15]. Rozměr
Počet všech možností
2x2
2
3x3
12
4x4
576
5x5
161 280
6x6
812 851 200
7x7
61 479 419 904 000
8x8
108 776 032 459 082 956 800
9x9
5 524 751 496 156 892 842 531 225 600
Jak je vidět, tak s rostoucím n hodně rychle roste i počet všech možností. Teď ukážu ještě jednu tabulku, ve které bude zapsaný průměrný výsledný čas, vygenerování náhodného latinského čtverce pro různé rozměry, které MATLAB dokáže Rozměr
Čas (s)
2x2
0.015
3x3
0.023
4x4
0.031
5x5
0.047
6x6
0.078
7x7
0.093
8x8
0.106
9x9
0.109
10 x 10
0.1404
15 x 15
0.6518
20 x 20
1.9188
Jak je vidět, čím větší latinský čtverec, tím je potřeba o kousíček delší čas pro vygenerování výsledku. Ale vždy je výsledek téměř okamžitě vygenerovaný. Opět ukážu graf závislosti času na konkrétním rozměru latinského čtverce - 52 -
Jak je vidět z grafu, tak čas mírně roste pro latinské čtverce do rozměru 10 x 10. Tento čas je, ale téměř zanedbatelný. S většími rozměry čas prudce stoupá.
2.3
Algoritmy řešící Sudoku Nyní už se vrhu na to, jak se dá udělat program, který vyřeší jakékoliv zadání
Sudoku. Sudoku lze programově řešit třemi způsoby. První z nich napodobuje lidské myšlení a doplňuje čísla na základě logických dedukcí. Druhý, rekurzivní, prostě zkouší všechny možnosti, dokud nedosáhne cíle. A třetí způsob je kombinací zmíněného prvního a druhého způsobu. Všechny přístupy mají výhody i nevýhody. „Logický" algoritmus zpravidla nedokáže vyřešit všechna zadání Sudoku. Umí jen tolik, kolik jej tvůrce „naučil". Oproti tomu rekurzivní algoritmus vyřeší každé Sudoku a dokonce odhalí i více řešení. Pokud jej spustíme na prázdné mřížce, najde nám všechny možnosti, jak může Sudoku vypadat, ale na výsledek bychom čekali asi hodně dlouho, protože těch možností existuje strašně moc, jak bylo zmíněno v kapitole 1.9.1 a také by nestačila paměť. Třetí způsob je nejlepší.
- 53 -
V této práci se proto budu věnovat pouze třetímu způsobu řešení, protože dokáže hodně rychle vyřešit jakékoliv zadání Sudoku. Čím je více správných řešení, tím je potřeba delší čas na řešení. Jak tento algoritmus vypadá, je vidět v následující části [19] function s = Sudoku(m,s) if any((size(m)-[9 9])~=0) error('Vložená matice m musí mít 9 řádků a 9 sloupců.') end if any(any(m~=floor(m))) || any(abs(m(:)-4.5)>4.5) error('V matici m můžou být pouze čísla 0 až 9.') end if ~exist('s') s = zeros([size(m),0]); end prvni_krok = min(find(m(:)==0)); if isempty(prvni_krok) s(:,:,size(s,3)+1) = m; else [i,j] = ind2sub([9,9],prvni_krok); for k=1:9 radky = (ceil(i/3)-1)*3+1; sloupce = (ceil(j/3)-1)*3+1; bloky = m(radky:radky+2,sloupce:sloupce+2); if sum(m(i,:)==k)==0 & sum(m(:,j)==k)==0 & sum(bloky(:)==k)==0 m(i,j) = k; s = Sudoku(m,s); end end end Tento algoritmus se hodně podobá algoritmu, který jsem popisovala u latinských čtverců v kapitole 2.2.2, proto v této kapitole zmíním jen ty části, ve kterých se od sebe liší. V prvním řádku jsem vytvořila opět funkci s = Sudoku(m, s), pomocí které se bude celý algoritmus spouštět. Kde s je výstupní matice obsahující řešení a m je vstupní matice obsahující předvyplněná čísla. Do vstupní matice zadáváme předvyplněná čísla na konkrétní pozice, na kterých se mají ve výsledku objevit, a na pozice prázdných polí
- 54 -
zapisujeme číslo 0. Jak matici m správně zadat do MATLABu a jak spustit celý algoritmus, ukážu v následující části. Nejprve, jak zadat matici m, která může vypadat například takto m = [0,1,0,9,0,0,0,8,7; 0,0,0,2,0,0,0,0,6; 0,0,0,0,0,3,2,1,0; 0,0,1,0,4,5,0,0,0; 0,0,2,1,0,8,9,0,0; 0,0,0,3,2,0,6,0,0; 0,9,3,8,0,0,0,0,0; 7,0,0,0,0,1,0,0,0; 5,8,0,0,0,6,0,9,0] MATLAB nám ji zobrazí jako matici m =
0
1
0
9
0
0
0
8
7
0
0
0
2
0
0
0
0
6
0
0
0
0
0
3
2
1
0
0
0
1
0
4
5
0
0
0
0
0
2
1
0
8
9
0
0
0
0
0
3
2
0
6
0
0
0
9
3
8
0
0
0
0
0
7
0
0
0
0
1
0
0
0
5
8
0
0
0
6
0
9
0
Nakonec spustím nadefinovaný algoritmus s = Sudoku(m) A za chvíli se objeví výsledná matice s
- 55 -
s =
2
1
5
9
6
4
3
8
7
8
3
9
2
1
7
4
5
6
6
4
7
5
8
3
2
1
9
9
7
1
6
4
5
8
2
3
3
6
2
1
7
8
9
4
5
4
5
8
3
2
9
6
7
1
1
9
3
8
5
2
7
6
4
7
2
6
4
9
1
5
3
8
5
8
4
7
3
6
1
9
2
Řešení tohoto hodně lehkého Sudoku trvalo 2,7 sekund. Ale tato doba se mění v závislosti na obtížnosti zadání Sudoku. Na řešení lehkého Sudoku je potřeba pár sekund, složité zadání Sudoku může trvat i několik desítek sekund. Pokud existuje více správných řešení, tak se nám ve výsledku všechny vypíší. V následující tabulce můžete vidět, jak dlouho v průměru trvalo řešení různých obtížností zadání Sudoku. Různá zadání jsem čerpala z [21] Obtížnost
lehká
Střední
Těžká
Čas (s)
0.078
0.321
2.0215
Je vidět, že daný algoritmus dokáže vyřešit jakoukoliv obtížnost zadání Sudoku v hodně rychlém času. Teď se ještě vrátím k nadefinovanému algoritmu. Vysvětlím, co jednotlivé řádky znamenají. Na třetím až pátém řádku je podmínka, if any((size(m)-[9 9])~=0) error('Vložená matice m musí mít 9 řádků a 9 sloupců.') end která kontroluje, zda vložená matice je správného rozměru, tzn. rozměru 9 x 9. Pokud tomu tak není, tak MATLAB vypíše hlášku, že vložená matice m musí mít 9 řádků a 9 sloupců, což můžete vidět na čtvrtém řádku a je na zadavateli, aby matici zadal správně. - 56 -
Na dalších třech řádcích je podobná podmínka, if any(any(m~=floor(m))) || any(abs(m(:)-4.5)>4.5) error('V matici m můžou být pouze čísla 0 až 9.') end která kontroluje opět vloženou matice, ale tentokrát z pohledu vyplněných čísel. Zde se kontroluje, zda vložená matice obsahuje pouze čísla 1 až 9. Pokud se v matici objevují nesprávná čísla, tak MATLAB vypíše hlášku, že v matici m můžou být pouze čísla 0 až 9. Další části algoritmu jsou téměř stejné jako u latinských čtverců, takže je nebudu znovu vysvětlovat. Jen zmíním, že tento algoritmus se od latinských čtverců liší ve dvou věcech. První věcí je to, že v Sudoku musí platit ještě jedna podmínka navíc. A to ta, že se čísla 1 až 9 musí vyskytovat i v každém bloku 3 x 3. Tato podmínka je do tohoto algoritmu přidána. A celkově tedy podmínka testuje, zda se dané číslo k vyskytuje v každém řádku, sloupci i bloku právě jednou. A druhá odlišnost je v tom, že se zde nemá vybrat náhodně jedno správné řešení, pokud jich existuje více, ale všechna správná řešení zobrazit. Takže se může stát, že řešení nebude jednoznačné, a i když to nebudeme čekat, tak se nám ve výsledku může objevit hned několik správných řešení daného zadání.
2.4
Algoritmy vytvářející zadání Sudoku V této kapitole se budu věnovat tomu, jak vytvořit správné zadání Sudoku, aby bylo
Sudoku jednoznačně řešitelné, tzn., aby nebylo více správných řešení pro jedno zadání. Vytváření zadání Sudoku se skládá ze dvou částí: První částí je vyplnění hrací plochy rozměru 9 x 9 (najít tzv. "budoucí řešení") a druhou částí je vynechání nepotřebných čísel. Proto i vytvořený algoritmus se bude skládat z těchto dvou částí. Kompletní mřížku lze opět vytvořit rekurzivně tak, že čísla dosazuji náhodně, aby bylo dodrženo základní pravidlo Sudoku.
- 57 -
Jak vypadá algoritmus pro první část, tj. vytvoření této mřížky, je vidět v následující části function s = zad(m,s) global delej if ~delej return end n=9; if ~exist('s') s = zeros([size(m),0]); end krok = min(find(m(:)==0)); if isempty(krok) s(:,:,size(s,3)+1) = m; delej = false; else [i,j] = ind2sub([n,n],krok); for k=randperm(9) radky = (ceil(i/3)-1)*3+1; sloupce = (ceil(j/3)-1)*3+1; bloky = m(radky:radky+2,sloupce:sloupce+2); if sum(m(i,:)==k)==0 && sum(m(:,j)==k)==0 && sum(bloky(:)==k)==0 m(i,j) = k; s = zad(m,s); end end end Jak je vidět, algoritmus je téměř totožný s algoritmem pro latinské čtverce vytvořené rekurzivním způsobem. Akorát zase s tím rozdílem, že je zde pevně daná velikost čtverce, jako n=9; a opět přidána navíc podmínka, která říká, že se mají čísla 1 až 9 navíc objevit i v bloku 3 x 3. Pro spuštění tohoto algoritmu potřebuji stejně jako u latinských čtverců zadat 4 vstupní hodnoty. Tyto vstupní hodnoty uložím do M- filu společně s druhou částí algoritmu pro vygenerování zadání. Nyní ukážu, jak tento algoritmus vypadá
- 58 -
global delej delej = true; m = zeros(9); s = zad(m); delej = true; while delej sold = s; j=ceil(81*rand); s(j)=0; v=Sudoku(s); kolik = size(v,3); if kolik~=1 delej = false; end end sold První čtyři řádky spouští předchozí algoritmus, úplně stejně jako u latinských čtverců. Pokud bychom spustili jen tyto čtyři první řádky, tak bychom dostali náhodně vygenerovanou mřížku označenou jako matici s. Tuto matici nepotřebujeme vidět, protože by nám prozradila správné řešení, proto ji neukazuji. Následující podmínka while delej sold = s; j=ceil(81*rand); s(j)=0; v=Sudoku(s); kolik = size(v,3); if kolik~=1 delej = false; end end vynechává náhodně čísla na pozici j v matici s. Do proměnné sold se postupně ukládá vždycky výchozí matice s, ze které vynechám náhodně číslo. Jakmile je náhodně vygenerována pozice j, nahradí se tato pozice v matici s nulou a zkouším, pomocí algoritmu na řešení Sudoku, který byl ukázán v předchozí kapitole 2.3, kolik má Sudoku správných řešení. Kolik je správných řešení, se zapisuje do proměnné kolik. A testuji, zda je jen jedno správné řešení nebo je jich více. Pokud je jen jedno správné řešení, tak se - 59 -
celý algoritmus vynechání čísla opakuje znovu tak dlouho, až je více správných řešení. Jakmile tato situace nastane. Zobrazí se nám proměnná sold, ve které je uložena matice s bez posledního vynechaného čísla, která měla jen jedno správné řešení. Tato matice se nám zobrazí a zastaví celý algoritmus. Pro spuštění celého algoritmu stačí napsat jen název M-filu, pod jakým máme uloženou druhou část. A téměř hned se nám vygeneruje náhodně nějaké zadání Sudoku. Toto zadání může vypadat například takto sold =
0
9
0
1
6
3
0
0
8
0
0
0
0
0
7
0
0
0
2
0
3
8
0
9
1
0
7
7
0
1
0
3
4
0
0
0
4
6
5
7
0
2
8
3
0
3
0
9
0
0
1
5
0
0
8
0
0
4
0
6
0
0
9
0
3
0
9
0
5
0
8
0
0
0
0
0
0
8
0
4
0
Vygenerování zadání tímto algoritmem trvá v průměru okolo 1.413 sekund a je velmi malá pravděpodobnost, že vygeneruje dvakrát za sebou stejné zadání. Protože jak jsem psala v kapitole 1.9.1 je 6,67 triliard možností, z kterých algoritmus vybírá správné řešení. Když máme vygenerované zadání, tak není žádný problém si ho zkontrolovat nebo podívat, jak má vypadat. K tomuto nám stačí využít předchozí algoritmus pro řešení Sudoku z předchozí kapitoly. Stačí tedy napsat pouze S = Sudoku(sold) a hned vidíme řešení. V našem případě správné řešení vypadá následovně
- 60 -
s =
5
9
7
1
6
3
4
2
8
6
1
8
2
4
7
9
5
3
2
4
3
8
5
9
1
6
7
7
8
1
5
3
4
6
9
2
4
6
5
7
9
2
8
3
1
3
2
9
6
8
1
5
7
4
8
5
2
4
7
6
3
1
9
1
3
4
9
2
5
7
8
6
9
7
6
3
1
8
2
4
5
Teď už nám nebrání nic v tom, abychom luštili každý den od rána do večera pořád jiné Sudoku.
- 61 -
Závěr Závěrem bych chtěla říct, že když jsem začala psát tuto práci, tak jsem si myslela, že hru Sudoku znám celkem dobře. Ale jak se ukázalo, tak tomu tak nebylo ani zdaleka. Historii této hry jsem téměř neznala, že existují další varianty také ne. Matematikou jsem se u této hry nikdy nezajímala, protože jsem si myslela, že existuje jen několik možností a k vyřešení postačí základní kombinatorika. Jak se ukázalo, tak moje myšlenky v tomto směru byly úplně špatné. Metody na řešení jsem znala jen ty základní, tak pro mě bylo velkým překvapením, že těchto metod existuje mnohem více, které dokážou ve spoustě případů řešení zjednodušit i zrychlit. Mým hlavním cílem této práce bylo naprogramovat v MATLABu algoritmus, který dokáže vyřešit jakékoliv zadání Sudoku a dále také vytvořit algoritmus, který dokáže náhodně generovat zadání. Tento cíl se mi podařilo splnit, i když ne vždy, byla cesta zrovna jednoduchá. Díky psaní této práce jsem se dozvěděla spoustu zajímavých informací o hře samotné, prohloubila si své znalosti o programu MATLAB a naučila jsem se v něm i programovat. Byla bych ráda, aby tato práce nebyla přínosem jen pro mě, ale i pro další studenty a zájemce o dané téma. Věřím, že znalosti, dovednosti a získané zkušenosti, které jsem získala touto diplomovou prací, využiji při dalším vzdělávání a v hledání nabídek práce.
- 62 -
Zdroje: [1]
Vražedná matematika Sudoku. Praha : Egmond ČR, s.r.o., 2006. 144 s.
[2]
Mistrovská Sudoku : Snadné i obtížné rébusy s 5 radami mistryně světa Jany Tylové. Praha : Kanzelsberger, a.s., 2006. 168 s.
[3]
Sudokuweb.cz : Magická hra, geniální hlavolam s jednoduchými pravidly [online]. 2008 [cit. 2009-10-17]. SUDOKU. Dostupné z WWW: http://sudokuweb.cz
[4]
Sudoku : Tisíce Sudoku jen pro Vás [online]. 2006 [cit. 2009-10-17]. SUDOKU. Dostupné z WWW: http://sudoku.hu.cz
[5]
Sudoku-hra.cz [online]. 2000 [cit. 2010-02-23]. Sudoku. Dostupné z WWW: http://www.sudoku-hra.cz/index.php
[6]
LHDelphi.wz.cz [online]. 2006 [cit. 2010-02-23]. Sudoku. Dostupné z WWW: http://sudoku-lh.wz.cz
[7]
Volny.cz [online]. 2008 [cit. 2010-10-17]. Jen takový malý příspěvek k řešení sudoku. Dostupné z WWW: http://www.volny.cz/jiven
[8]
THE PUZZLECLUB [online]. 2010 [cit. 2010-04-09]. Sudoku. Dostupné z WWW: http://www.thepuzzleclub.com/sudoku.php
[9]
Internetový magazín spisovatele, publicisty a badatele Jaroslava Chvátala [online]. 24.11.2005
[cit.
2010-10-30].
Matrix
2001.
Dostupné
z
WWW:
http://www.matrix-2001.cz/clanek-detail/898-fenomen-sudoku
[10]
Online-sudoku.cz [online]. [cit. 2010-10-30]. O Sudoku. Dostupné z WWW: http://www.online-sudoku.cz
- 63 -
[11]
Sudoku. In Wikipedia : the free encyclopedia [online]. St. Petersburg (Florida): Wikipedia Foundation, 1995, last modified on 22. 9. 2010 [cit. 2010-10-30]. Dostupné z WWW: http://cs.wikipedia.org/wiki/Sudoku
[12]
Prófův svět [online]. 12. 02. 2007 [cit. 2010-11-02]. Magické čtverce. Dostupné z WWW: http://profuvsvet.ic.cz/view.php?cisloclanku=2007020007
[13]
Magic square. In Wikipedia : the free encyclopedia [online]. St. Petersburg (Florida) : Wikipedia Foundation, 1995, last modified on 29.10.2010 [cit. 2010-1102]. Dostupné z WWW: http://en.wikipedia.org/wiki/Magic_square
[14]
FUCHS, Eduard. Magické čtverce aneb Od knihy I-ťing k internetové současnosti [online], 14.4.2004. 33 s. Diplomová práce. Masarykova univerzita. Dostupné z WWW: http://bart.math.muni.cz/~fuchs/Efuchs/historie_pdf/mactv.pdf
[15]
Latin square. In Wikipedia : the free encyclopedia [online]. St. Petersburg (Florida): Wikipedia Foundation, 1995, last modified on 12.9.2010 [cit. 2010-11-02]. Dostupné z WWW: http://en.wikipedia.org/wiki/Latin_square
[16]
FRAZER JARVIS, BERTRAM FELGENHAUER, Enumerating possible Sudoku grids [online]. June 20, 2005. 7 s. Oborová práce. Department of Computer Science TU Dresden, Germany & Department of Pure Mathematics University of Sheffield, U.K. Dostupné z WWW: http://www.afjarvis.staff.shef.ac.uk/sudoku/sudoku.pdf
[17]
Mathematics of Sudoku. In Wikipedia : the free encyclopedia [online]. St. Petersburg (Florida) : Wikipedia Foundation, 1995, last modified on 6.11.2010 [cit. 2010-11-17].
Dostupné
z
WWW:
http://en.wikipedia.org/wiki/Mathematics_of_Sudoku
[18]
Stanislava Kelemenová, Jana Míšaná, Jana Orsaghová. Algoritmizácia a naprogramovanie hry Sudoku [online]. 2006. 42 s. Študentská vedecká konferencia. Univerzita
Komenského.
Dostupné
z
http://cyril.fmph.uniba.sk/mffuk/studium/svk/AI/kelemenova.pdf - 64 -
WWW:
[19]
MATLAB - The Language Of Technical Computing [online]. 1994 [cit. 2011-02-03].
MathWorks.
Dostupné
z
WWW:
http://www.mathworks.com/matlabcentral/fileexchange/8083-matlab-sudoku-solver
[20]
The MathWorks, Inc. [online]. 1994 [cit. 2011-03-11]. MathWorks. Dostupné z WWW: http://www.mathworks.com/
[21]
Online Sudoku [online]. 2009 [cit. 2011-03-25]. SUDOKU ONLINE. Dostupné z WWW: http://www.sudoku-online.mojeip.cz/
[22]
MATLAB. In Wikipedia : the free encyclopedia [online]. St. Petersburg (Florida) : Wikipedia Foundation, 1995, last modified on 17. března 2011 [cit. 2011-03-25]. Dostupné z WWW: http://cs.wikipedia.org/wiki/MATLAB.
[23]
Latin Squares: Leonhard Euler, Quasigroup, Latin Square, Mathematics of Sudoku, Graeco-Latin Square, R. C. Bose, Circulant Matrix, Books LLC, 2010
[24]
Narendra Jussien: A to Z of Sudoku. Ecole des Mines de Nantes, Francie 2007
[25]
Seymour S Block, Santiago A Tavares: Before Sudoku: The World of Magic Squares. Oxford Univ., 2009
[26]
Wei-Meng Lee:Programming Sudoku (Technology in Action).Apress, 2006
- 65 -
