INTERAKTIVNÍ PRŮVODCE · LISTOPAD 2026

Sudoku

Od prvního singlu
po řetězy a algoritmy

Na pozadí řeší počítač sudoku tak jako člověk. V každém kroku hledá nejjednodušší techniku, která ještě něco přinese – od skrytého singlu po Swordfish a XY-řetěz – a pojmenuje ji. Modře jsou pole, ze kterých závěr plyne, oranžově zapsaná číslice nebo škrtnutí kandidáti. Všechny techniky vysvětlují kapitoly 2 až 8 a stejný řešitel hodnotí obtížnost úloh v kapitole 12.

krok řešení–

technika–

vyplněno–

kandidátů v mřížce–

Začít 🎮 Hrát ve 3DJak sudoku řeší počítač

Úvodem

Jak průvodce používat

Sudoku má jediné pravidlo, které se vejde do jedné věty, a přesto z něj vyrostla celá řemeslná dovednost s vlastním slovníkem: singly, zamčení kandidáti, ryby, křídla a řetězy. Průvodce vede od pravidel a prvního skenování přes poznámky tužkou a pokročilé techniky až k variantám, matematice mřížek a k tomu, jak sudoku řeší a vyrábí počítač. Je pro hráče, kteří si občas zahrají a chtějí hrát lépe, pro rodiče a děti i pro studenty matematiky a informatiky, které zajímá, co je pod kapotou.

🧩

Tři patra každé kapitoly. Nahoře krátké vysvětlení a laboratoř nebo minihra na vlastní mřížce, kde si věc vyzkoušíte klepáním na pole. Pod ní dvě mise za XP. Dole rozbalovací teorie pro ty, kdo chtějí jít do hloubky: přesné definice, důkazy, proč technika funguje, řešené příklady a procvičení s řešením. Teorie bývá o úroveň náročnější než úvod kapitoly. Barevná tečka v obsahu ukazuje úroveň. Postup se ukládá jen ve vašem prohlížeči.

Hned za úvodem najdete sekci Hrajte sudoku ve 3D: kostky čísel na dřevěné desce, pět obtížností podle technik z tohoto průvodce a trenér, který ukáže další logický krok a odkáže na kapitolu, kde se technika vykládá.

Mapa průvodce

**Tab. 0.1**Kapitoly, úroveň a co se v nich naučíte
Kapitola	Úroveň	Co se naučíte
1 Pravidla, mřížka a historie	základy	řádek, sloupec, blok, jednotka, sousedé, kandidát, značení polí; od Eulerových latinských čtverců po světovou vlnu 2005
2 Skenování a singly	základy	křížové skenování, skrytý singl, nahý singl, poslední volné pole, v jakém pořadí hledat
3 Kandidáti a poznámky tužkou	základy	kdy a jak psát kandidáty, eliminace po zápisu, rohové a středové poznámky, chyby z nepozornosti a jak je najít
4 Zamčení kandidáti	základy	ukazující (blok → řádek či sloupec) a nárokující (řádek či sloupec → blok), proč fungují
5 Dvojice, trojice a čtveřice	pokročilí	nahé a skryté podmnožiny, důkaz, dualita nahých a skrytých podmnožin, proč stačí čtveřice
6 Ryby	pokročilí	X-wing, Swordfish, Jellyfish, základní a krycí linie, ryby s ploutví v kostce
7 Křídla	pokročilí	XY-wing, XYZ-wing a W-wing krok za krokem, pole se dvěma kandidáty
8 Barvení a řetězy	pokročilí	silné a slabé vazby, jednoduché barvení, X-řetězy a X-cykly, XY-řetězy, AIC v kostce, kde končí logika a začíná hádání
9 Killer a další varianty	mistr a věda	klece a kombinace součtů, pravidlo 45, Sudoku X, Jigsaw, Windoku, mini 6 × 6 a 4 × 4
10 Matematika sudoku	mistr a věda	latinské čtverce, počet mřížek 9 × 9, podstatně různé mřížky, symetrie, minimum 17 vodítek, barvení grafu
11 Jak sudoku řeší počítač	mistr a věda	backtracking, MRV, propagace omezení, exact cover a Algoritmus X, převod na SAT, NP-úplnost
12 Tvorba úloh, obtížnost a soutěže	mistr a věda	generování s jediným řešením, minimální úlohy, symetrie vodítek, hodnocení obtížnosti, mistrovství světa, trénink rychlosti

Co budete potřebovat

Tužku a papír, nebo jen prst na displeji. Všechny úlohy z průvodce jsou v laboratořích, takže tisknout nic nemusíte. Pro první část stačí počítat do devíti. Od kapitoly 9 se hodí sčítání a kombinační čísla, v kapitolách 10 a 11 trocha kombinatoriky a algoritmického myšlení – co je potřeba, průvodce vysvětlí na místě.

Navazující látku najdete v sousedních průvodcích: jiný myšlenkový sport a stromy variant v průvodci Šachy, kombinatoriku, permutace a grupy symetrií v průvodci Matematika, pravděpodobnost a práci se vzorkem v průvodci Statistika a modely, důkaz sporem a výrokovou logiku (základ převodu na SAT) v průvodci Logika a kritické myšlení a algoritmy, složitost a umělou inteligenci obecně v průvodci Informatika.

Značení a předpoklady

Pole se v celém průvodci značí ř3s7 = 3. řádek shora, 7. sloupec zleva. Bloky se číslují 1 až 9 po řádcích, tedy 1. blok vlevo nahoře, 5. blok uprostřed a 9. blok vpravo dole. Laboratoře, hero i 3D hra používají řešitel, který v každém kroku zkouší techniky od nejjednodušší.

**Tab. 0.2**Úrovně obtížnosti v průvodci a ve 3D hře
Úroveň	Nejtěžší potřebná technika	Kapitola
1	skrytý singl v bloku, nahý singl	2
2	skrytý singl v řádku nebo sloupci	2
3	zamčení kandidáti, nahá a skrytá dvojice	4, 5
4	trojice a čtveřice, X-wing, XY-wing, XYZ-wing, W-wing	5, 6, 7
5	Swordfish, Jellyfish, jednoduché barvení, X-řetěz, XY-řetěz	6, 8
mimo škálu	úloha potřebuje techniku nad rámec průvodce	8, 11

Statistiky „ve vzorku“ se týkají 6 000 úloh, které generátor z kapitoly 12 vyrobil s pevnými semínky (středová symetrie, jediné řešení, z úlohy už nejde ubrat žádnou souměrnou dvojici vodítek) a řešitel průvodce ohodnotil. Všechny úlohy v laboratořích mají jediné řešení.

Čtyři druhy rámečků

Příklad Řešený krok nebo výpočet

Konkrétní situace z mřížky nebo výpočet, který si můžete ověřit v laboratoři.

Z historie

Jak hra vznikla, kdo ji pojmenoval, co dokázali matematici a jak se hraje na mistrovstvích.

Mistrovská pomůcka

Rychlé pravidlo, zkratka nebo návyk, který používají zkušení řešitelé.

Pozor

Častá chyba, mýtus nebo past, do které se snadno spadne.

Studijní materiál o hře. Hrajte pro radost a s mírou – bez sázek a peněz. Průvodce nejmenuje ani nedoporučuje aplikace či programy; historické údaje, výsledky soutěží a matematické výsledky mají v příloze C zdroj a datum ověření (7. 11. 2026). Úlohy, statistiky a počty v laboratořích jsou spočítané přímo v prohlížeči nebo skriptem nad stejným kódem.

Rozsahem odpovídá: matematika – kombinatorika (permutace, kombinační čísla, počítání s grupami symetrií, Burnsideovo lemma v kostce) a pravděpodobnost na úrovni úvodních vysokoškolských kurzů; informatika – úvod do umělé inteligence a algoritmů prohledávání (backtracking, heuristiky, propagace omezení, exact cover, převod na SAT) a pojem NP-úplnosti; pravidla – klasické sudoku a varianty podle pramenů uvedených v příloze C.

Hrajte

Sudoku ve 3D

📲 Hrát jako aplikace – samostatná stránka hry: nainstalujete si ji do telefonu nebo počítače a hrajete i bez připojení.

Řešte sudoku na dřevěné desce, kde je každá číslice kostka. Na výběr je Klasické 9 × 9, Denní výzva (v daný den stejné zadání pro všechny), Killer s klecemi a součty, Sudoku X s diagonálami a Mini 6 × 6 pro děti. Obtížnost 1 až 5 odpovídá technikám z průvodce: 1 jsou singly z kapitoly 2, 2 skryté singly a méně vodítek, 3 zamčení kandidáti z kapitoly 4 a dvojice z kapitoly 5, 4 trojice, X-wing z kapitoly 6 a XY-wing z kapitoly 7, 5 Swordfish, barvení a řetězy z kapitoly 8. Ovládání v kostce: klepněte na pole a pak na číslo v číselníku; na klávesnici šipky, 1–9, Delete, N přepne poznámky a Z vrátí tah.

Jak to funguje: každá úloha má jediné řešení a jde vyřešit logikou bez hádání – ověřuje to stejný druh řešitele, jaký popisuje kapitola 12. Nápověda trenéra ukáže další logický krok, pojmenuje techniku a odkáže na kapitolu, kde se vykládá. Poznámky tužkou můžete psát ručně nebo nechat doplnit automaticky (kapitola 3), tahy jde vracet i opakovat. Za rychlé vyřešení bez nápovědy a bez chyby jsou tři hvězdy. Rekordy, hvězdy a série denních výzev se ukládají jen ve vašem prohlížeči. Po vyřešení se kostky v otočné vlně přetočí a složí obrázek.

Část IZáklady

Pravidla, mřížka a historiezáklady

Mřížku 9 × 9 doplňte číslicemi 1 až 9 tak, aby se žádná číslice neopakovala v řádku, ve sloupci ani v bloku 3 × 3. To je celé pravidlo. Všechno ostatní – singly, kandidáti, ryby i řetězy – jsou jen důsledky této jedné věty. Kapitola zavádí slovník, se kterým pracuje celý průvodce, a ukazuje, jak hra vznikla.

🔢

Sudoku funguje jako zasedací pořádek, kde se nikdo nesmí potkat se svým dvojníkem: v každé řadě židlí, v každém sloupci a u každého stolu 3 × 3 sedí od každé číslice právě jedna. Kdo se na pole naučí dívat očima jeho dvaceti sousedů, vidí, co do něj patří a co ne.

Obr. 1.1 Tři druhy jednotek: 3. řádek (modře), 7. sloupec (zeleně) a 7. blok (oranžově). V každé jednotce je každá číslice 1–9 právě jednou. Čísla nad mřížkou a vlevo jsou čísla sloupců a řádků.

Průzkumník mřížky

Klepněte na libovolné pole. Laboratoř podbarví jeho řádek, sloupec, blok nebo všech 20 sousedů a spočítá, kolik číslic už sousedé „zabrali“. V režimu kandidátů vidíte, co do prázdných polí ještě může přijít.

LABORATOŘ

Model: úloha úrovně 1 s 30 vodítky a jediným řešením. Kandidáti pole jsou číslice, které nemá žádný z jeho 20 sousedů; laboratoř zatím nepoužívá žádnou techniku, jen pravidlo.

Minihra: Kde je chyba?

Laboratoř ukáže rozpracovanou mřížku. Někdy je v ní číslice, která porušuje pravidla, někdy ne. Klepněte na pole s chybou, nebo stiskněte „Bez chyby“. Správnost se ukáže až po odpovědi; kolo má šest úkolů a za aspoň pět správných získáte 15 XP.

MINIHRA

0 / 6

+Teorie: pravidla, jednotky, sousedé, kandidáti a historie

1.1Pravidla

Klasické sudoku je mřížka 9 × 9 = 81 polí rozdělená tlustšími čarami na devět bloků 3 × 3. Některá pole jsou předem vyplněná – to jsou vodítka. Úkolem je doplnit do prázdných polí číslice 1 až 9 tak, aby každý řádek, každý sloupec a každý blok obsahoval každou číslici právě jednou.sudoku, grid, cell, box, clue (given)

Číslice tu nejsou čísla: nic se nesčítá ani nenásobí, šlo by hrát s písmeny nebo barvami. Důležité je jen to, že je jich devět a že jsou navzájem různé. (Varianta Killer z kapitoly 9 je výjimka, tam se sčítá.)

Pozor

„Žádná číslice se neopakuje“ a „každá číslice je jednou“ znamená v jednotce o devíti polích totéž – jenže jen pro vyplněnou jednotku. V rozpracované mřížce chybějící číslice nevadí, vadí jen opakování. Proto se chyba často pozná až pozdě: špatná číslice sama o sobě žádné pravidlo neporuší, dokud ji „nedožene“ správná.

1.2Jednotky, pásy a štoky

Řádek, sloupec a blok mají společné jméno jednotka: je to devítice polí, v níž je každá číslice právě jednou. Klasické sudoku má 9 řádků, 9 sloupců a 9 bloků, tedy 27 jednotek. Každé pole leží právě ve třech z nich.unit (house), row, column, box

Tři bloky vedle sebe tvoří pás (řádky 1–3, 4–6 a 7–9), tři bloky nad sebou štok (sloupce 1–3, 4–6 a 7–9). Pásy a štoky se hodí při skenování (kapitola 2) a jsou to i jednotky symetrií v kapitole 10: řádky se smějí prohazovat jen uvnitř pásu.band, stack

**Tab. 1.1**Základní pojmy a počty v klasickém sudoku 9 × 9
Pojem	Co to je	Počet
pole	jeden čtvereček mřížky, značí se ř3s7	81
jednotka	řádek, sloupec nebo blok	27
pás / štok	tři bloky vedle sebe / nad sebou	3 / 3
sousedé pole	pole, která s ním sdílejí jednotku	20
dvojice sousedních polí	81 · 20 / 2	810
výskyty každé číslice	jednou v každém z 9 řádků	9
součet vyplněné mřížky	9 · (1 + 2 + … + 9) = 9 · 45	405

1.3Sousedé a kandidáti

Sousedé pole jsou všechna pole, se kterými sdílí aspoň jednu jednotku: 8 dalších v řádku, 8 ve sloupci a 4 v bloku, které ještě nebyly započteny. Dohromady 20 – pro každé pole stejně, v rohu i ve středu.peers

Počet sousedů\[ |P(p)| = \underbrace{8}_{\text{řádek}} + \underbrace{8}_{\text{sloupec}} + \underbrace{(9 - 1 - 2 - 2)}_{\text{zbytek bloku}} = 20 \]

Kandidát prázdného pole je číslice, kterou nemá žádný z jeho sousedů. Pokud mají sousedé dohromady k různých číslic, má pole 9 − k kandidátů. Pozor, počítají se různé číslice: stejná číslice ve sloupci i v bloku ubere jen jednoho kandidáta.candidate

Obr. 1.2 Pole ř5s5 (oranžově) a jeho 20 sousedů (modře). Dvanáct sousedů je vyplněných, ale obsahují jen šest různých číslic (1, 2, 3, 6, 8 a 9), takže pole má tři kandidáty: 4, 5 a 7.

Příklad Jediný kandidát

V úloze z obr. 1.2 má pole ř5s9 osm vyplněných sousedů a každý má jinou číslici. Chybí jen pětka, takže ř5s9 = 5. Takovému poli se říká nahý singl a v kapitole 2 je to jedna ze dvou základních technik. Pole ř5s5 vedle má sousedů vyplněných víc (dvanáct), a přesto tři kandidáty – rozhoduje počet různých číslic, ne počet vyplněných polí.

1.4Jediné řešení

Správně zadaná úloha má právě jedno řešení. To není součást pravidla „neopakovat“, ale dohoda autorů a soutěží: úloha s více řešeními se považuje za vadnou, protože ji nejde vyřešit úvahou, jen tipnout. Kapitola 10 ukazuje, že k jedinému řešení je potřeba nejméně 17 vodítek, a kapitola 12, jak autor jedinečnost zaručí.unique solution, well-posed puzzle

Mistrovská pomůcka

Číslice pište jen tehdy, když víte, proč tam patří. Když si důvod umíte říct jednou větou („v 5. bloku nemá sedmička jiné místo“), nedělá se chyba ani pod časovým tlakem. Tip „vypadá to dobře“ je nejčastější začátek zamotané mřížky.

1.5Historie

Latinský čtverec je tabulka n × n, ve které je každý symbol jednou v každém řádku a sloupci – sudoku bez bloků. Zkoumal je Leonhard Euler v pojednání Recherches sur une nouvelle espèce de quarrés magiques (vyšlo 1782), kde rozebíral i úlohu o 36 důstojnících: šest pluků po šesti hodnostech postavit do čtverce tak, aby se v žádném řádku ani sloupci neopakoval pluk ani hodnost.Latin square

Francouzský deník Le Siècle otiskl 19. 11. 1892 číselnou hádanku na mřížce 9 × 9 odvozenou od magického čtverce a konkurenční La France 6. 7. 1895 verzi, která už byla skoro moderním sudoku – číslice 1 až 9 v každém řádku a sloupci a skryté bloky 3 × 3, jen nevyznačené. Moderní podobu s vyznačenými bloky zveřejnilo americké nakladatelství Dell Magazines v roce 1979 pod jménem Number Place; autorství se připisuje architektovi Howardu Garnsovi.

V dubnu 1984 hru převzal japonský vydavatel hádanek Nikoli pod názvem „Sūji wa dokushin ni kagiru“ (zhruba „číslice musí být samotné“), který se zkrátil na sudoku. Zakladatel Nikoli Maki Kadži (1951–2021) se proto někdy nazývá otcem sudoku. Japonští autoři přidali dvě tradice, které platí dodnes: vodítka rozmístěná souměrně a úlohy řešitelné úvahou. Světovou vlnu odstartoval londýnský deník The Times, který 12. 11. 2004 otiskl úlohy Novozélanďana Wayna Goulda; během roku 2005 se sudoku objevilo v novinách po celém světě a v roce 2006 se konalo první mistrovství světa.

Obr. 1.3 Od latinských čtverců k mistrovství světa. Rok 1984 (oranžově) dal hře jméno; rok 2012 je datum zveřejnění důkazu, že 17 vodítek je minimum (kapitola 10).

Z historie

První mistrovství světa v sudoku se konalo 10.–11. 3. 2006 v italské Lucce a vyhrála ho Češka Jana Tylová. Česká stopa v soutěžním sudoku je výrazná i později: Praha hostila mistrovství světa v letech 2007 a 2018 a české družstvo vyhrálo soutěž týmů v letech 2008, 2016 a 2022 (kapitola 12).

1.6Procvičení

Kolik společných sousedů mají pole ř1s1 a ř1s2?

Leží ve stejném řádku i bloku. Společní sousedé: zbylých 7 polí 1. řádku a 6 polí 1. bloku mimo 1. řádek, celkem 13.

Kolik společných sousedů mají pole ř1s1 a ř5s5? A pole ř1s1 a ř2s2?

ř1s1 a ř5s5 nesdílejí žádnou jednotku; společní sousedé jsou jen dva „rohy obdélníku“ ř1s5 a ř5s1, tedy 2. ř1s1 a ř2s2 leží ve stejném bloku, ale v různých řádcích a sloupcích: společných je zbylých 7 polí bloku (žádné pole mimo blok nevidí obě).

Jaký je součet všech číslic ve vyřešeném sudoku?

Každý řádek obsahuje 1 až 9, tedy 45. Devět řádků: 9 · 45 = 405. Tenhle součet se hodí v Killer sudoku (kapitola 9) jako kontrola, že součty klecí sedí.

Pole má 12 vyplněných sousedů. Kolik kandidátů může mít nejméně a kolik nejvíc?

Nejméně 1: mezi dvanácti číslicemi může být osm různých a pole je nahý singl (devět různých by znamenalo spor). Nejvíc 5: každá číslice se mezi sousedy objeví nejvýš třikrát (jednou v řádku, jednou ve sloupci, jednou v bloku), takže dvanáct vyplněných sousedů nese aspoň 12 / 3 = 4 různé číslice a zbude nejvýš 9 − 4 = 5 kandidátů. Mez je dosažitelná – skript ji našel hned v první náhodné mřížce (pole ř1s1, číslice 2, 3, 6 a 7, každá třikrát).

Kolik jednotek obsahuje současně pole ř4s4 a ř4s6? A kolik pole ř4s4 a ř6s4?

ř4s4 a ř4s6 leží ve 4. řádku a v 5. bloku: dvě společné jednotky. ř4s4 a ř6s4 leží ve 4. sloupci a také v 5. bloku: rovněž dvě. Dvě různá pole nemohou sdílet tři jednotky – to by musela ležet ve stejném řádku i sloupci, a byla by tedy totožná.

Co si odnést

Jedno pravidlo: v každém z 27 řádků, sloupců a bloků je každá číslice 1–9 právě jednou.
Každé pole má 20 sousedů; kandidáti jsou číslice, které žádný soused nemá – počítají se různé číslice.
Hra vychází z latinských čtverců, jako Number Place vyšla v USA 1979, jméno sudoku jí dal Nikoli 1984 a svět dobyla v letech 2004–2005.

Část IZáklady

Skenování a singlyzáklady

Dvě techniky vyřeší většinu novinových sudoku. Skrytý singl: číslice má v řádku, sloupci nebo bloku jediné možné místo. Nahý singl: pole má jedinou možnou číslici. První se hledá skenováním číslic, druhý prohlížením polí. Kdo je umí najít rychle a spolehlivě, vyřeší lehké úlohy bez jediné poznámky.

🔦

Skenování je jako hledání volného místa v kině, kde už sedí vaši známí: kamkoli by sedla další sedmička, uviděla by jinou sedmičku v řadě nebo ve sloupci. Když v sále zbude jediné místo, kde žádnou jinou sedmičku nevidí, je to její místo.

Skener singlů

Vyberte číslici: laboratoř vyznačí její stávající výskyty, protáhne z nich čáry řádky a sloupci a zeleně podbarví skryté singly – pole, kde má číslice v některé jednotce jediné místo. V režimu nahých singlů ukáže pole s jediným kandidátem. „Zapsat nalezené“ je doplní a ukáže, co se tím otevřelo.

LABORATOŘ

Model: úlohy A a B jsou úrovně 1 (30 a 31 vodítek), úloha C úrovně 2 (29 vodítek). Modré body jsou pole, kde vybraná číslice ještě může stát, šedě podbarvená pole ji mít nemohou. Opakovaným skenováním a zápisem vyřešíte A i B celé.

Minihra: Najdi singl

Najděte pole, které jde vyplnit s jistotou, klepněte na něj a pak na číslici. Laboratoř kandidáty neukazuje – skenujte sami. Uznává se jen jistý zápis (skrytý nebo nahý singl), ne šťastný tip. Kolo má osm pokusů a za aspoň šest správných získáte 15 XP.

MINIHRA

0 / 8

+Teorie: skrytý a nahý singl, křížové skenování a pořadí hledání

2.1Skrytý singl

Označme K(p) množinu kandidátů pole p. Číslice d je v jednotce U skrytý singl, pokud v U ještě nestojí a může v ní stát na jediném poli. Protože v jednotce musí být, stojí právě tam – bez ohledu na to, kolik dalších kandidátů to pole má. Proto „skrytý“: číslici v poli mezi ostatními kandidáty nevidíte, dokud se nepodíváte na celou jednotku.hidden single

Skrytý singl\[ d \notin U \ \wedge\ \big|\{\,p \in U : d \in K(p)\,\}\big| = 1 \ \Rightarrow\ \text{to jediné pole je } d \]

2.2Křížové skenování

Skrytý singl v bloku se hledá křížovým skenováním: vyberete číslici, podíváte se na řádky a sloupce, ve kterých už stojí, a v duchu je „proškrtáte“. Pole bloku, kterými žádná čára neprochází a která jsou prázdná, jsou jediná možná místa. Zbude-li jediné, je to skrytý singl.cross-hatching, scanning

Obr. 2.1 Křížové skenování jedničky v úloze A. Čtyři jedničky (oranžové kroužky) proškrtají svými řádky a sloupci osm z devíti polí prázdného 5. bloku. Zbude jediné pole ř4s4 (zeleně): skrytý singl, i když je blok zcela prázdný. Modré body ukazují, kde všude jednička ještě může stát.

Mistrovská pomůcka

Skenujte číslice podle toho, kolikrát už v mřížce jsou – od nejčastější. Číslice, která stojí sedmkrát, má volná jen dvě místa a skoro vždy jedno z nich hned prozradí. Projeďte pak bloky v pásu najednou: dvě stejné číslice v sousedních blocích pásu určují řádek, ve kterém musí být třetí.

2.3Nahý singl

Nahý singl je opačný pohled: pole, jehož sousedé obsahují osm různých číslic, má jediného kandidáta – tu devátou. Hledá se prohlížením polí, nejlépe v řádcích, sloupcích a blocích, kde už je hodně vyplněno.naked single, sole candidate

Obr. 2.2 Nahý singl v úloze B. Pole ř4s3 má deset vyplněných sousedů (modře) s číslicemi 2, 3, 4, 5, 6, 7, 8 a 9. Zbývá jediný kandidát, 1. V žádné z jeho jednotek přitom jednička není skrytý singl – pomůže jen pohled na pole.

Speciální případ obou technik je poslední volné pole: jednotka, ve které zbývá jediné prázdné pole. Chybějící číslice je jasná na první pohled a zkušení řešitelé taková pole vyplňují jako první.full house

Pozor

Nahý singl se snadno „najde“ chybně: přehlédnete jednoho souseda a pole má zdánlivě jediného kandidáta. Než číslici zapíšete, projděte ještě jednou řádek, sloupec i blok. U skrytého singlu je častá chyba opačná – zapomenete, že číslice v jednotce už stojí, a „najdete“ jí druhé místo.

2.4Kam až singly stačí

Řešitel průvodce zkouší v každém kroku nejdřív skrytý singl v bloku a nahý singl, potom skrytý singl v řádku a sloupci a teprve pak dražší techniky. Ve vzorku 6 000 vygenerovaných úloh vypadá výsledek takto:

**Tab. 2.1**Kolik úloh vyřeší jen singly (vzorek 6 000 úloh se středovou symetrií)
Nejtěžší potřebná technika	Úloh	Podíl	Kumulativně
úroveň 1: skrytý singl v bloku, nahý singl	2 608	43,5 %	43,5 %
úroveň 2: navíc skrytý singl v řádku či sloupci	1 388	23,1 %	66,6 %
úroveň 3 a výš: potřeba kandidátů a dalších technik	2 004	33,4 %	100 %

V úlohách úrovně 1 tvoří skryté singly v blocích 94,1 % všech kroků; nahých singlů je málo, ale bez nich by se řešitel často zasekl. Nahý singl použilo 85,5 % úloh vzorku, skrytý singl v řádku nebo sloupci 50,7 %.

Příklad Úloha A na začátku

V úloze A z laboratoře najde skenování na začátku deset skrytých singlů: pětka tři, čtyřka a devítka po dvou, jednička, dvojka a sedmička po jednom; trojka, šestka a osmička žádný. Nahé singly jsou na začátku dva. Po jejich zapsání se otevřou další – úloha úrovně 1 se takhle „rozsype“ až do konce.

2.5Procvičení

V úloze A z laboratoře má pětka na začátku tři skryté singly. Kolik nahých singlů má na začátku úloha B?

Osm. Ověřte v laboratoři: úloha B, režim „nahé singly“. Úloha B má i víc vodítek (31), ale hlavně jsou rozmístěná tak, že mnoho polí „vidí“ osm různých číslic.

Jak se liší skrytý singl v bloku od skrytého singlu v řádku?

Logicky ničím – v obou případech má číslice v jednotce jediné místo. Liší se jen tím, jak se hledají: v bloku stačí křížové skenování, v řádku musíte pro každé prázdné pole řádku ověřit sloupec i blok. Proto je skrytý singl v řádku nebo sloupci v průvodci úroveň 2.

V bloku zbývají tři prázdná pole a jednička musí být v jednom z nich. Řádky dvou z těchto polí už jedničku mají. Co platí?

Jednička stojí ve třetím poli – je to skrytý singl v bloku. Druhé dvě pole jedničku mít nemohou, protože ji vidí v řádku.

Pole má v řádku číslice 1, 4, 7, ve sloupci 2, 4, 8 a v bloku 3, 7, 9. Je to nahý singl?

Různé číslice sousedů: 1, 2, 3, 4, 7, 8, 9 – sedm. Chybí 5 a 6, pole má dva kandidáty, takže nahý singl to není. Pomoci může skrytý singl: má-li například šestka v řádku jiné místo, a pětka ne, je pole 5.

Kolik procent úloh ve vzorku vyřeší jen singly všech druhů (úrovně 1 a 2)?

(2 608 + 1 388) / 6 000 = 3 996 / 6 000 = 66,6 %. Zbylá třetina potřebuje kandidáty a techniky z kapitol 4 až 8.

Co si odnést

Skrytý singl: číslice má v jednotce jediné místo. Nahý singl: pole má jedinou číslici.
Křížové skenování: vyberte číslici, proškrtejte její řádky a sloupce a hledejte blok s jediným volným místem.
Samotné singly vyřeší ve vzorku dvě třetiny úloh; skenujte od nejčastější číslice.

Část IZáklady

Kandidáti a poznámky tužkouzáklady

Když singly dojdou, nastupuje tužka. Do prázdných polí se drobně zapisují kandidáti – číslice, které tam ještě mohou být – a po každém zápisu se škrtají. Poznámky jsou pracovní plocha všech technik od kapitoly 4 dál. Kdo je vede pečlivě, vidí vzory, kdo je vede ledabyle, dělá chyby, které se projeví až o dvacet tahů později.

✏️

Poznámky tužkou jsou jako seznam podezřelých v detektivce. Na začátku jsou podezřelí všichni, koho nikdo neviděl jinde. Každé alibi někoho škrtne a když zbude jediný, případ je vyřešen. Detektiv, který zapomene škrtnout podezřelého s alibi, obviní nevinného.

Tužka a guma

Vyřešte úlohu s poznámkami. Klepněte na pole a pak na číslici; v režimu poznámek se číslice zapisují drobně jako kandidáti. „Doplnit kandidáty“ je vyplní automaticky, „Zkontrolovat“ označí chyby, „Nápověda“ ukáže další logický krok a pojmenuje techniku.

LABORATOŘ

po zápisu škrtat u sousedů

Model: lehká úloha (31 vodítek) jde celá singly, úloha úrovně 3 (28 vodítek) potřebuje i zamčené kandidáty a skrytou dvojici. Kontrola porovnává s jediným řešením úlohy: červená číslice je v konfliktu s jinou, červený rámeček je číslice bez konfliktu, ale špatně, červený podklad je pole, jehož poznámky neobsahují správnou číslici. Za vyřešenou úlohu získáte 15 XP.

+Teorie: kdy a jak psát kandidáty, eliminace a chyby z nepozornosti

3.1Kandidáti

Kandidát pole p je číslice, která v p zatím může stát. Na začátku jsou to číslice, které nemá žádný z 20 sousedů; techniky z dalších kapitol pak odebírají i takové kandidáty, kterým sousedé nebrání, ale jiná úvaha ano. Kandidáti, které už nejde škrtnout ničím, tvoří v každé chvíli horní odhad toho, co do pole může přijít – správná číslice mezi nimi musí být vždy.candidate, pencil mark

Počáteční kandidáti a úbytek po zápisu\[ K(p) = \{1,\dots,9\} \setminus \{\,g(q) : q \in P(p)\,\}, \qquad \Delta = |K(p)| + \big|\{\,q \in P(p) : d \in K(q)\,\}\big| \]

Druhý vzorec říká, o kolik kandidátů v mřížce ubude, když do pole p zapíšete číslici d: zmizí všichni kandidáti pole p a číslice d u všech sousedů, kteří ji měli.

Obr. 3.1 Úloha úrovně 3 z laboratoře se všemi kandidáty. Na 53 prázdných polí připadá 182 kandidátů, průměrně 3,43 na pole. Dva kandidáty má osm polí, tři 24 polí, čtyři 12 polí, pět osm polí a šest jediné pole; žádné nemá jediného kandidáta, takže nahé singly na začátku nejsou.

3.2Kdy a jak je psát

Psát všechny kandidáty hned na začátku je zbytečná práce: většinu z nich škrtnou singly, které se najdou i bez tužky. Osvědčený postup má tři fáze.

Skenování bez tužky – singly z kapitoly 2, dokud přibývají.
Rohové poznámky – číslici zapíšete do rohu pole jen tehdy, když má v bloku nejvýš dvě místa. Tomuto stylu se v soutěžním prostředí říká Snyderova notace (podle amerického mistra světa Thomase Snydera). Dvojice rohových poznámek jsou zároveň silné vazby z kapitoly 8.Snyder notation, corner marks
Úplní kandidáti – teprve když se zaseknete, doplníte do středu polí všechny kandidáty a hledáte vzory: zamčené kandidáty, dvojice, ryby, křídla.centre marks, full candidates

Mistrovská pomůcka

Po každém zápisu číslice hned škrtněte stejnou číslici ve všech 20 sousedech – řádek, sloupec, blok, v tomto pořadí. Zvyk „zapsat a hned škrtat“ zabrání většině chyb. V laboratoři ho dělá zaškrtávátko „po zápisu škrtat u sousedů“; zkuste ho vypnout a uvidíte, jak rychle poznámky přestanou odpovídat mřížce.

3.3Jak kandidáti ubývají

Při řešení klesají dvě čísla: prázdná pole a kandidáti. Zápis číslice ubere jedno prázdné pole a obvykle několik kandidátů, škrt podle techniky ubere kandidáty, ale žádné pole. Proto kandidátů ubývá zpočátku rychleji – v úloze z obr. 3.1 za prvních deset kroků ze 182 na 135 (o 47), zatímco prázdných polí jen z 53 na 46.

Obr. 3.2 Řešení úlohy z obr. 3.1 krok za krokem: 56 kroků, z toho 48 skrytých singlů v bloku, 3 skryté singly v řádku nebo sloupci, 2 nahé singly, 2 zamčení kandidáti a 1 skrytá dvojice. Kde klesá jen modrá křivka a oranžová stojí, jde o škrty bez zápisu (6. až 8. krok).

3.4Chyby z nepozornosti

Většina „neřešitelných“ úloh je ve skutečnosti řešitelná – jen se v mřížce schovává chyba. Nejčastější druhy:

**Tab. 3.1**Typické chyby a jak je odhalit
Chyba	Co se stane	Kontrola
přehlédnutý soused	do pole se zapíše číslice, kterou už má řádek, sloupec nebo blok	před zápisem projít všechny tři jednotky
chybějící škrt	poznámky obsahují kandidáta, který tam být nemůže; falešný „nahý singl“ se neobjeví, ale technika najde nesmysl	po zápisu škrtat u všech 20 sousedů
škrtnutá správná číslice	poznámky přijdou o správného kandidáta; časem vznikne pole bez kandidátů	každý škrt umět zdůvodnit jednou větou
přepsání vodítka	vodítko omylem změníte nebo přehlédnete	vodítka psát (nebo zobrazovat) jinak než vlastní číslice
tip	číslice „vypadá dobře“, ale nebyla dokázaná	psát jen to, co plyne z techniky

Pozor

Chyba se projeví až pozdě a daleko od místa, kde vznikla – typicky jako pole bez kandidátů nebo dvě stejné číslice v jednotce. V tu chvíli nemá smysl opravovat jen poslední zápis: buď se vrátíte k poslední jisté mřížce, nebo začnete znovu. Proto se v soutěžích píše tužkou a s gumou a v laboratoři i ve 3D hře je tlačítko Zpět.

3.5Ruční, nebo automatické poznámky?

Automatické doplnění kandidátů ušetří čas, ale ochudí o trénink: kdo kandidáty nikdy nepočítá sám, nevidí, proč tam jsou, a hůř hledá vzory. Dobrý kompromis je skenovat a psát rohové poznámky ručně a automatiku zapnout až u těžkých úloh, kde jde o techniky z kapitol 5 až 8. Na papíře soutěžní řešitelé píšou kandidáty jen tam, kde se jim to vyplatí.

3.6Procvičení

Pole má kandidáty {2, 5, 6}. Zapíšete do něj 6 a šestku má jako kandidáta ještě sedm jeho sousedů. O kolik kandidátů v mřížce ubude?

Δ = |K(p)| + 7 = 3 + 7 = 10: zmizí všichni tři kandidáti pole a šestka u sedmi sousedů.

Lehká úloha z laboratoře má 31 vodítek a na začátku 157 kandidátů. Kolik je to průměrně na prázdné pole?

Prázdných polí je 81 − 31 = 50, průměr 157 / 50 = 3,14 kandidátu na pole. Úloha úrovně 3 má na pole 3,43 – rozdíl je malý, obtížnost dělá až to, jaké vzory kandidáti tvoří.

V bloku máte rohovou sedmičku jen ve dvou polích a obě leží ve 4. sloupci. Co z toho plyne?

Sedmička bloku bude ve 4. sloupci, takže ve zbytku 4. sloupce sedmička být nemůže. To jsou zamčení kandidáti z kapitoly 4 – rohové poznámky je ukazují samy.

Při kontrole najdete ve sloupci dvě pětky. Stačí jednu smazat?

Obvykle ne. Jedna pětka je možná správná a druhá je důsledek dřívější chyby – a z té chyby mohly vzniknout další zápisy. Bezpečné je vrátit se k poslednímu stavu, o kterém víte, že byl v pořádku. Laboratoř a 3D hra na to mají tlačítko Zpět.

Proč v obr. 3.2 mezi 5. a 8. krokem klesá jen modrá křivka?

6., 7. a 8. krok nejsou zápisy, ale škrty: dvakrát zamčení kandidáti (po jednom kandidátovi) a jednou skrytá dvojice, takže prázdných polí zůstává 48. Skrytá dvojice v 8. kroku ubrala 6 kandidátů najednou (ze 154 na 148).

Co si odnést

Kandidáti jsou horní odhad: správná číslice mezi nimi musí být vždy.
Nejdřív skenujte bez tužky, pak rohové poznámky, úplné kandidáty až při zaseknutí.
Po každém zápisu škrtejte u všech 20 sousedů a každý škrt umějte zdůvodnit.

Část IZáklady

Zamčení kandidátizáklady

První technika, která nic nezapisuje, jen škrtá. Když kandidáti číslice v bloku leží všichni v jednom řádku, ta číslice bude v tomto řádku – a jinde v řádku být nemůže. A naopak: leží-li kandidáti řádku všichni v jednom bloku, nemůže být číslice jinde v bloku. Dva pohledy na tutéž úvahu se jmenují ukazující a nárokující.

🔒

Představte si klíč, o kterém víte, že je v kabátě visícím v předsíni. Kabát patří do předsíně i do skříně ve vašem pokoji? Ne – ale klíč je jistě v předsíni, takže ho nemá smysl hledat v jiných místnostech domu. Zamčený kandidát je klíč, jehož místnost znáte, i když ještě nevíte, ve které kapse je.

Zamčení kandidáti

Vyberte příklad a číslici. Laboratoř najde všechny zamčené kandidáty dané číslice: modře podbarví jednotku, ve které kandidáti leží, šedě tu, ve které se škrtá, a přeškrtne odstraněné kandidáty. „Provést škrt“ ho uplatní a hledá se dál.

LABORATOŘ

Model: stav úlohy těsně před prvním použitím techniky (všechny singly už jsou vyplněné a kandidáti aktuální). V režimu „jedna číslice“ jsou modré body kandidáti vybrané číslice; oranžově zvýrazněné jsou ti zamčení.

Minihra: Kde zmizí kandidát?

Laboratoř ukáže kandidáty jedné číslice. Najděte zamčené kandidáty a klepnutím označte všechna pole, kde lze číslici škrtnout; pak stiskněte „Vyhodnotit“. Řešení se ukáže až po vyhodnocení. Série má pět úloh a za aspoň čtyři správné získáte 15 XP.

MINIHRA

0 / 5

+Teorie: průnik jednotek, ukazující a nárokující kandidáti

4.1Průnik dvou jednotek

Blok a řádek (nebo blok a sloupec), které se kříží, mají společná tři pole. Označme K_d(A) pole jednotky A, kde je číslice d kandidátem. Pokud všechna leží v průniku A ∩ B, číslice d jednotky A skončí v průniku – a tím pádem i v jednotce B. V jednotce B je ale každá číslice jen jednou, takže ve zbytku B ji lze škrtnout.locked candidates, intersection removal

Zamčení kandidáti\[ K_d(A) \subseteq A \cap B \ \Rightarrow\ d \notin K(p)\quad \text{pro všechna } p \in B \setminus A \]

Podle toho, která jednotka je A, se rozlišují dva případy.

**Tab. 4.1**Dva druhy zamčených kandidátů
	Ukazující (pointing)	Nárokující (claiming)
kandidáti leží	v bloku, všichni v jednom řádku nebo sloupci	v řádku nebo sloupci, všichni v jednom bloku
škrtá se	ve zbytku řádku nebo sloupce mimo blok	ve zbytku bloku mimo řádek nebo sloupec
jinak se jmenuje	pointing pair / triple	box-line reduction
podíl úloh vzorku, které ji použily	28,4 %	12,4 %

4.2Ukazující: z bloku do řádku

Kandidáti „ukazují“ ven z bloku podél řádku nebo sloupce. Hledají se nejsnáz v rohových poznámkách (kapitola 3): dvě rohové poznámky téže číslice ve stejném řádku bloku jsou ukazující dvojice.pointing pair

Obr. 4.1 Ukazující dvojice. V 1. bloku (modře) může 7 stát jen na ř1s2 a ř1s3 (oranžově), oba v 1. řádku. Sedmička bloku je tedy v 1. řádku a ve zbytku řádku (šedě) být nemůže: škrtá se 7 na ř1s5.

4.3Nárokující: z řádku do bloku

Řádek nebo sloupec „nárokuje“ číslici pro jeden blok. Hledá se tak, že pro číslici projdete řádek nebo sloupec a všimnete si, že všechna jeho možná místa padnou do jednoho bloku.claiming, box-line reduction

Obr. 4.2 Nárokující dvojice. Ve 4. sloupci (modře) může 5 stát jen na ř4s4 a ř5s4, obě pole leží v 5. bloku. Pětka sloupce je tedy v 5. bloku a zbytek bloku (šedě) ji mít nemůže: škrtá se 5 na ř5s6.

Příklad Co se stane po škrtu

Škrt sám nic nezapíše, ale často otevře singl. Když v obr. 4.2 zmizí pětka z ř5s6, může mít pětka v 6. sloupci nebo v 5. řádku jediné zbývající místo – skrytý singl. Řešitel průvodce proto po každém škrtu znovu zkouší nejdřív singly; v úloze úrovně 3 z kapitoly 3 se po dvou zamčených kandidátech a jedné skryté dvojici úloha „rozsype“ už jen singly.

Mistrovská pomůcka

Skenujte po pásech. V pásu tří bloků stačí pro danou číslici zjistit, ve kterých řádcích už je; pokud v jednom bloku pásu zbývají kandidáti jen v jednom řádku, máte ukazující dvojici a zároveň víte, ve kterém řádku musí být číslice ve zbývajícím bloku. Zkušení řešitelé tak najdou zamčené kandidáty už během skenování, bez úplných poznámek.

4.4Proč to není hádání

Úvaha neříká, ve kterém z polí průniku číslice je – jen že je v průniku. To stačí: škrt platí v každém možném dokončení mřížky, takže je stejně jistý jako singl. Zamčení kandidáti jsou zároveň nejmenší „ryba“ (kapitola 6) a nejmenší „podmnožina“ (kapitola 5) – stejná myšlenka s jednou číslicí a dvěma jednotkami.

Pozor

Častá chyba je škrtnout i v samotném průniku nebo „na druhou stranu“: u ukazující dvojice se škrtá v řádku mimo blok, nikdy ve zbytku bloku. Ve zbytku bloku číslice být nemůže už předem – proto jsou kandidáti zamčení.

4.5Procvičení

Kolik polí mají společných blok a řádek, které se kříží? Kolik polí řádku a kolik polí bloku leží mimo průnik?

Průnik má 3 pole. Mimo průnik je 6 polí řádku a 6 polí bloku – v těchto šesti polích se škrtá.

Ve 4. bloku je trojka kandidátem jen na ř5s1 a ř5s3. Kde ji škrtnete?

Ukazující dvojice v 5. řádku: trojku škrtnete v 5. řádku mimo 4. blok, tedy na polích ř5s4 až ř5s9, kde je kandidátem.

Ve 2. řádku je osmička kandidátem jen na ř2s7 a ř2s9. Kde ji škrtnete?

Obě pole leží ve 3. bloku: nárokující dvojice. Osmičku škrtnete ve 3. bloku mimo 2. řádek: ř1s7, ř1s8, ř1s9, ř3s7, ř3s8, ř3s9.

Co když jsou kandidáti číslice v bloku jen v jediném poli?

Pak je to skrytý singl a číslice se rovnou zapíše. Zamčení kandidáti jsou zobecnění: místo jednoho pole víme jen tři pole průniku.

Proč neexistují „zamčení kandidáti“ mezi řádkem a sloupcem?

Řádek a sloupec se protínají v jediném poli. Kdyby všichni kandidáti číslice v řádku leželi v průniku se sloupcem, je to jediné pole – skrytý singl. Technika tedy dává smysl jen pro blok s řádkem nebo blok se sloupcem.

Co si odnést

Leží-li kandidáti číslice jedné jednotky v průniku s druhou jednotkou, ve zbytku druhé jednotky se škrtají.
Ukazující: blok → řádek či sloupec. Nárokující: řádek či sloupec → blok.
Škrtá se vždy mimo průnik a v té jednotce, kterou kandidáti „nevyčerpávají“.

Část IIPokročilí

Dvojice, trojice a čtveřicepokročilí

Mají-li dvě pole jednotky stejné dva kandidáty, tyto dvě číslice si mezi sebe rozdělí – a nikdo jiný v jednotce je mít nemůže. To je nahá dvojice. Stejná úvaha funguje pro tři a čtyři pole a obráceně i pro číslice: vejdou-li se dvě číslice jen do dvou polí, jiní kandidáti z nich zmizí. To je skrytá dvojice. Kapitola ukazuje, proč obojí platí, a proč stačí hledat do velikosti čtyři.

👯

Dva kamarádi si koupili lístky na dvě konkrétní sedadla, jen nevědí, kdo bude sedět kde. Ať se dohodnou jakkoli, ta dvě sedadla jsou obsazená a nikdo další na ně nemůže. A naopak: smějí-li dva hosté sedět jen na dvou určitých místech, ta místa patří jim, i kdyby si na ně dělal nárok kdokoli jiný.

Blok s kandidáty

Jeden blok, v každém poli devět tlačítek kandidátů. Klepnutím kandidáty zapínáte a vypínáte. Laboratoř najde všechny nahé a skryté podmnožiny do velikosti čtyři, které něco škrtají, a odhalí i spor (pole, která se nevejdou). Zkuste z předvolby „prázdný blok“ sestavit vlastní dvojici.

LABORATOŘ

Model: devět polí jedné jednotky (čísla polí vpravo dole). Modře nahá podmnožina, zeleně skrytá, oranžově její číslice, přeškrtnutí kandidáti zmizí. Spor nastane, když některá skupina polí má dohromady méně kandidátů než polí – v reálné úloze to znamená, že se někde škrtl správný kandidát.

Minihra: Najdi podmnožinu

Laboratoř ukáže stav skutečné úlohy těsně před nahou nebo skrytou dvojicí či trojicí. Najděte ji a klepnutím označte všechna pole, kde zmizí nějaký kandidát; pak stiskněte „Vyhodnotit“. Vzor se ukáže až po vyhodnocení. Série má pět úloh, za aspoň čtyři správné získáte 15 XP.

MINIHRA

0 / 5

+Teorie: nahé a skryté podmnožiny, důkaz a dualita

5.1Nahé podmnožiny

Nahá dvojice: dvě pole jednotky, která mají dohromady jen dva kandidáty. Nahá trojice: tři pole s dohromady třemi kandidáty, nahá čtveřice: čtyři pole se čtyřmi. Pozor, u trojice nemusí mít každé pole všechny tři číslice – pole {1, 2}, {2, 3} a {1, 3} tvoří nahou trojici {1, 2, 3}.naked pair, naked triple, naked quad

Nahá podmnožina\[ C \subseteq U,\ \ |C| = k,\ \ \Big|\bigcup_{p \in C} K(p)\Big| = k \ \Rightarrow\ \text{číslice } \bigcup_{p\in C} K(p) \text{ ve zbytku } U \text{ škrtneme} \]

Proč to platí: každé z k polí dostane jednu číslici a všechny musí být různé, protože leží v jedné jednotce. Polí je k a možných číslic také k, takže je spotřebují všechny – na zbytek jednotky žádná z nich nezbude. Je to holubníkový (Dirichletův) princip: k holubů v k přihrádkách obsadí všechny přihrádky.pigeonhole principle

Obr. 5.1 Nahá dvojice ve 4. řádku (šedě). Pole ř4s1 a ř4s2 (modře) mají oba kandidáty {2, 9}. Dvojka a devítka řádku jsou tedy v nich a ve zbytku řádku se škrtají – tady 9 na ř4s7. Kandidáti jsou zobrazeni jen ve 4. řádku.

5.2Skryté podmnožiny

Skrytá dvojice: dvě číslice, které se v jednotce vejdou jen do dvou polí. Ta dvě pole musí obsadit, a jiní kandidáti z nich proto mizí. Podobně skrytá trojice a skrytá čtveřice. „Skrytá“ proto, že pole mají ještě další kandidáty a dvojici v nich na první pohled nevidíte.hidden pair, hidden triple, hidden quad

Skrytá podmnožina\[ D \subseteq \{1,\dots,9\},\ \ |D| = k,\ \ \big|\{\,p \in U : K(p) \cap D \neq \emptyset\,\}\big| = k \ \Rightarrow\ \text{v těchto polích ponecháme jen } D \]

Obr. 5.2 Skrytá dvojice ve 2. sloupci. Dvojka a sedmička se ve sloupci vejdou jen na ř4s2 {2, 7} a ř8s2 {2, 3, 7}. Obsadí je, takže trojka na ř8s2 zmizí. Kandidáti jsou zobrazeni jen ve 2. sloupci.

5.3Dualita: každá nahá podmnožina má skrytý protějšek

Má-li jednotka n prázdných polí a najdete v ní nahou podmnožinu k polí, zbylých n − k polí obsahuje všechny ostatní číslice jednotky – a ty se do nahé podmnožiny nevejdou. Zbytek je tedy skrytá podmnožina velikosti n − k a obě provádějí přesně tytéž škrty. Platí to i obráceně.complementary subsets

Mistrovská pomůcka

Z duality plyne, že stačí hledat podmnožiny do velikosti čtyři: v jednotce s nejvýš devíti prázdnými poli má z každé dvojice protějšků aspoň jedna velikost nejvýš čtyři (min(k, 9 − k) ≤ 4). A prakticky: hledejte tu menší z obou – v jednotce se sedmi prázdnými poli místo skryté pětice nahou dvojici.

5.4Proč se špatně hledají

Počet skupin, které by člověk musel prověřit, rychle roste. V jednotce s devíti prázdnými poli je možných skupin k polí (a stejně tak k číslic):

**Tab. 5.1**Počet skupin k polí z devíti a podíl úloh vzorku, které podmnožinu použily
Velikost k	Skupin C(9, k)	Nahá – úloh vzorku	Skrytá – úloh vzorku
1 (singl)	9	85,5 %	99,98 %
2 (dvojice)	36	12,2 %	7,5 %
3 (trojice)	84	1,9 %	0,45 %
4 (čtveřice)	126	0,05 %	–

Vzorek 6 000 úloh, řešitel zkouší nahé podmnožiny před skrytými. Skrytou čtveřici nepoužila žádná úloha – její škrty vždy dřív obstarala nahá podmnožina, protějšek z duality. Nahou čtveřici použily 3 úlohy z 6 000.

Příklad Nahá trojice bez trojic

V předvolbě „nahá trojice“ mají pole 3, 4 a 8 kandidáty {1, 2}, {2, 3} a {1, 3}. Žádné nemá tři kandidáty, a přesto je to trojice {1, 2, 3}. Škrtne pět kandidátů: jedničku v polích 1 a 6, dvojku v poli 2 a trojku v polích 5 a 9.

Pozor

Tři pole se dvěma kandidáty {1, 2} v jedné jednotce nejsou „silná trojice“, ale spor: tři pole, dvě číslice. V úloze to znamená chybu někde dřív (předvolba „spor“). Stejně tak dvě pole s jediným kandidátem 5.

5.5Procvičení

V řádku mají tři pole kandidáty {4, 7}, {4, 8} a {7, 8}. Co platí pro ostatní pole řádku?

Je to nahá trojice {4, 7, 8}: tři pole, tři číslice dohromady. Ve zbytku řádku se škrtají 4, 7 i 8.

V předvolbě „skrytá dvojice“ se trojka a šestka vejdou jen do polí 2 a 7. Kolik kandidátů zmizí?

Pole 2 má {1, 3, 6, 9}, pole 7 {2, 3, 6, 8}. Ponechají si jen {3, 6}: zmizí 1 a 9 z pole 2 a 2 a 8 z pole 7, celkem 4 kandidáti.

Jednotka má šest prázdných polí a najdete v ní nahou dvojici. Jaký skrytý protějšek v ní je?

Zbylá 6 − 2 = 4 pole tvoří skrytou čtveřici zbylých čtyř číslic. Škrtá tytéž kandidáty jako nahá dvojice.

Kolik skupin tří polí musíte v nejhorším případě prověřit v jednotce s devíti prázdnými poli? A kolik skupin čtyř?

C(9, 3) = 9 · 8 · 7 / 6 = 84 a C(9, 4) = 9 · 8 · 7 · 6 / 24 = 126. Proto řešitelé začínají od polí s málo kandidáty – podmnožinu tvoří jen pole, která mají nejvýš k kandidátů.

V bloku mají pole kandidáty {1, 2}, {1, 2} a třetí pole {1, 2, 5}. Co platí?

První dvě pole jsou nahá dvojice {1, 2}. Třetí pole proto 1 ani 2 mít nemůže: zbude mu jediný kandidát a je to 5 (nahý singl jako důsledek dvojice).

Co si odnést

Nahá: k polí má dohromady k kandidátů – ty číslice ve zbytku jednotky škrtněte.
Skrytá: k číslic se vejde jen do k polí – jiné kandidáty z těch polí škrtněte.
Každá nahá podmnožina má skrytý protějšek, takže stačí hledat do velikosti čtyři – a vždy tu menší.

Část IIPokročilí

Ryby: X-wing, Swordfish, Jellyfishpokročilí

Ryby jsou vzory jedné číslice přes několik řádků a sloupců. Když se kandidáti číslice ve dvou řádcích vejdou do dvou sloupců, je to X-wing: dvě číslice obsadí oba sloupce a jinde v nich být nemohou. Se třemi řádky a sloupci je to Swordfish, se čtyřmi Jellyfish. Jméno „ryby“ dostaly od síťky řádků a sloupců, do které se chytí.

🎣

Dva hlídači mají každý projít jednu chodbu a oba smějí stát jen u dvou stejných dveří, každý u jiných. Ať se rozestaví jakkoli, oboje dveře jsou hlídané. Kdo by chtěl ke dveřím z jiné chodby, narazí na hlídače. Řádky jsou chodby, sloupce dveře a hlídači číslice.

Rybářská síť

Laboratoř ukazuje kandidáty jedné číslice. Klepnutím na pole (nebo na číslo řádku či sloupce u okraje) vyberte základní řádky. Laboratoř spočítá, do kolika sloupců se jejich kandidáti vejdou; je-li sloupců stejně jako řádků, chytila se ryba a přeškrtne, co jde škrtnout. Přepnutím na sloupce hledáte rybu otočenou o 90°.

LABORATOŘ

Model: stav skutečné úlohy těsně před rybou. Modře základní linie, šedě krycí linie, oranžově kandidáti ryby; přeškrtnutí kandidáti v krycích liniích mimo rybu zmizí. Jellyfish je vzácná: ve vzorku 6 000 úloh ji potřebovaly dvě.

Minihra: Chyť rybu

Laboratoř ukáže kandidáty jedné číslice ve stavu těsně před X-wingem nebo Swordfishem. Najděte rybu a označte všechna pole, kde číslice zmizí; pak „Vyhodnotit“. Ryba se ukáže až po vyhodnocení. Série má pět úloh, za aspoň čtyři správné získáte 20 XP.

MINIHRA

0 / 5

+Teorie: základní a krycí linie, důkaz, dualita a ryby s ploutví

6.1X-wing

Vyberte číslici d a dva řádky, ve kterých má d jen dvě možná místa – a to v týchž dvou sloupcích. Těm řádkům se říká základní linie, sloupcům krycí linie. Čtyři pole tvoří rohy obdélníku.X-wing, base sets, cover sets

V každém základním řádku bude právě jedna číslice d. Ty dvě číslice nemohou být ve stejném sloupci, takže jedna je v prvním krycím sloupci a druhá ve druhém. Oba krycí sloupce tím mají svou číslici d a nikde jinde v nich už být nemůže. Které dva rohy obdélníku to budou, nevíme – ale nepotřebujeme to vědět.

Obr. 6.1 X-wing na číslici 9. V řádcích 4 a 8 (modře) může devítka stát jen ve sloupcích 1 a 7 (šedě). Oba sloupce tedy dostanou devítku z těchto řádků a ve zbytku sloupců se škrtá – tady 9 na ř6s1. Body jsou kandidáti devítky.

6.2Swordfish a Jellyfish

Úvaha funguje pro libovolný počet n řádků: vejdou-li se kandidáti číslice z n základních řádků do n krycích sloupců, obsadí je a ve zbytku krycích sloupců se číslice škrtá. Pro n = 3 je to Swordfish, pro n = 4 Jellyfish. Základní řádek přitom nemusí mít kandidáta v každém krycím sloupci – stačí dvě nebo tři místa, jen všechna musí ležet v krycích sloupcích.swordfish, jellyfish

Ryba velikosti n\[ |B| = |C| = n,\quad \bigcup_{r \in B} K_d(r) \subseteq \bigcup_{c \in C} c \ \Rightarrow\ d \notin K(p)\ \ \text{pro } p \in \bigcup_{c\in C} c \setminus \bigcup_{r\in B} r \]

Obr. 6.2 Swordfish na číslici 4. Řádky 2, 6 a 9 (modře) mají každý jen dvě místa pro čtyřku, všechna ve sloupcích 1, 2 a 8 (šedě). Tři čtyřky obsadí tři sloupce, takže ve sloupci 2 mimo rybu čtyřka zmizí: škrt na ř4s2.

Příklad Jellyfish z laboratoře

Na číslici 3: v řádcích 2, 5, 6 a 8 má trojka 2, 2, 3 a 2 místa, všechna ve sloupcích 1, 4, 6 a 9. Čtyři trojky obsadí čtyři sloupce a škrtnou trojku na ř1s4, ř1s9, ř3s9 a ř9s9. Jellyfish použily jen 2 úlohy z 6 000 ve vzorku – v soutěžích se vyskytuje vzácně.

6.3Dualita a proč nejsou větší ryby

Pro číslici d označme m počet řádků, kde ještě není zapsaná – stejně tolik je i takových sloupců. Ryba velikosti n v řádcích znamená, že zbylých m − n sloupců tvoří rybu velikosti m − n „ve sloupcích“, a obě škrtají totéž. Protože m ≤ 9, má vždy jedna z dvojice velikost nejvýš 4. Ryby velikosti 5 a víc proto hledat nemusíte – je to stejná dualita jako u podmnožin v kapitole 5. Ryba je vlastně podmnožina v jiné „jednotce“: místo polí jednoho řádku pracuje s řádky jedné číslice.fish duality

Mistrovská pomůcka

X-wing hledejte u číslic, které už jsou v mřížce šestkrát nebo sedmkrát: zbývají jim dva či tři řádky a vzor je hned vidět. V rohových poznámkách (Snyderova notace) se X-wing pozná jako dvě dvojice rohových poznámek ve stejných dvou sloupcích.

6.4Ryby s ploutví

Někdy má základní řádek navíc kandidáta mimo krycí sloupce – ploutev. Pak ryba neplatí celá, ale platí „buď ryba, nebo ploutev“. Škrtat jde jen v polích krycích sloupců, která zároveň vidí ploutev (leží s ní v bloku). Ryby s ploutví (finned X-wing, finned Swordfish) řešitel průvodce nepoužívá; jsou o úroveň výš než úroveň 5.finned fish, fin

Pozor

Škrtá se v krycích liniích mimo rybu, nikdy v základních. Kdo si splete řádky se sloupci, škrtne správnou číslici. Pomůže říct si nahlas: „V řádcích 4 a 8 je devítka jen ve sloupcích 1 a 7, takže škrtám ve sloupcích 1 a 7.“

6.5Procvičení

Ve sloupcích 6 a 7 může osmička stát jen v řádcích 4 a 9. Kde osmičku škrtnete?

Základní linie jsou sloupce 6 a 7, krycí řádky 4 a 9. Škrtá se v řádcích 4 a 9 mimo sloupce 6 a 7. V úloze z laboratoře (X-wing ve sloupcích) je to jediné pole ř4s5.

Jeden ze tří základních řádků Swordfishe má jen jedno místo pro číslici. Co to znamená?

Pak je to skrytý singl v řádku a číslice se rovnou zapíše. Ryba má smysl, jen když má každý základní řádek aspoň dvě místa.

Číslice 5 už je zapsaná ve třech řádcích. Najdete Swordfish v řádcích. Jakou rybu tvoří zbylé sloupce?

Zbývá m = 6 řádků i sloupců bez pětky. Swordfish má n = 3, protějšek tedy velikost 6 − 3 = 3: Swordfish ve sloupcích, se stejnými škrty.

Kolik dvojic řádků musíte pro jednu číslici prověřit, hledáte-li X-wing v řádcích? A kolik trojic pro Swordfish?

C(9, 2) = 36 dvojic a C(9, 3) = 84 trojic. Prakticky mnohem méně: berou se jen řádky, kde má číslice dvě (nebo tři) místa.

Jsou zamčení kandidáti z kapitoly 4 taky ryba?

Ano, v širším smyslu: ryba velikosti 1, kde základní linií je blok a krycí linií řádek nebo sloupec (nebo naopak). Jedna číslice v bloku „obsadí“ jeden řádek a jinde v něm být nemůže.

Co si odnést

Ryba: kandidáti číslice z n řádků se vejdou do n sloupců – ve zbytku těch sloupců se číslice škrtá.
X-wing = 2, Swordfish = 3, Jellyfish = 4; větší ryby nejsou potřeba díky dualitě.
Škrtá se v krycích liniích mimo rybu; základní řádek potřebuje aspoň dvě místa.

Část IIPokročilí

Křídla: XY, XYZ a Wpokročilí

Pole se dvěma kandidáty je malý přepínač: buď je to jedna číslice, nebo druhá. Tři takové přepínače správně propojené tvoří křídlo. Ať je prostřední pole (pivot) čímkoli, určitá číslice Z skončí v jednom z krajních polí (klepet) – a kdo vidí obě klepeta, Z mít nemůže. Kapitola probírá XY-wing, XYZ-wing a W-wing krok za krokem.

🦅

Máte dvě cesty domů a víte jen, že po jedné z nich vás čeká kamarád s deštníkem. Ať půjdete kudykoli, deštník budete mít – takže svůj vlastní můžete nechat doma. Křídlo je úvaha „ať tak, nebo tak, výsledek je stejný“.

Křídla krok za krokem

Vyberte druh křídla a příklad. Tlačítkem „Další krok“ projdete úvahu v pěti krocích: kde hledat, pivot, klepeta, rozbor případů a škrt. Pole vzoru mají kandidáty zvýrazněné, čárkované čáry spojují pivot s klepety přes společnou číslici.

LABORATOŘ

Model: stav skutečné úlohy těsně před křídlem. Oranžový rámeček je pivot (u W-wingu dvojice polí se stejnými kandidáty), modré rámečky klepeta nebo konce silné vazby, červeně pole se škrtem.

Minihra: Najdi křídlo

Stav úlohy těsně před XY-wingem, XYZ-wingem nebo W-wingem. Najděte vzor a označte pole, kde zmizí kandidát; pak „Vyhodnotit“. Vzor se ukáže až po vyhodnocení. Série má pět úloh, za aspoň čtyři správné získáte 20 XP.

MINIHRA

0 / 5

+Teorie: pole se dvěma kandidáty, rozbor případů a tři druhy křídel

7.1Pole se dvěma kandidáty

Pole s právě dvěma kandidáty {X, Y} je nejjednodušší logický přepínač: buď X, nebo Y, třetí možnost není. Každá technika této kapitoly je rozbor případů: vyzkouší obě polohy přepínače a ukáže, že v obou platí stejný závěr. Závěr, který platí ve všech případech, platí vždy – to není hádání, ale důkaz.bivalue cell, proof by cases

7.2XY-wing

Pivot {X, Y} vidí dvě klepeta {X, Z} a {Y, Z}. Je-li pivot X, klepeto {X, Z} přijde o X a je Z. Je-li pivot Y, je Z druhé klepeto. Z je tedy jistě v jednom z klepet a pole, které vidí obě klepeta, Z mít nemůže.XY-wing (Y-wing), pivot, pincers

XY-wing jako rozbor případů\[ \text{pivot} = X \Rightarrow \text{klepeto}_1 = Z,\qquad \text{pivot} = Y \Rightarrow \text{klepeto}_2 = Z \qquad\Longrightarrow\qquad Z \notin K(p)\ \ \text{pro } p \in P(\text{klepeto}_1) \cap P(\text{klepeto}_2) \]

Obr. 7.1 XY-wing. Pivot ř7s2 {4, 5} (oranžově) vidí klepeta ř7s8 {4, 9} (stejný řádek) a ř8s3 {5, 9} (stejný blok). Je-li pivot 4, je ř7s8 = 9; je-li 5, je ř8s3 = 9. Pole ř8s9 vidí obě klepeta, takže devítku mít nemůže. Kandidáti jsou zobrazeni jen v polích vzoru a v poli se škrtem.

7.3XYZ-wing

Pivot má tři kandidáty {X, Y, Z}, klepeta {X, Z} a {Y, Z}. Případy jsou tři: pivot X (pak je Z první klepeto), pivot Y (druhé klepeto), nebo je pivot sám Z. Z je tedy v jednom ze tří polí a škrtá se jen v polích, která vidí všechna tři. Taková pole leží vždy v bloku pivota, proto XYZ-wing škrtá málo – obvykle jeden nebo dva kandidáty.XYZ-wing

Příklad XYZ-wing z laboratoře

Pivot ř3s7 {3, 6, 9}, klepeta ř2s8 {3, 9} a ř5s7 {6, 9}. Ať je pivot 3, 6, nebo 9, devítka skončí v pivotu nebo v jednom z klepet. Pole ř2s7 vidí všechna tři (pivot a ř2s8 ve 3. bloku, ř5s7 v 7. sloupci) – devítku škrtáme.

7.4W-wing

Dvě pole se stejnou dvojicí {X, Z}, která se nevidí, plus silná vazba na X: jednotka, kde může X stát jen na dvou místech, z nichž jedno vidí první pole a druhé druhé pole. Kdyby ani jedno z polí nebylo Z, byla by obě X – a pak by X neměla v té jednotce kam. Aspoň jedno pole je tedy Z a kdo vidí obě, Z mít nemůže.W-wing, strong link

Obr. 7.2 W-wing. Pole ř6s1 a ř7s3 (oranžově) mají stejnou dvojici {6, 8} a nevidí se. Ve 3. řádku (šedě) může 8 stát jen na ř3s1 nebo ř3s3 (modře, plná čára = silná vazba). Kdyby obě oranžová pole byla 8, nezbyla by ve 3. řádku osmička. Jedno z nich je 6, a proto ř5s3, které vidí obě, šestku mít nemůže.

**Tab. 7.1**Tři křídla v přehledu (podíl úloh vzorku 6 000, které je použily)
Křídlo	Vzor	Kde se škrtá Z	Podíl úloh
XY-wing	pivot {X, Y}, klepeta {X, Z}, {Y, Z}	pole, která vidí obě klepeta	8,9 %
XYZ-wing	pivot {X, Y, Z}, klepeta {X, Z}, {Y, Z}	pole, která vidí pivot i obě klepeta	4,1 %
W-wing	dvě pole {X, Z} + silná vazba na X	pole, která vidí obě pole {X, Z}	10,1 %

Mistrovská pomůcka

Křídla hledejte od pivotu: projděte pole se dvěma kandidáty a u každého se podívejte, jestli vidí dvě další pole se dvěma kandidáty, která s ním sdílejí po jedné číslici a navzájem tu třetí. Rohové poznámky pomohou u W-wingu – dvojice rohových poznámek je silná vazba.

Pozor

Klepeta musí mít stejnou třetí číslici Z. Pivot {1, 4} s klepety {1, 6} a {4, 8} není XY-wing: v jednom případě vznikne šestka, ve druhém osmička, a nic společného se škrtnout nedá.

7.5Křídla jako krátké řetězy

XY-wing je řetěz tří polí se dvěma kandidáty: klepeto – pivot – klepeto. W-wing je řetěz pole – silná vazba – pole. Kapitola 8 ukáže, že řetězy mohou být libovolně dlouhé a že všechna křídla jsou jejich nejkratší případy.

7.6Procvičení

Pivot {2, 7} vidí klepeta {2, 5} a {7, 5}. Kterou číslici a kde škrtnete?

Z = 5. Je-li pivot 2, je první klepeto 5; je-li 7, je druhé klepeto 5. Pětku škrtnete ve všech polích, která vidí obě klepeta.

Proč u XYZ-wingu nestačí, aby pole vidělo obě klepeta?

Protože Z může být i v pivotu (pivot má kandidáty X, Y i Z). Pole, které vidí jen klepeta, by mohlo Z mít, kdyby Z bylo v pivotu. Proto se škrtá jen tam, kam vidí všechna tři pole.

Proč se u W-wingu dvě pole {X, Z} nesmějí vidět?

Kdyby se viděla, byla by to nahá dvojice (kapitola 5) a škrtala by X i Z v celé společné jednotce – jednodušší technika. W-wing je užitečný právě u polí daleko od sebe.

Pivot ř7s2 a klepeta ř7s8 a ř8s3 z obr. 7.1: proč devítku nelze škrtnout na ř7s5?

ř7s5 vidí klepeto ř7s8 (stejný řádek), ale ne ř8s3 (jiný řádek, sloupec i blok). Kdyby byla devítka v ř8s3, mohla by ř7s5 devítku mít. Škrtá se jen tam, kam vidí obě klepeta.

Kolik polí může vidět obě klepeta XY-wingu, pokud klepeta leží v různých pásech i štocích?

Jen 2: „rohy obdélníku“ – průsečík řádku prvního klepeta se sloupcem druhého a naopak. Leží-li klepeta ve stejném pásu (nebo štoku), přibudou společní sousedé v blocích a může jich být až 6.

Co si odnést

Křídlo je rozbor případů: ať je pivot čímkoli, Z skončí v klepetu (nebo v pivotu u XYZ).
Škrtá se v polích, která vidí obě klepeta; u XYZ-wingu navíc i pivot.
W-wing: dvě stejné dvojice {X, Z}, které se nevidí, spojené silnou vazbou na X.

Část IIPokročilí

Barvení a řetězypokročilí

Všechny techniky od singlu po křídla jsou krátké logické řetězy. Tady se řetězy prodlužují. Základem jsou dva druhy vazeb mezi kandidáty: silná (aspoň jeden platí) a slabá (nejvýš jeden platí). Střídáním silných a slabých vazeb vzniká barvení, X-řetězy, XY-řetězy a obecně AIC. Kapitola končí otázkou, kde logika přechází v hádání.

🔗

Řetěz je jako řada domina: když padne první kostka, padnou všechny. V sudoku se ale nepoužívá „když“ jako tip, nýbrž jako rozbor obou možností: buď platí začátek řetězu, nebo – přes všechny kostky – jeho konec. Jedno z toho je pravda vždycky, a co odporuje obojímu, je pryč.

Barvení a řetězy

Vyberte techniku a příklad a procházejte úvahu po krocích. U barvení se nejdřív ukážou silné vazby jedné číslice, pak se obarví střídavě modře a zeleně a nakonec se najde spor nebo past. U řetězů se ukáže řetěz a škrt.

LABORATOŘ

Model: stav skutečné úlohy těsně před technikou. Plná čára = silná vazba, čárkovaná = slabá. U XY-řetězu je u čáry spojovací číslice zvýrazněna v obou polích. Řešitel průvodce hledá X-řetězy do délky 10 polí a XY-řetězy do délky 8 polí a vybírá nejkratší.

Minihra: Logika, nebo hádání?

Zařaďte každou úvahu: je to čistá logika, logika, která předpokládá jediné řešení, nebo hádání? Vysvětlení se ukáže po výběru. Za aspoň sedm správných z osmi získáte 15 XP.

MINIHRA

0 / 8

+Teorie: vazby, barvení, X-řetězy, XY-řetězy, AIC a hranice logiky

8.1Silná a slabá vazba

Mezi dvěma kandidáty (číslice v poli) jsou dva užitečné vztahy.strong link, weak link

Silná vazba (zápis A = B): aspoň jeden z kandidátů platí. Vzniká, když má číslice v jednotce právě dvě místa, nebo mezi dvěma kandidáty pole se dvěma kandidáty.
Slabá vazba (zápis A − B): nejvýš jeden z kandidátů platí. Vzniká mezi stejnými číslicemi ve vzájemně viditelných polích, nebo mezi dvěma kandidáty téhož pole.

Vazby jako výroky\[ A = B \iff (\neg A \Rightarrow B), \qquad A - B \iff (A \Rightarrow \neg B) \]

Silná vazba v jednotce s právě dvěma místy je zároveň slabá (dvě stejné číslice v jednotce být nemohou) – takovou vazbu lze v řetězu použít v obou rolích.

8.2Jednoduché barvení

Vezměte jednu číslici a všechny její silné vazby. Spojené kandidáty obarvěte střídavě dvěma barvami. V každé souvislé síti je jedna barva celá pravdivá a druhá celá nepravdivá – jen zatím nevíte která. Z toho plynou dvě pravidla.simple coloring, color wrap, color trap

Spor (color wrap): dvě pole stejné barvy se vidí. Obě být danou číslicí nemohou, takže ta barva je nepravdivá a číslice se škrtá ve všech jejích polích.
Past (color trap): pole mimo síť vidí pole obou barev. Jedna z nich je pravdivá, takže číslice v tom poli být nemůže.

Obr. 8.1 Jednoduché barvení číslice 4, past. Silné vazby (čáry) spojují sedm kandidátů: modře ř2s1, ř5s3 a ř8s2, zeleně ř2s2, ř6s1, ř7s3 a ř8s9. Pole ř5s9 vidí modrou ř5s3 (řádek) i zelenou ř8s9 (sloupec), a jedna z barev je pravdivá – čtyřku na ř5s9 škrtáme.

Příklad Spor barev z laboratoře

U číslice 8 (předvolba „barvení – spor“, příklad 1) mají pole ř9s3 a ř9s6 stejnou barvu a leží ve stejném řádku. Ta barva tedy pravdivá být nemůže a osmička se škrtá ve všech jejích polích: ř4s5, ř9s3 a ř9s6. Jeden spor tak škrtne tři kandidáty najednou.

8.3X-řetězy a X-cykly

X-řetěz je řetěz kandidátů jedné číslice, ve kterém se střídají silné a slabé vazby a který silnou vazbou začíná i končí: A = B − C = D. Když A neplatí, platí B, pak neplatí C a platí D. Takže platí A nebo D – a kandidát, který vidí oba konce, je pryč. Uzavřený řetěz je X-cyklus; X-wing je nejkratší X-cyklus (čtyři pole) a Swordfish také jde zapsat jako cyklus.X-chain, X-cycle

Řetěz se střídavými vazbami\[ A = B - C = D \ \Rightarrow\ A \vee D \ \Rightarrow\ d \notin K(p)\ \ \text{pro } p \in P(A) \cap P(D) \]

Příklad X-řetěz z laboratoře

Číslice 7: ř4s7 = ř9s7 − ř8s8 = ř8s2. Silné vazby jsou 7. sloupec (sedmička jen na ř4s7 a ř9s7) a 8. řádek (jen na ř8s8 a ř8s2), slabá vazba ř9s7 − ř8s8 je společný 9. blok. Jeden z konců ř4s7 a ř8s2 je sedmička; pole ř4s2 vidí oba (4. řádek a 2. sloupec), takže sedmičku mít nemůže.

8.4XY-řetězy

XY-řetěz skáče mezi poli se dvěma kandidáty. Sousední pole se vidí a sdílejí číslici, přes kterou se „předává“ pravda. Začíná-li první pole kandidátem Z a končí-li poslední pole také Z, platí: buď je první pole Z, nebo se po řetězu vynutí Z v posledním poli. XY-wing je XY-řetěz tří polí.XY-chain

Obr. 8.2 XY-řetěz čtyř polí: ř4s8 {6, 8} → ř5s7 {2, 6} → ř5s4 {2, 4} → ř9s4 {4, 8}. Když ř4s8 není 8, je 6, pak ř5s7 = 2, ř5s4 = 4 a ř9s4 = 8. Jeden z konců je tedy 8 a pole ř4s4, které vidí oba (4. řádek a 4. sloupec), osmičku mít nemůže. Kandidáti jsou zobrazeni jen v polích řetězu a v poli se škrtem.

8.5AIC v kostce

AIC (alternating inference chain, řetěz se střídavými závěry) spojuje oba druhy: silné vazby přes jednotky i přes pole se dvěma kandidáty, různé číslice v jednom řetězu. Zapisuje se stejně, například (jen ukázka zápisu) (7)ř4s7 = (7)ř9s7 − (7)ř9s9 = (2)ř9s9 − (2)ř1s9 = (2)ř1s3. Pravidlo zůstává: řetěz začíná i končí silnou vazbou, takže platí jeden z konců, a kandidát se slabou vazbou na oba konce se škrtá. Všechny techniky kapitol 4 až 8 jsou zvláštní případy AIC – proto se o nich mluví jako o jedné rodině.AIC, Eureka notation

**Tab. 8.1**Řetězy v přehledu (podíl úloh vzorku 6 000, které je použily)
Technika	Co spojuje	Kde se škrtá	Podíl úloh
jednoduché barvení	silné vazby jedné číslice	celá barva (spor) nebo pole vidící obě barvy (past)	5,9 %
X-řetěz	jedna číslice, střídavé vazby	pole vidící oba konce	4,6 %
XY-řetěz	pole se dvěma kandidáty	pole vidící oba konce	5,5 %
AIC	obojí, více číslic	kandidát se slabou vazbou na oba konce	mimo řešitel

8.6Kde končí logika a začíná hádání

Řetěz je rozbor případů: ukazuje, že škrt platí v každém řešení. Hádání je jiný postup – zvolíte možnost, pokračujete, a když narazíte na spor, vracíte se (backtracking, kapitola 11). Hranice není ostrá. Úvaha „kdyby tu byla trojka, po pěti vynucených krocích vznikne spor, tedy tu trojka není“ je formálně důkaz sporem (technika Nishio), ale vlastně jde o pokus, jen krátký. Mezi soutěžními řešiteli platí neformální dohoda: dlouhé zkoušení „co kdyby“ se za eleganci nepovažuje, krátký řetěz ano.trial and error, bifurcation, Nishio

Zvláštní skupinou jsou techniky, které využívají předpoklad jediného řešení, například unikátní obdélník: kdyby čtyři pole ve dvou blocích tvořila obdélník se stejnou dvojicí kandidátů, šly by obě číslice prohodit a úloha by měla dvě řešení – takže to nastat nemůže. Logicky je to v pořádku jen u úloh, o nichž víte, že mají jediné řešení. Řešitel průvodce tyto techniky nepoužívá.uniqueness techniques, unique rectangle

Pozor

Řetěz musí začínat i končit silnou vazbou. Řetěz A = B − C (končící slabou vazbou) dává jen „když neplatí A, neplatí C“, a z toho žádný škrt neplyne. Nejčastější chyba je považovat dvě stejné číslice ve stejném bloku za silnou vazbu, i když má číslice v bloku tři místa.

8.7Procvičení

Ve 2. řádku může trojka stát jen na ř2s4 a ř2s8. Jaká je mezi nimi vazba?

Silná (jedno z polí je 3) a zároveň slabá (obě 3 být nemohou). Taková vazba se do řetězu hodí na kterékoli místo.

Pro číslici 5 platí řetěz ř1s1 = ř1s6 − ř4s6 = ř4s2. Ve kterých polích můžete pětku škrtnout?

V polích, která vidí oba konce ř1s1 a ř4s2: ř1s2, ř2s2, ř3s2, ř4s1, ř5s1 a ř6s1 – pokud tam pětka je kandidátem.

Při barvení vidí pole jednu modrou a dvě zelená pole. Může mít číslici?

Ne. Vidí obě barvy a jedna z nich je pravdivá – je to past. Počet polí každé barvy nehraje roli.

XY-řetěz {1, 5} → {5, 7} → {7, 1}: první a poslední pole se nevidí. Kterou číslici a kde škrtnete?

Začíná i končí jedničkou (Z = 1). Když první pole není 1, je 5, druhé 7 a poslední 1. Jednička je tedy v jednom z konců a škrtá se ve všech polích, která vidí oba konce. Se třemi poli je to vlastně XY-wing s pivotem {5, 7}.

Je unikátní obdélník „hádání“?

Není to hádání, ale není to ani čistá logika: platí jen pro úlohy s jediným řešením. U úlohy z novin nebo soutěže, kde je jedinečnost zaručená, je použití korektní; u neověřené úlohy může vést k chybě.

Co si odnést

Silná vazba: aspoň jeden platí. Slabá: nejvýš jeden platí. Řetěz je střídá a začíná i končí silnou.
Barvení: stejná barva, která se vidí, je nepravdivá; pole, které vidí obě barvy, číslici nemá.
Řetěz je rozbor případů, ne tip. Techniky „jediného řešení“ jsou zvláštní skupina mezi logikou a důvěrou v autora.

Část IIIMistr a věda

Killer a další variantymistr a věda

Varianty mění jedno ze dvou: přidávají podmínky, nebo mění tvar oblastí. Killer sudoku přidává klece se součty a místo vodítek dává jen čísla. Sudoku X přidává diagonály, Windoku čtyři okna, Jigsaw nahrazuje bloky nepravidelnými oblastmi a mini sudoku 6 × 6 a 4 × 4 zmenšují mřížku pro děti. Kapitola ukazuje tabulku kombinací součtů (spočítanou skriptem), pravidlo 45 a to, jak varianty mění počet sousedů.

🧮

Killer sudoku je jako účtenka bez položek: víte, kolik se zaplatilo za tři věci, a víte, že každá stála celý počet korun od 1 do 9 a žádné dvě stejně. Utratit 23 se dá jediným způsobem – za 6, 8 a 9. Kdo zná „ceník“ součtů, vyřeší polovinu úlohy dřív, než napíše první číslici.

Kalkulačka kombinací součtů

Nastavte velikost klece a součet. Laboratoř vypíše všechny sady různých číslic s tímto součtem a nakreslí, kolik kombinací má každý součet. Klepnutím na číslici ji vyžádáte (zeleně) nebo vyloučíte (červeně) – třeba proto, že už v řádku je – a seznam se zúží.

LABORATOŘ

Počet polí klece Součet klece

Model: všechny podmnožiny číslic 1–9 dané velikosti (u 3 polí jich je C(9, 3) = 84) roztříděné podle součtu. Oranžový sloupec je zvolený součet. Číslice „ve všech“ musí v kleci být, číslice „v žádné“ v ní být nemohou.

Varianty a sousedé

Přepínejte varianty a klepněte na pole: laboratoř podbarví všechny jeho sousedy a spočítá, kolik jich má. Čím víc sousedů, tím víc informací pole dostává – a tím méně vodítek varianta potřebuje.

LABORATOŘ

Model: sousedé jsou pole, která s vybraným polem sdílejí aspoň jednu oblast (řádek, sloupec, blok, diagonálu, okno nebo klec). Rozložení Jigsaw a klecí je jedna pevná ukázka.

Minihra: Pravidlo 45

Podbarvený blok pokrývají klece (čárkovaně, součet v rohu). Buď jedna klec trčí z bloku ven, nebo jedno pole bloku patří do klece, která sahá ven. Spočítejte číslici v poli s otazníkem a klepněte na ni. Řešení se ukáže po odpovědi. Kolo má šest úkolů, za aspoň pět správných získáte 15 XP.

MINIHRA

0 / 6

+Teorie: Killer a kombinace součtů, pravidlo 45, Sudoku X, Jigsaw, Windoku a malé mřížky

9.1Killer sudoku

Platí všechna pravidla klasického sudoku a k nim klece: skupiny polí ohraničené čárkovaně, u kterých je zadán součet. Číslice v kleci dávají tento součet a neopakují se. Vodítka obvykle žádná nejsou – všechnu informaci nesou součty. Součet všech klecí je vždy 405, součet číslic celé mřížky.killer sudoku, cage

Obr. 9.1 Killer sudoku z laboratoře: 31 klecí (4 jednopolové, 11 dvoupolových, 9 tří- a 7 čtyřpolových), součty dávají dohromady 405. Osm klecí má jedinou možnou sadu: čtyři jednopolové (fungují jako vodítka), dvě dvoupolové se součtem 17 (8 + 9), dvoupolová se součtem 4 (1 + 3) a čtyřpolová se součtem 30 (6, 7, 8, 9).

9.2Kombinace součtů

Klec o n polích obsahuje n různých číslic, tedy jednu z C(9, n) podmnožin. Nejmenší součet má sada 1, 2, …, n, největší sada 9, 8, …, 10 − n:

Rozsah součtů klece o n polích\[ s_{\min} = \frac{n(n+1)}{2}, \qquad s_{\max} = \frac{n(19-n)}{2}, \qquad \text{počet sad} = \binom{9}{n} \]

**Tab. 9.1**Kombinace součtů podle velikosti klece (spočítáno výčtem všech 511 neprázdných podmnožin)
Polí	Sad	Součty	Nejvíc sad	Součty s jedinou sadou
2	36	3–17	4 (9, 10, 11)	3 = 1 + 2, 4 = 1 + 3, 16 = 7 + 9, 17 = 8 + 9
3	84	6–24	8 (14, 15, 16)	6 = {1, 2, 3}, 7 = {1, 2, 4}, 23 = {6, 8, 9}, 24 = {7, 8, 9}
4	126	10–30	12 (20)	10 = {1, 2, 3, 4}, 11 = {1, 2, 3, 5}, 29 = {5, 7, 8, 9}, 30 = {6, 7, 8, 9}
5	126	15–35	12 (25)	15, 16, 34, 35
6	84	21–39	8 (29, 30, 31)	21, 22, 38, 39
7	36	28–42	4 (34, 35, 36)	28, 29, 41, 42
8	9	36–44	1	všechny (chybí jediná číslice 45 − s)

Tabulka je souměrná: klec o n polích se součtem s má tolik sad jako klec o 9 − n polích se součtem 45 − s (doplněk). Jedinečné součty jsou vždy dva nejmenší a dva největší.

Mistrovská pomůcka

Naučte se nazpaměť „krajní“ součty: dvojice 3, 4, 16, 17, trojice 6, 7, 23, 24 a čtveřice 10, 11, 29, 30. A ještě dvojice se dvěma sadami: 5 = 1 + 4 nebo 2 + 3, 15 = 6 + 9 nebo 7 + 8. Ve středu tabulky jsou součty s mnoha sadami (trojice se součtem 15 jich má osm) a ty se luští až pomocí pravidla 45.

9.3Pravidlo 45

Každá jednotka má součet 1 + 2 + … + 9 = 45. Pokrývají-li klece celou jednotku a jedno pole navíc, je to pole („outie“) rovno součtu klecí minus 45. Leží-li naopak celé klece uvnitř jednotky a chybí jediné pole („innie“), je to pole rovno 45 minus součet klecí. Stejně to funguje pro dvě nebo tři jednotky dohromady (90, 135).rule of 45, innie, outie

Pravidlo 45\[ x_{\text{navíc}} = \sum_{\text{klece}} s_k - 45 \qquad\qquad x_{\text{chybějící}} = 45 - \sum_{\text{klece uvnitř}} s_k \]

Obr. 9.2 Pravidlo 45 v 1. bloku. Čtyři klece se součty 9, 8, 11 a 19 pokrývají celý blok a navíc pole ř1s4 (otazník). Dohromady 47, blok sám 45, takže ř1s4 = 47 − 45 = 2.

9.4Sudoku X, Windoku a Jigsaw

Sudoku X přidává podmínku, že se číslice neopakují ani na dvou hlavních diagonálách. Pole na diagonále tím získá až 12 sousedů navíc: středové pole jich má 32. Windoku (také Hyper sudoku) přidává čtyři okna 3 × 3 posunutá o jedno pole od rohů. Jigsaw nahrazuje bloky devíti nepravidelnými oblastmi po devíti polích; techniky z kapitol 2 až 8 fungují dál, jen „blok“ je jiný tvar.sudoku X, windoku (hyper sudoku), jigsaw sudoku

Obr. 9.3 Čtyři varianty. Sudoku X: diagonály čárkovaně. Windoku: čtyři podbarvená okna. Jigsaw: devět nepravidelných oblastí (jedno pevné rozložení z laboratoře). Mini 6 × 6: šest bloků 2 × 3, čísla 1 až 6.

**Tab. 9.2**Kolik sousedů má pole v jednotlivých variantách (spočítáno v laboratoři)
Varianta	Polí	Oblastí	Sousedů min.	max.	průměr
klasické 9 × 9	81	27	20	20	20,00
Sudoku X	81	29	20	32	21,33
Windoku	81	31	20	24	21,58
Jigsaw (ukázka)	81	27	16	22	20,12
Killer (ukázka, 31 klecí)	81	58	20	22	20,15
mini 6 × 6	36	18	12	12	12,00
mini 4 × 4	16	12	7	7	7,00

V Jigsaw má pole méně sousedů, když jeho oblast leží hodně v jeho řádku nebo sloupci – pak se jednotky „překrývají“ a nepřinášejí tolik nových polí.

9.5Mini sudoku 6 × 6 a 4 × 4

Pro děti a začátečníky jsou mřížky 6 × 6 (bloky 2 × 3, číslice 1–6) a 4 × 4 (bloky 2 × 2, číslice 1–4). Mají stejnou logiku, jen méně polí: pole 6 × 6 má 12 sousedů, pole 4 × 4 sedm. Úplných mřížek 4 × 4 je jen 288 a 6 × 6 je jich 28 200 960 – kapitola 10 je nechá spočítat. Malé mřížky jsou ideální na první skenování: dítě se naučí hledat „kam ještě může jednička“ bez zahlcení.

Příklad Dvě klece v jednom řádku

V 1. řádku leží celé tři klece se součty 17, 9 a 12 a jedno pole řádku patří do klece, která pokračuje dolů. Klece uvnitř řádku dávají 17 + 9 + 12 = 38, takže zbývající pole řádku obsahuje 45 − 38 = 7 – bez ohledu na to, jaký součet má klec, která z řádku vede ven.

Pozor

V Killer sudoku se číslice nesmí opakovat v kleci, i když klec leží přes dva bloky. Častá chyba: klec se dvěma poli a součtem 8 „4 + 4“. Správně jsou jen 1 + 7, 2 + 6 a 3 + 5.

9.6Procvičení

Dvoupolová klec má součet 16. Které číslice v ní jsou?

Jediná sada: 7 a 9. (8 + 8 je zakázané opakování.)

Kolik sad má třípolová klec se součtem 15? Je nějaká číslice, která musí být ve všech?

Osm sad: 159, 168, 249, 258, 267, 348, 357, 456. Žádná číslice není ve všech – pomůže až vyloučení číslic, které v řádku nebo bloku už jsou (vyzkoušejte v kalkulačce).

Čtyřpolová klec má součet 12. Které číslice v ní určitě jsou?

Sady jsou dvě: 1245 a 1236. Ve všech jsou 1 a 2; zbylá dvě pole jsou buď 4 a 5, nebo 3 a 6.

Kolik sad má klec se třemi poli a součtem 10? A kolik dvoupolová klec se součtem 10?

Trojice: 4 (127, 136, 145, 235). Dvojice: také 4 (19, 28, 37, 46) – součty 9, 10 a 11 mají u dvojic nejvíc sad.

Kolik sousedů má středové pole v Sudoku X a proč?

20 klasických sousedů plus 16 polí obou diagonál, z nichž 4 (ř4s4, ř4s6, ř6s4, ř6s6) už leží v jeho bloku: 20 + 16 − 4 = 32.

Klece pokrývají celý 9. řádek a dvě pole navíc ve 8. řádku. Součty klecí dávají 59. Co víte o dvou polích navíc?

Jejich součet je 59 − 45 = 14. Obě leží v 8. řádku, takže se liší: 7 + 7 nejde a zbývá 5 + 9 nebo 6 + 8.

Co si odnést

Killer: klece se součty, číslice se v kleci neopakují; krajní součty mají jedinou sadu.
Pravidlo 45: jednotka dává 45, takže pole navíc nebo chybějící pole se dopočítá.
Varianty přidávají oblasti (X, Windoku, klece) nebo mění jejich tvar (Jigsaw); techniky zůstávají stejné.

Matematika sudokumistr a věda

Kolik je vůbec různých vyplněných sudoku? Kolik z nich je „doopravdy“ jiných, a ne jen přeznačených nebo otočených? A kolik nejméně vodítek musí mít úloha s jediným řešením? Na tyto otázky odpověděli matematici mezi lety 2005 a 2012 – s pomocí počítačů, ale i chytrého počítání. Malé případy si spočítáte sami.

🔢

Úplných mřížek sudoku 9 × 9 je zhruba 6,67 · 10²¹ – kdyby každý z osmi miliard lidí vyplnil jednu mřížku za sekundu, trvalo by vypsat je všechny přes 26 000 let. A přitom latinských čtverců 9 × 9 (bez podmínky bloků) je ještě 828 186krát víc.

Počítadlo mřížek

Laboratoř poctivě prohledá všechny možnosti: u latinských čtverců zafixuje první řádek i sloupec (redukovaný čtverec), u sudoku první řádek, a výsledek vynásobí počtem přeznačení. Sledujte, jak rychle počty rostou, a porovnejte 4 × 4 a 6 × 6 s latinskými čtverci téže velikosti.

LABORATOŘ

Velikost latinského čtverce

Model: úplné prohledání s návratem (backtracking). Velikost 9 × 9 laboratoř nepočítá – ani s redukcí by to v prohlížeči nedoběhlo; hodnoty pro 7 × 7 až 9 × 9 v grafu jsou z literatury (OEIS A002860, Felgenhauer a Jarvis 2005). Sudoku 6 × 6 (672 849 uzlů) může trvat i několik sekund.

Laboratoř symetrií

Z jedné úlohy vyrobte ekvivalentní: přeznačte číslice, prohoďte řádky uvnitř pásu, celé pásy, sloupce, štoky, překlopte nebo otočte mřížku. Úloha vypadá jinak, ale počet vodítek, jednoznačnost i obtížnost zůstávají.

LABORATOŘ

Model: každá operace zachová pravidla sudoku – řádky zůstanou řádky, bloky bloky. Dole je úloha zapsaná jako 81 znaků (0 = prázdné pole), jak se úlohy předávají mezi programy.

+Teorie: latinské čtverce, počet mřížek, třídy ekvivalence, 17 vodítek a barvení grafu

10.1Latinské čtverce

Latinský čtverec řádu n je tabulka n × n vyplněná n symboly tak, že se v žádném řádku ani sloupci neopakují. Leonhard Euler o nich psal ve spisu E530 (předneseno 1779, vyšlo 1782). Každé vyplněné sudoku je latinský čtverec řádu 9 s podmínkou navíc – i bloky obsahují každou číslici jednou.Latin square, reduced Latin square

Čtverec, jehož první řádek i sloupec jsou 1, 2, …, n, je redukovaný. Z každého redukovaného se permutací sloupců a pak řádků 2 až n vyrobí n! · (n − 1)! různých čtverců a žádné dva se neopakují:

Počet latinských čtverců\[ L(n) = n!\,(n-1)!\,R(n), \qquad L(4) = 24 \cdot 6 \cdot 4 = 576 \]

**Tab. 10.1**Latinské čtverce a sudoku podle velikosti (OEIS A002860; malé případy ověřené laboratoří)
n	redukovaných R(n)	latinských čtverců L(n)	sudoku
2	1	2	–
3	1	12	–
4	4	576	288
5	56	161 280	–
6	9 408	812 851 200	28 200 960
7		61 479 419 904 000	–
8		≈ 1,088 · 10²⁰	–
9		≈ 5,525 · 10²⁷	≈ 6,671 · 10²¹

Sudoku 6 × 6 má bloky 2 × 3. Latinské čtverce 9 × 9 spočítali S. E. Bammel a J. Rothstein (1975).

Obr. 10.1 Počty latinských čtverců (modře) a sudoku (oranžově) na logaritmické ose. Podmínka bloků ubere u 4 × 4 polovinu, u 6 × 6 asi 96,5 % a u 9 × 9 všechny kromě zhruba jednoho čtverce z 828 186.

10.2Kolik je mřížek 9 × 9

Bertram Felgenhauer a Frazer Jarvis spočítali v roce 2005 všechny úplné mřížky sudoku. Postup: první blok lze přeznačením vždy převést na 1 2 3 / 4 5 6 / 7 8 9, takže stačí počítat mřížky s pevným prvním blokem a výsledek vynásobit 9!. Doplnit zbytek prvního pásu (tří řádků) jde 56 · 6⁶ = 2 612 736 způsoby – to laboratoř průvodce ověřila prohledáním. Pásy se pak roztřídí do 44 tříd, které mají stejný počet doplnění, a teprve ty dopočítal program.Felgenhauer, Jarvis 2005

Počet úplných mřížek sudoku\[ N_9 = 6\,670\,903\,752\,021\,072\,936\,960 = 9! \cdot 72^2 \cdot 2^7 \cdot 27\,704\,267\,971 \approx 6{,}671 \cdot 10^{21} \]

Poslední činitel 27 704 267 971 je prvočíslo – už nejde rozložit na další symetrie. Pro srovnání: latinských čtverců 9 × 9 je zhruba 828 186krát víc.

10.3Podstatně různé mřížky

Dvě mřížky jsou podstatně stejné, když jednu převedete na druhou operacemi z laboratoře symetrií. Geometrických operací je 6 permutací pásů, 6³ permutací řádků uvnitř pásů, totéž pro štoky a sloupce a transpozice – dohromady 2 · 6⁸ = 3 359 232; s přeznačením číslic (9!) to dává 1 218 998 108 160 operací.essentially different grids, Burnside's lemma

Grupa symetrií sudoku\[ |G| = \underbrace{2 \cdot 6^8}_{3\,359\,232} \cdot\ 9! = 1\,218\,998\,108\,160, \qquad \frac{N_9}{|G|} \approx 5\,472\,447\,994 \]

Pouhé vydělení ale nestačí, protože některé mřížky jsou souměrné – některá operace je převede samy na sebe, a jejich třída je proto menší. Ed Russell a Frazer Jarvis (2006) to vyřešili Burnsideovým lemmatem a dostali přesně 5 472 730 538 podstatně různých mřížek, o 282 544 víc než prosté dělení.

Obr. 10.2 U sudoku 4 × 4 je grupa symetrií jen 128 geometrických operací krát 4! = 3 072 a všech 288 mřížek spadne do dvou tříd: 96 mřížek je podstatně stejných jako levá, 192 jako pravá.

10.4Nejméně vodítek: 17

Úlohy se 17 vodítky jsou známé dlouho a nikdo nenašel úlohu s jediným řešením a 16 vodítky. V lednu 2012 zveřejnili Gary McGuire, Bastian Tugemann a Gilles Civario důkaz, že taková neexistuje: počítačem prošli všechny podstatně různé mřížky a v žádné nenašli 16 vodítek, která by určila celé řešení. Článek vyšel v roce 2014 v časopise Experimental Mathematics.minimum number of clues, unavoidable set, hitting set

Klíčem jsou nevyhnutelné množiny: skupiny polí, které lze v mřížce přeskládat a dostat jinou platnou mřížku. Nejmenší má čtyři pole – dvě číslice v rozích obdélníku přes dva řádky, dva sloupce a dva bloky (a b / b a). Pokud žádné z těch polí není vodítko, lze a s b prohodit a řešení není jediné. Úloha tedy musí „zasáhnout“ každou nevyhnutelnou množinu aspoň jedním vodítkem – a hledání takových zásahových množin (hitting sets) je jádro důkazu.

Mistrovská pomůcka

Jednoduchá dolní mez, kterou dokážete sami: v zadání s jediným řešením se musí objevit aspoň osm různých číslic. Kdyby chyběly dvě, například 4 a 7, můžete je v řešení všude prohodit a dostanete druhé řešení se stejnými vodítky.

10.5Sudoku jako barvení grafu

Udělejte z každého pole vrchol a spojte hranou každou dvojici sousedů. Vznikne graf sudoku s 81 vrcholy, každý má stupeň 20, takže hran je 81 · 20 / 2 = 810. Vyplněná mřížka je obarvení grafu devíti barvami, kde sousední vrcholy mají různé barvy, a úloha je částečné obarvení, které jde doplnit jediným způsobem. Herzberg a Murty (2007) touto cestou zkoumali počty doplnění pomocí chromatického polynomu.graph colouring, chromatic number

Graf sudoku\[ |V| = 81, \qquad \deg v = 8 + 8 + 4 = 20, \qquad |E| = \frac{81 \cdot 20}{2} = 810, \qquad \chi = 9 \]

Příklad 288 mřížek 4 × 4

První řádek je 1 2 3 4 (ostatní se dostanou přeznačením, 4! = 24 možností). Laboratoř pak najde 12 doplnění a prohledávání při tom projde 112 uzlů. Celkem 12 · 24 = 288. U 6 × 6 s prvním řádkem 1 až 6 je doplnění 39 168, celkem 39 168 · 720 = 28 200 960.

Pozor

Počet mřížek (6,67 · 10²¹) není počet úloh. Z jedné mřížky jde vyrobit obrovské množství úloh s různými vodítky a ne všechny mají jediné řešení. Kolik je úloh, se přesně neví.

10.6Procvičení

Kolik je latinských čtverců 3 × 3?

Redukovaný je jen jeden (1 2 3 / 2 3 1 / 3 1 2), takže L(3) = 3! · 2! · 1 = 12.

Proč mají latinské čtverce 4 × 4 právě dvakrát víc možností než sudoku 4 × 4?

576 / 288 = 2. Podmínka bloků 2 × 2 vyřadí přesně polovinu latinských čtverců – to laboratoř ukáže, když přepnete mezi „latinské čtverce“ (velikost 4) a „sudoku 4 × 4“.

Kolik geometrických operací (bez přeznačení číslic) má sudoku 9 × 9?

Pásy 3! = 6, řádky uvnitř tří pásů 6³, štoky 6, sloupce 6³ a transpozice ×2: 2 · 6⁸ = 3 359 232.

Kolik hran má graf sudoku 4 × 4?

Každé pole má 3 + 3 + 1 = 7 sousedů, takže 16 · 7 / 2 = 56 hran.

Zadání obsahuje 20 vodítek, ale chybí v něm všechny dvojky a pětky. Může mít jediné řešení?

Ne. V každém řešení lze dvojky a pětky prohodit a vodítka se nezmění – úloha má aspoň dvě řešení.

Odhad počtu podstatně různých mřížek dělením je 5 472 447 994, skutečnost 5 472 730 538. Proč je skutečnost větší?

Souměrné mřížky se při dělení „započítají jen zlomkem“, protože je některé operace nechají beze změny a jejich třída má méně prvků než |G|. Burnsideovo lemma je počítá správně a výsledek je o 282 544 vyšší.

Co si odnést

Úplných mřížek 9 × 9 je 6 670 903 752 021 072 936 960 (Felgenhauer a Jarvis 2005), podstatně různých 5 472 730 538 (Russell a Jarvis 2006).
Nejméně vodítek pro jediné řešení je 17 (McGuire, Tugemann a Civario, 2012).
Sudoku je obarvení grafu s 81 vrcholy a 810 hranami devíti barvami; malé případy (4 × 4 = 288) se dají spočítat ručně.

Algoritmy: jak sudoku řeší počítačmistr a věda

Počítač nepotřebuje X-wing. Stačí mu zkoušet číslice a vracet se, když narazí na spor – backtracking. Jenže dobře zvolené pořadí zkoušení ušetří stovky až desetitisíce kroků. Kapitola srovná čtyři strategie na skutečných úlohách, ukáže sudoku jako úlohu přesného pokrytí (Knuthův Algoritmus X) a jako logickou formuli pro SAT řešič a vysvětlí, proč je zobecněné sudoku NP-úplné.

🤖

Představte si bludiště, ve kterém na každé křižovatce zkusíte nejdřív levou chodbu. Když narazíte na zeď, vrátíte se k poslední křižovatce a zkusíte další. Takhle se dostanete ven vždycky – otázka je jen, za jak dlouho. A chytrý průzkumník začne tam, kde má nejmíň možností.

Backtracking pod lupou

Vyberte úlohu a strategii. Laboratoř úlohu vyřeší a spočítá uzly – kolikrát zkusila zapsat číslici. Graf porovná všechny čtyři strategie. „Přehrát“ ukáže hledání krok za krokem: oranžově zkoušená číslice, zeleně doplnění vynucené nahým singlem, červeně návrat.

LABORATOŘ

Rychlost přehrávání

Model: „naivně“ = první prázdné pole zleva shora, číslice od 1 do 9. MRV = pole s nejméně možnostmi. „+ nahé singly“ = po každém zápisu se doplní všechna pole s jedinou možností. Algoritmus X = přesné pokrytí, vždy podmínka s nejméně možnostmi. „Ověřit jednoznačnost“ hledá i druhé řešení, takže musí projít celý strom.

Matice exact cover 4 × 4

Každý řádek matice je jedna volba „pole + číslice“ (64 řádků), každý sloupec jedna podmínka (64 sloupců). Krokujte Algoritmus X: vybere sloupec s nejméně jedničkami, zkusí jeden jeho řádek a odstraní všechny sloupce, které řádek pokrývá, i řádky, které s ním kolidují. Když nějaký sloupec zůstane bez jedniček, vrací se.

LABORATOŘ

Model: matice 64 × 64 s 256 jedničkami (každý řádek má čtyři: pole, řádek + číslice, sloupec + číslice, blok + číslice). Šedé sloupce a řádky jsou odstraněné, oranžové řádky vybrané, modrý sloupec se právě zpracovává. U úlohy s vodítky vede pravidlo „nejméně jedniček“ k řešení bez jediné slepé uličky; „první volný sloupec“ jich udělá tři.

+Teorie: backtracking, MRV, propagace, exact cover a Dancing Links, SAT a NP-úplnost

11.1Backtracking

Najdi prázdné pole, zapiš první číslici, která neporušuje pravidla, a pokračuj dalším polem. Když nějaké pole nemá žádnou možnost, vrať se k poslednímu zápisu a zkus tam další číslici. Algoritmus prochází strom prohledávání: každý uzel je jeden zkušební zápis, každý list buď řešení, nebo slepá ulička.backtracking, search tree, node, dead end

Obr. 11.1 Celý strom naivního backtrackingu pro úlohu 4 × 4 se sedmi vodítky a devíti prázdnými poli. Projde 12 uzlů. Zápis ř1s2 = 2 hned vede do slepé uličky (pole ř1s3 pak nemá žádnou možnost), ř1s2 = 3 pokračuje. Druhá slepá ulička: po ř3s1 = 2 a ř3s2 = 1 nemá možnost pole ř3s4, takže se algoritmus vrátí a ř3s1 = 3 už vede k řešení 1324 / 4213 / 3142 / 2431.

11.2MRV a propagace omezení

Naivní pořadí je hloupé: zkouší pole s devíti možnostmi, i když vedle je pole s jedinou. Heuristika MRV (minimum remaining values) jde vždy do pole s nejméně možnostmi – pole s jednou možností je vlastně nahý singl, pole bez možnosti okamžitý spor. Propagace omezení jde dál: po každém zápisu doplní všechny nahé singly, dokud nějaké jsou, a teprve pak se větví. Člověk dělá totéž – jen jeho propagace je bohatší o techniky z kapitol 2 až 8.minimum remaining values, constraint propagation

Obr. 11.2 Uzly do prvního řešení pro tři úlohy z laboratoře (logaritmická osa). U těžší úlohy klesne počet z 34 108 (naivně) na 174 s MRV a na 20 s propagací nahých singlů. Pozor na prostřední a pravou skupinu: úloha „mimo škálu technik“ dá naivnímu backtrackingu méně práce (3 058 uzlů) než úloha úrovně 4 – obtížnost pro člověka a pro počítač jsou různé věci.

**Tab. 11.1**Uzly prohledávání (do prvního řešení | do ověření jednoznačnosti), spočítáno v laboratoři
Úloha	Vodítek	naivně	MRV	MRV + nahé singly	Algoritmus X
lehká (úroveň 1)	30	3 253 \| 10 783	106 \| 157	10 \| 16	51 \| 51
těžší (úroveň 4)	27	34 108 \| 46 123	174 \| 442	20 \| 66	81 \| 111
mimo škálu	28	3 058 \| 3 139	135 \| 205	9 \| 16	107 \| 107

U propagace se nepočítají vynucená doplnění (lehká úloha 80, těžší 137, mimo škálu 102 v průběhu celého hledání). Algoritmus X počítá každé zapsané pole jako uzel, i když je vynucené: lehká úloha má 51 prázdných polí a 51 uzlů, tedy ani jednu slepou uličku.

11.3Exact cover a Algoritmus X

Úloha přesného pokrytí: je dána matice nul a jedniček a máme vybrat řádky tak, aby v každém sloupci byla právě jedna jednička. Sudoku 9 × 9 se převede na matici 729 × 324: řádek je volba „pole ř, s má číslici d“ (9 · 9 · 9 = 729), sloupec je podmínka – každé pole má číslici (81), každý řádek, sloupec i blok má každou číslici (3 · 81). Každý řádek matice má čtyři jedničky, celkem jich je 2 916.exact cover, Algorithm X, Dancing Links (DLX)

Sudoku jako přesné pokrytí\[ 9^3 = 729 \text{ řádků}, \qquad 4 \cdot 81 = 324 \text{ sloupců}, \qquad 729 \cdot 4 = 2\,916 \text{ jedniček} \]

Donald Knuth popsal v článku Dancing Links (2000) Algoritmus X: vyber sloupec s nejméně jedničkami, zkus postupně jeho řádky, odstraň pokryté sloupce a kolidující řádky a pokračuj rekurzivně. „Tančící odkazy“ jsou trik s dvojitě propojenými seznamy, díky kterému jde odstraněný řádek vrátit zpět v konstantním čase. Sloupec s jedinou jedničkou je přitom buď nahý singl (podmínka „pole“), nebo skrytý singl (podmínka „řádek + číslice“ a další) – Algoritmus X tedy umí oba singly zadarmo.

11.4Převod na SAT

Proměnná x_r,s,d říká „v poli ř, s je číslice d“ – je jich 729. Pravidla se zapíšou jako klauzule (disjunkce): každé pole má aspoň jednu číslici (81 klauzulí) a žádná číslice není v řádku, sloupci či bloku dvakrát (pro každou jednotku a číslici 36 dvojic, celkem 3 · 81 · 36 = 8 748 klauzulí). Vodítka jsou jednotkové klauzule. Moderní SAT řešič takovou formuli vyřeší okamžitě.Boolean satisfiability (SAT), CNF, clause

Minimální a rozšířené kódování (počty klauzulí bez vodítek)\[ 81 + 3 \cdot 81 \cdot 36 = 8\,829, \qquad 8\,829 + 81 \cdot 36 + 3 \cdot 81 = 11\,988 \]

Rozšířené kódování přidává nadbytečné, ale pro řešič užitečné klauzule: každé pole má nejvýš jednu číslici a každá číslice je v každé jednotce aspoň jednou. To je přesně informace, ze které vznikají nahé a skryté singly.

11.5NP-úplnost

Sudoku 9 × 9 je pro počítač snadné, protože je malé. Zobecněné sudoku n² × n² (bloky n × n) je ale NP-úplné: Takayuki Yato a Takahiro Seta (2003) ukázali, že rozhodnout, zda má částečně vyplněná mřížka řešení, je stejně těžké jako nejtěžší úlohy třídy NP. Dokázali navíc, že i úloha „najdi jiné řešení, když jedno znáš“ je těžká (ASP-úplnost). Pro tvůrce úloh to znamená, že na ověření jednoznačnosti velkých sudoku neexistuje známá rychlá zkratka.NP-complete, ASP-complete

Mistrovská pomůcka

Hádání v soutěži se nevyplácí, ale když už, hádejte jako MRV: v poli se dvěma kandidáty (bivalue). Jeden ze dvou pokusů je správný a špatný se obvykle rychle prozradí sporem.

Příklad Matice 4 × 4

Pro sudoku 4 × 4 má matice 4³ = 64 řádků a 4 · 16 = 64 sloupců s 256 jedničkami. Úloha z laboratoře má 4 vodítka a 12 prázdných polí; Algoritmus X s pravidlem „nejméně jedniček“ udělá právě 12 výběrů bez návratu. Na prázdné mřížce najde všech 288 řešení přes 2 156 výběrů.

Pozor

Malý počet uzlů neznamená lehkou úlohu pro člověka a naopak. Počítač je rychlý v hádání s návratem, člověk v hledání vzorů. Obtížnost pro lidi se proto hodnotí podle potřebných technik (kapitola 12), ne podle času řešiče.

11.6Procvičení

Kolik slepých uliček udělal naivní backtracking ve stromu z obr. 11.1?

Dvě (po ř1s2 = 2 a po ř3s2 = 1). Celkem 12 uzlů: 9 na cestě k řešení a 3 zbytečné (ř1s2 = 2, ř3s1 = 2, ř3s2 = 1).

Proč musí ověření jednoznačnosti projít víc uzlů než hledání prvního řešení?

Po nalezení řešení musí algoritmus pokračovat a vyloučit všechny zbylé větve – teprve pak ví, že druhé řešení není. U těžší úlohy to je 442 místo 174 uzlů (MRV).

Kolik řádků a sloupců má matice exact cover pro sudoku 6 × 6?

6³ = 216 řádků a 4 · 36 = 144 sloupců, v každém řádku čtyři jedničky (864 celkem).

Kolik binárních klauzulí „číslice d není v řádku dvakrát“ je potřeba pro jeden řádek a jednu číslici?

Každá dvojice polí řádku: C(9, 2) = 36. Pro všechny řádky, sloupce, bloky a číslice 3 · 81 · 36 = 8 748.

Lehká úloha úrovně 1 jde vyřešit jen singly. Proč přesto MRV potřebuje 106 uzlů, a ne 51?

MRV vidí jen nahé singly (pole s jednou možností). Úroveň 1 ale potřebuje i skryté singly v blocích; kde žádný nahý singl není, MRV musí hádat ze dvou možností a občas se vrací (55 slepých uliček). Algoritmus X vidí oba druhy singlů, a proto má přesně 51 uzlů.

Znamená NP-úplnost, že sudoku 9 × 9 je pro počítač těžké?

Ne. NP-úplnost mluví o růstu náročnosti s velikostí n. Pevná velikost 9 × 9 je vždy vyřešená za zlomek sekundy – laboratoř ji vyřeší nanejvýš za desítky milisekund.

Co si odnést

Backtracking najde řešení vždy; MRV a propagace omezení zmenší strom o několik řádů.
Sudoku je přesné pokrytí (729 × 324) – Knuthův Algoritmus X s Dancing Links; jde zapsat i jako SAT (729 proměnných).
Zobecněné sudoku je NP-úplné (Yato a Seta 2003); obtížnost pro člověka a pro počítač se liší.

Tvorba úloh, obtížnost a soutěžemistr a věda

Dobrá úloha má jediné řešení a dá se vyřešit úvahou bez hádání. Kapitola ukazuje, jak taková úloha vzniká – od úplné mřížky po minimální zadání –, jak se obtížnost hodnotí podle nejtěžší potřebné techniky a proč počet vodítek skoro nic neříká. Na konci jsou mistrovství světa, kde se Češi drží mezi nejlepšími, a rady k tréninku rychlosti.

🏗️

Sochař nepřidává hlínu, ale odsekává kámen. Tvůrce sudoku taky: začne s plnou mřížkou a ubírá číslice, dokud řešení zůstává jediné. Když už nejde ubrat nic, je úloha hotová – a teprve pak se ukáže, jak je těžká.

Generátor: ubírej, dokud je řešení jediné

Laboratoř vezme náhodnou úplnou mřížku a v náhodném pořadí zkouší ubírat vodítka (podle zvolené symetrie po dvojicích). Zeleně ubrané pole, červeně pole, které musí zůstat – bez něj by úloha měla víc řešení. Na konci řešitel úlohu ohodnotí.

LABORATOŘ

Model: jednoznačnost se po každém ubrání ověřuje backtrackingem, který hledá dvě řešení (kapitola 11). Výsledná úloha je minimální vzhledem ke zvolené symetrii: žádnou další skupinu vodítek nejde ubrat. Hodnocení je nejvyšší úroveň techniky, kterou řešitel průvodce potřeboval.

Hodnotitel obtížnosti

Vložte úlohu jako 81 znaků (řádky za sebou, prázdné pole 0 nebo tečka) – třeba z novin nebo z laboratoře symetrií. Hodnotitel ověří jednoznačnost, úlohu vyřeší logikou a vypíše, které techniky a kolikrát potřeboval, s odkazem na kapitolu.

LABORATOŘ

Zadání (81 znaků)

Model: řešitel vždy použije nejlehčí dostupnou techniku (pořadí z kapitol 2 až 8) a úroveň úlohy je maximum úrovní použitých technik. Úlohy, na které nestačí, označí „mimo škálu“.

Minihra: Odhadni obtížnost

Prohlédněte si úlohu a odhadněte, jakou úroveň 1–5 jí přidělí řešitel. Hodnocení a použité techniky se ukážou až po odpovědi. Kolo má pět úloh, za aspoň tři přesné odhady získáte 15 XP.

MINIHRA

0 / 5

+Teorie: generátor, hodnocení technikami, symetrie, mistrovství světa a trénink

12.1Jak vzniká úloha

Běžný postup má tři kroky. (1) Náhodná úplná mřížka: backtracking z kapitoly 11, který zkouší číslice v náhodném pořadí. (2) Ubírání vodítek: v náhodném pořadí se zkusí pole vymazat a ověří se, že úloha má pořád jediné řešení; když ne, číslice se vrátí. (3) Hodnocení: logický řešitel úlohu vyřeší a podle nejtěžší potřebné techniky jí přidělí úroveň. Když úroveň nesedí, generátor zkusí jinou mřížku nebo jiné pořadí.puzzle generator, minimal puzzle

Výsledek je minimální úloha: žádné další vodítko nejde ubrat. To ale neznamená nejmenší možnou – z jiné mřížky nebo při jiném pořadí ubírání by mohla vyjít úloha s méně vodítky. Úlohy se 17 vodítky (kapitola 10) náhodný generátor prakticky nenajde; v bance průvodce mělo 6 000 úloh nejméně 22 vodítek. Stejné zadání pro všechny v jeden den se dá zařídit tak, že generátor dostane semínko náhody odvozené z data.

12.2Obtížnost podle technik

Pro člověka je úloha tak těžká, jak těžkou techniku potřebuje. Řešitel průvodce zkouší techniky od nejlehčí a úroveň úlohy je nejvyšší úroveň, kterou musel použít: 1 = skryté singly v blocích a nahé singly, 2 = skryté singly v řádcích a sloupcích, 3 = zamčení kandidáti a dvojice, 4 = trojice, čtveřice, X-wing a křídla, 5 = Swordfish, Jellyfish, barvení a řetězy. Na zbytek („mimo škálu“) by byly potřeba techniky nad rámec průvodce, například unikátní obdélník, množiny ALS nebo delší řetězy.difficulty rating

Obr. 12.1 Banka průvodce: 6 000 náhodně vygenerovaných minimálních úloh se středovou symetrií, roztříděných podle nejtěžší potřebné techniky. Dvě třetiny (66,60 %) stačí vyřešit singly, 5,97 % je mimo škálu. Průměrný počet vodítek se mezi úrovněmi 1 až 5 liší jen o 0,6.

**Tab. 12.1**Jak často řešitel techniku v bance 6 000 úloh použil aspoň jednou
Technika	Úroveň	Podíl úloh	Technika	Úroveň	Podíl úloh
skrytý singl v bloku	1	99,98 %	X-wing	4	4,15 %
nahý singl	1	85,53 %	XY-wing	4	8,90 %
skrytý singl v řádku nebo sloupci	2	50,72 %	XYZ-wing	4	4,07 %
zamčení kandidáti – ukazující	3	28,43 %	W-wing	4	10,12 %
zamčení kandidáti – nárokující	3	12,42 %	Swordfish	5	0,48 %
nahá dvojice	3	12,22 %	Jellyfish	5	0,03 %
skrytá dvojice	3	7,50 %	jednoduché barvení	5	5,88 %
nahá trojice	4	1,88 %	X-řetěz	5	4,62 %
skrytá trojice	4	0,45 %	XY-řetěz	5	5,50 %
nahá čtveřice	4	0,05 %

Řešitel zkouší techniky v pevném pořadí, takže čísla platí pro toto pořadí. Jiný řešitel může místo XY-wingu použít třeba barvení. Skrytou čtveřici nepotřebovala žádná úloha.

Příklad Vodítka a obtížnost

Průměrný počet vodítek je na úrovni 1 27,77, na úrovni 4 27,53 a mimo škálu 27,19. Rozdíly jsou zlomky jednoho vodítka, zatímco náročnost se liší o celé kapitoly. Úloha s 24 vodítky může být lehká a úloha s 30 vodítky těžká.

12.3Symetrie vodítek

Úlohy v novinách i na soutěžích mají vodítka většinou rozmístěná souměrně, nejčastěji středově (pole ř, s a 10 − ř, 10 − s jsou buď obě vodítka, nebo obě prázdná). Je to estetická tradice spojovaná hlavně s japonským vydavatelem Nikoli; na řešení nemá vliv. Generátor pak ubírá vodítka po dvojicích, takže výsledek má obvykle o něco víc vodítek než úloha bez symetrie.clue symmetry

Obr. 12.2 Čtyři úlohy z generátoru (vodítka podbarvená): bez symetrie 23 vodítek, středová 28, zrcadlová podle svislé osy 25 a diagonální 26. Bez symetrie a diagonální vyšly mimo škálu, středová a zrcadlová na úrovni 1 – obtížnost se symetrií nesouvisí.

12.4Mistrovství světa v sudoku

Mistrovství světa v sudoku (WSC) pořádá od roku 2006 Světová hádankářská federace (WPF). Soutěží se v kolech s různými variantami – klasické, Killer, Sudoku X, Jigsaw a desítky dalších – a jednotlivci i státní týmy. První mistrovství se konalo 10.–11. 3. 2006 v italské Lucce a vyhrála ho Češka Jana Tylová. Česko je od té doby stálou velmocí: týmové zlato v letech 2008, 2016 a 2022, individuální medaile Jakuba Ondrouška (stříbro 2010 a 2016, bronz 2008, 2013, 2014 (dělený) a 2015) a Roberta Babilona (bronz 2009). Mistrovství republiky pořádá HALAS – Hráčská asociace logických her a sudoku.World Sudoku Championship (WSC), World Puzzle Federation (WPF)

**Tab. 12.2**Mistrovství světa v sudoku – místa a vítězové jednotlivců
Rok	Místo	Vítěz	Rok	Místo	Vítěz
2006	Lucca	Jana Tylová (CZ)	2016	Senec	Tiit Vunk (EE)
2007	Praha	Thomas Snyder (US)	2017	Bengalúru	Kota Morinishi (JP)
2008	Goa	Thomas Snyder (US)	2018	Praha	Kota Morinishi (JP)
2009	Žilina	Jan Mrozowski (PL)	2019	Kirchheim	Ken Endo (JP)
2010	Filadelfie	Jan Mrozowski (PL)	2022	Krakov	Tiit Vunk (EE)
2011	Eger	Thomas Snyder (US)	2023	Toronto	Dai Tantan (CN)
2012	Kraljevica	Jan Mrozowski (PL)	2024	Peking	Ming Letian (CN)
2013	Peking	Jin Ce (CN)	2025	Eger	Dai Tantan (CN)
2014	Londýn	Kota Morinishi (JP)	2026	Kalkata	(19. ročník, 11.–18. 10. 2026)
2015	Sofie	Kota Morinishi (JP)

V letech 2020 a 2021 se mistrovství kvůli pandemii nekonalo. Výsledky ročníku 2026 se nám v době ověření nepodařilo spolehlivě potvrdit. Zdroje v příloze C.

12.5Trénink rychlosti

Rychlost nevzniká rychlejším psaním, ale tím, že řešitel méně hledá naslepo. Osvědčené zásady:

Skenujte systematicky: číslici po číslici (1 až 9) křížovým skenováním přes pásy a štoky, ne pole po poli.
Kandidáty pište co nejpozději a úsporně – nejdřív jen rohové poznámky pro dvě místa v bloku (Snyderova notace, kapitola 3), plné kandidáty až tehdy, když singly dojdou.
Trénujte po úrovních: dokud úroveň 1 netrvá pár minut, nemá smysl honit X-wing. Minihry v kapitolách 2, 4 a 6 trénují právě rozpoznání vzoru.
Kontrolujte průběžně: jedna chyba z nepozornosti stojí víc času než deset pomalých kroků. Na soutěžích se za chybné řešení body nedávají.
Hrajte s mírou: krátké denní řešení udrží pozornost lépe než maratony. Sudoku je hra pro radost, ne o peníze.

Mistrovská pomůcka

Soutěžní řešitelé si před kolem projdou všechny úlohy a pořadí volí podle bodů za minutu. Lehkou úlohu se 100 body za 4 minuty je lepší vyřešit dřív než těžkou se 150 body za 10 minut. To se hodí i doma: když se zaseknete, odložte úlohu a vraťte se k ní s čerstvou hlavou.

Pozor

Úloha z generátoru bez kontroly jednoznačnosti není sudoku. Pokud má víc řešení, řešitel musí v některém okamžiku hádat a „správné“ řešení je jen to, které si autor náhodou zvolil. Hodnotitel výše takové zadání odhalí.

12.6Procvičení

Úloha se středovou symetrií má 27 vodítek. Je středové pole ř5s5 vodítkem?

Ano. Všechna ostatní pole tvoří dvojice (ř, s) a (10 − ř, 10 − s), takže vodítek mimo střed je sudý počet. Lichých 27 znamená, že vodítkem je i střed.

Jaký podíl úloh z banky potřebuje víc než singly (úroveň 3 a výš včetně „mimo škálu“)?

(582 + 555 + 509 + 358) / 6 000 = 2 004 / 6 000 = 33,40 %, tedy zhruba každá třetí.

Generátor ubral všechno, co šlo, a vyšlo 24 vodítek. Existuje z téže mřížky úloha s méně vodítky?

Možná ano. Minimální (nejde nic ubrat) neznamená nejmenší. Jiné pořadí ubírání by mohlo skončit u jiné minimální úlohy s méně vodítky.

Kolik úloh z banky by šlo vyřešit jen skrytými singly v blocích a nahými singly?

Úroveň 1: 2 608 z 6 000, tedy 43,47 %.

Kolikrát vyhrál mistrovství světa v sudoku Kota Morinishi a v kterých letech?

Čtyřikrát: 2014 Londýn, 2015 Sofie, 2017 Bengalúru a 2018 Praha.

Proč hodnotitel nehodnotí obtížnost podle počtu uzlů backtrackingu?

Počítač a člověk řeší jinak. V kapitole 11 dala úloha „mimo škálu“ naivnímu backtrackingu méně práce (3 058 uzlů) než úloha úrovně 4 (34 108). Člověk ale hádat nechce – rozhoduje, jaký vzor musí najít.

Co si odnést

Úloha vzniká z plné mřížky ubíráním vodítek s kontrolou jednoznačnosti; výsledek je minimální, ne nejmenší.
Obtížnost určuje nejtěžší potřebná technika, ne počet vodítek; symetrie je estetika.
Mistrovství světa se koná od roku 2006, první vyhrála Jana Tylová a Česko patří k nejlepším týmům.

PřílohaA

Slovníček

Česká hesla s anglickým termínem. Hledat lze v obou jazycích.

PřílohaB

Vzorce a přehledy

Techniky podle úrovní

**Tab. B.1**Úrovně obtížnosti průvodce a hry (řešitel zkouší techniky v tomto pořadí)
Úroveň	Techniky	Kapitola
1	skrytý singl v bloku, nahý singl	2
2	skrytý singl v řádku nebo sloupci	2
3	zamčení kandidáti (ukazující, nárokující), nahá a skrytá dvojice	4, 5
4	nahá a skrytá trojice a čtveřice, X-wing, XY-wing, XYZ-wing, W-wing	5, 6, 7
5	Swordfish, Jellyfish, jednoduché barvení, X-řetěz, XY-řetěz	6, 8
mimo škálu	techniky nad rámec průvodce (ryby s ploutví, unikátní obdélník, ALS, delší řetězy)	–

Vzorce na jednom místě

Sousedé pole (kap. 1)\[ |P(p)| = 8 + 8 + 4 = 20, \qquad 27 \text{ jednotek}, \qquad 81 \cdot 20 / 2 = 810 \text{ dvojic sousedů} \]

Skrytý singl (kap. 2)\[ \big|\{\,p \in U : d \in K(p)\,\}\big| = 1 \ \Rightarrow\ \text{to jediné pole je } d \]

Zamčení kandidáti (kap. 4)\[ K_d(A) \subseteq A \cap B \ \Rightarrow\ d \notin K(p)\quad \text{pro } p \in B \setminus A \]

Nahá podmnožina (kap. 5)\[ |C| = k,\ \Big|\bigcup_{p \in C} K(p)\Big| = k \ \Rightarrow\ \text{tyto číslice ve zbytku jednotky škrtneme} \]

Ryba velikosti n (kap. 6)\[ \bigcup_{r \in B} K_d(r) \subseteq \bigcup_{c \in C} c,\ |B| = |C| = n \ \Rightarrow\ d \text{ škrtneme v krycích liniích mimo rybu} \]

Řetěz se střídavými vazbami (kap. 8)\[ A = B - C = D \ \Rightarrow\ A \vee D \ \Rightarrow\ d \notin K(p)\ \ \text{pro } p \in P(A) \cap P(D) \]

Killer: rozsah součtů a pravidlo 45 (kap. 9)\[ \frac{n(n+1)}{2} \le s \le \frac{n(19-n)}{2}, \qquad x_{\text{navíc}} = \sum s_k - 45 \]

Latinské čtverce a sudoku (kap. 10)\[ L(n) = n!\,(n-1)!\,R(n), \qquad N_9 = 9! \cdot 72^2 \cdot 2^7 \cdot 27\,704\,267\,971, \qquad |G| = 2 \cdot 6^8 \cdot 9! \]

Exact cover a SAT (kap. 11)\[ 729 \times 324,\ 2\,916 \text{ jedniček}; \qquad 729 \text{ proměnných},\ 81 + 3 \cdot 81 \cdot 36 = 8\,829 \text{ klauzulí} \]

Killer: součty s jedinou sadou

**Tab. B.2**Součty klecí, které mají jedinou možnou sadu číslic (spočítáno výčtem)
Polí	Součet → sada
2	3 → 12, 4 → 13, 16 → 79, 17 → 89
3	6 → 123, 7 → 124, 23 → 689, 24 → 789
4	10 → 1234, 11 → 1235, 29 → 5789, 30 → 6789
5	15 → 12345, 16 → 12346, 34 → 46789, 35 → 56789
6	21 → 123456, 22 → 123457, 38 → 356789, 39 → 456789
7	28 → 1234567, 29 → 1234568, 41 → 2456789, 42 → 3456789
8	36 až 44: chybí číslice 45 − s
9	45 → 123456789

Počty na jednom místě

**Tab. B.3**Čísla z kapitol 9 až 12
Údaj	Hodnota	Zdroj
úplné mřížky 9 × 9	6 670 903 752 021 072 936 960	Felgenhauer a Jarvis 2005
podstatně různé mřížky 9 × 9	5 472 730 538	Russell a Jarvis 2006
nejmenší počet vodítek	17	McGuire, Tugemann, Civario 2012
mřížky 4 × 4 / 6 × 6 (bloky 2 × 3)	288 / 28 200 960	laboratoř 10.1
latinské čtverce 9 × 9	5 524 751 496 156 892 842 531 225 600	OEIS A002860
symetrie (geometrické / s přeznačením)	3 359 232 / 1 218 998 108 160	výpočet
banka průvodce: úroveň 1 / 2 / 3 / 4 / 5 / mimo	2 608 / 1 388 / 582 / 555 / 509 / 358	6 000 úloh, kap. 12

PřílohaC

Zdroje a předpoklady

Historické údaje, matematické výsledky a výsledky soutěží byly ověřeny na uvedených zdrojích. Ověřeno 7. 11. 2026.

Historie hry

Euler, L.: Recherches sur une nouvelle espèce de quarrés magiques (Eneström E530). Verhandelingen uitgegeven door het Zeeuwsch Genootschap der Wetenschappen te Vlissingen 9 (1782), s. 85–239; předneseno 8. 3. 1779. Ověřeno 7. 11. 2026.
Hádanky v deníku Le Siècle (19. 11. 1892) a La France (6. 7. 1895); Number Place v časopisech Dell Magazines 1979 (Howard Garns); Nikoli duben 1984 („Sūji wa dokushin ni kagiru“); The Times 12. 11. 2004 (úlohy Wayna Goulda): encyklopedické heslo Sudoku (Wikipedie, anglická verze) a prameny v něm citované. Ověřeno 7. 11. 2026.
Maki Kadži (Maki Kaji, 8. 10. 1951 – 10. 8. 2021), zakladatel nakladatelství Nikoli: encyklopedické heslo Maki Kaji a zprávy o jeho úmrtí ze srpna 2021. Ověřeno 7. 11. 2026.

Matematika a algoritmy

Felgenhauer, B.; Jarvis, F. (2005): Enumerating possible Sudoku grids a navazující text Mathematics of Sudoku I; Russell, E.; Jarvis, F. (2006): Mathematics of Sudoku II – 6 670 903 752 021 072 936 960 mřížek, 5 472 730 538 podstatně různých. Stránka F. Jarvise afjarvis.org.uk/sudoku a OEIS A107739. Ověřeno 7. 11. 2026.
OEIS A002860 (počet latinských čtverců řádu n); Bammel, S. E.; Rothstein, J. (1975): The number of 9 × 9 Latin squares. Discrete Mathematics 11, 93–95. Ověřeno 7. 11. 2026.
McGuire, G.; Tugemann, B.; Civario, G. (2014): There is no 16-clue Sudoku: Solving the Sudoku minimum number of clues problem via hitting set enumeration. Experimental Mathematics 23(2), 190–217, doi 10.1080/10586458.2013.870056; preprint arXiv:1201.0749 (1. 1. 2012, revize 1. 9. 2013). Ověřeno 7. 11. 2026.
Herzberg, A. M.; Murty, M. R. (2007): Sudoku Squares and Chromatic Polynomials. Notices of the AMS 54(6), 708–717. Ověřeno 7. 11. 2026.
Knuth, D. E. (2000): Dancing Links. In: Millennial Perspectives in Computer Science, Palgrave, 187–214; arXiv:cs/0011047. Ověřeno 7. 11. 2026.
Yato, T.; Seta, T. (2003): Complexity and Completeness of Finding Another Solution and Its Application to Puzzles. IEICE Transactions on Fundamentals E86-A(5), 1052–1060. Ověřeno 7. 11. 2026.

Soutěže

World Puzzle Federation: přehled mistrovství světa v sudoku a v hádankách (worldpuzzle.org) a encyklopedické heslo World Sudoku Championship s tabulkou ročníků, vítězů a medailistů. Ověřeno 7. 11. 2026.
19. mistrovství světa v sudoku, Kalkata (Indie), 11.–18. 10. 2026: stránky pořadatele. Konečné výsledky se nepodařilo spolehlivě ověřit. Ověřeno 7. 11. 2026.
Mistrovství České republiky v sudoku pořádá HALAS – Hráčská asociace logických her a sudoku (například 16.–17. 9. 2023 na Přírodovědecké fakultě Masarykovy univerzity v Brně). Ověřeno 7. 11. 2026.

Literatura

Rosenhouse, J.; Taalman, L. (2011): Taking Sudoku Seriously: The Math Behind the World's Most Popular Pencil Puzzle. Oxford University Press.
Knuth, D. E. (2022): The Art of Computer Programming, Volume 4B: Combinatorial Algorithms, Part 2. Addison-Wesley (oddíl 7.2.2.1 Dancing links, sudoku jako přesné pokrytí).
Delahaye, J.-P. (2006): The Science behind Sudoku. Scientific American, červen 2006.
Herzberg, A. M.; Murty, M. R. (2007), McGuire, G. a kol. (2014), Yato, T.; Seta, T. (2003) – viz výše.

Modelové předpoklady laboratoří

Všechny úlohy, mřížky a statistiky počítá kód průvodce. Jednoznačnost se ověřuje backtrackingem s heuristikou MRV, který hledá dvě řešení. Logický řešitel zkouší techniky v pevném pořadí podle tabulky B.1 a vždy použije nejlehčí dostupnou; úroveň úlohy je nejvyšší úroveň použité techniky. Jiný řešitel s jiným pořadím nebo jinými technikami může stejné úloze přidělit jinou úroveň, a „mimo škálu“ proto neznamená „nejtěžší“, jen „nad rámec technik průvodce“. Banka pro statistiky v kapitolách 3 až 12 je 6 000 náhodných minimálních úloh se středovou symetrií vytvořených generátorem z kapitoly 12 (pevná semínka, výsledky jsou opakovatelné); stránka obsahuje výběr 109 úloh z ní. Počty mřížek 4 × 4 a 6 × 6, kombinace součtů Killeru, počty uzlů prohledávání, velikosti matice exact cover a počty klauzulí SAT jsou spočítané laboratořemi nebo skriptem nad stejným kódem; počty pro 9 × 9 jsou převzaté z uvedených prací a prvočíselnost činitele 27 704 267 971 a počet 9! · 56 · 6⁶ doplnění prvního pásu byly přepočítány. Rozložení Jigsaw a klecí Killeru jsou pevné ukázky, ne náhodný výběr ze všech možných.

Co zůstává nejisté

Počet známých úloh se 17 vodítky (sbírka G. Roylea, řádově desítky tisíc) uvádějí sekundární zdroje různě, proto jej průvodce nevyčísluje. Přesná doba, kdy se v Japonsku ustálilo zkrácené jméno „sudoku“, se v pramenech liší. Výsledky mistrovství světa 2026 v Kalkatě nebyly v době ověření spolehlivě dostupné.

Interaktivní průvodce Sudoku (listopad 2026). Studijní materiál o hře – hrajte pro radost a s mírou, bez sázek a peněz. Průvodce nejmenuje ani nedoporučuje aplikace, programy ani výrobce.