← Herna
Hledání min ve 3D
📖 Průvodce
📖 Průvodce: Hledání min12 kapitol hned pod hrou ↓
Hledání min🧭 Další průvodci a hry
INTERAKTIVNÍ PRŮVODCE · LISTOPAD 2026

Hledání min

Logika čísel
od prvního klepnutí po řešiče a složitost

Na pozadí hraje počítač hledání min na poli 16 × 16 se 40 minami tak jako člověk. Po prvním klepnutí v každém kroku hledá nejjednodušší techniku, která ještě něco odhalí – od splněného a plného čísla přes podmnožinu a překryv čísel až po výčet možností a počet min – a pojmenuje ji. Modře jsou čísla, ze kterých závěr plyne, oranžově pole, která se právě odkryla nebo dostala vlajku. Techniky vysvětlují kapitoly 2 až 6 a stejný řešič v kapitole 12 vyrábí pole, na kterých se nikdy nemusí hádat.

krok řešení–
technika–
odkryto–
zbývá min–
Úvodem

Jak průvodce používat

Hledání min je hra o čtení čísel. Pod zakrytými poli je schovaný daný počet min a každé odkryté pole ukáže, kolik min leží v jeho osmi sousedních polích. Kdo hraje „od oka“, často klepne naslepo, i když by se dalo přesně říct, kde mina je a kde není. Průvodce vede od pravidel a prvních jistých tahů přes vzory 1-1, 1-2 a 1-2-1 a výčet možností až k pravděpodobnosti, složitosti a k tomu, jak hledání min řeší a vyrábí počítač. Je pro hráče, kteří hru znají z počítače a chtějí hrát přesněji, pro rodiče a děti, které si při tom procvičí počítání do osmi a logické usuzování, i pro studenty matematiky a informatiky.

🚩

Tři patra každé kapitoly. Nahoře krátké vysvětlení a laboratoř nebo minihra na vlastním poli, kde si věc vyzkoušíte klepáním. Pod ní dvě mise za XP. Dole rozbalovací teorie pro ty, kdo chtějí jít do hloubky: přesné definice, 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 Hledání min ve 3D: louku z travnatých kostek, pět obtížností podle technik z tohoto průvodce a trenéra, který ukáže další logický krok a odkáže na kapitolu, kde se technika vykládá. Každé pole ve hře jde od prvního klepnutí dořešit bez hádání.

Mapa průvodce

Tab. 0.1Kapitoly, úroveň a co se v nich naučíte
KapitolaÚroveňCo se naučíte
1 Pravidla, pojmy a historiezákladyco znamená číslo, osm sousedů, první klepnutí, výhra a prohra; předchůdci z 80. let, verze z 90. let, české jméno a varianty
2 První tahyzákladyprázdná oblast, kde začít, splněné a plné číslo, vlajky, akord, typické omyly u okrajů a rohů
3 Podmnožinazákladyvzory 1-1 a 1-2 u stěny i uprostřed, jak podmnožinu vidět, odečítání min
4 Překryv číselzákladyvzory 1-2-1 a 1-2-2-1 odvozené krok za krokem, redukce čísla o vlajky, proč vzory platí i otočené
5 Výčet možnostípokročilíúsek hranice, rozmístění min, která neodporují žádnému číslu, nezávislé ostrůvky, výčet v hlavě
6 Počet min a konec hrypokročilíkdy rozhodne počítadlo min, pole mimo hranici, poslední chvíle hry
7 Hrát rychle a přesněpokročilíakordy, hraní bez vlajek, 3BV a efektivita, chyby z nepozornosti, mobil, zdravé hraní
8 Když hádat musíšpokročilísituace 50/50, pravděpodobnost jednotlivých polí, nejbezpečnější tah a tah, který nejvíc prozradí, proč hra v průvodci hádání nepotřebuje
9 Kombinatorika a pravděpodobnostmistr a vědapočet rozmístění C(n, m), vážení rozmístění, hustota a obtížnost, simulace: kolik her jde vyhrát bez hádání
10 Složitostmistr a vědaNP-úplnost konzistence (Kaye 2000), co-NP-úplnost odvoditelnosti (Scott, Stege, van Rooij 2011), co to znamená pro hráče
11 Jak řeší počítačmistr a vědačísla jako soustava rovnic, podmnožiny, prohledávání po nezávislých částech hranice, SAT a celočíselné programování v kostce, pravděpodobnostní řešič
12 Tvorba hry bez hádánímistr a vědanáhodné rozmístění, kontrola řešičem, oprava přesunem min, obtížnost podle nejtěžší techniky, varianty pole

Co budete potřebovat

Papír se čtverečky a tužku na rozkreslení vzorů – nebo jen prst na displeji. Všechna pole z průvodce jsou v laboratořích, takže nic tisknout nemusíte. Pro první část stačí počítat do osmi a odčítat; dítě, které zvládne sčítání do deseti, zvládne i vzor 1-2-1. Od kapitoly 8 se hodí zlomky a procenta, v kapitole 9 kombinační čísla a v kapitolách 10 a 11 trocha 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: logické hry s jediným řešením a poznámky tužkou v průvodcích Sudoku a Kakuro, kombinační čísla a zlomky v průvodci Matematika, pravděpodobnost, simulace a intervaly spolehlivosti 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, prohledávání a NP-úplnost obecně v průvodci Informatika.

Značení a předpoklady

Pole se v celém průvodci značí ř3s5 = 3. řádek shora, 5. sloupec zleva; levé horní pole je ř1s1. U výřezů z většího pole (schémata bez čísel řádků) se pole značí písmeny a, b, c… Světle šedá pole na okraji výřezu jsou odkrytá pole, jejichž čísla pro daný závěr nejsou potřeba. Klasické rozměry jsou 9 × 9 s 10 minami, 16 × 16 se 40 minami a 30 × 16 s 99 minami. Laboratoře, hero i 3D hra používají stejný řešič, 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á technikaKapitolaPodíl polí 9 × 9Podíl polí 16 × 16
1Splněné číslo, Plné číslo264,5 %24,9 %
2Podmnožina (vzory 1-1, 1-2)316,0 %28,3 %
3Překryv čísel (1-2-1, 1-2-2-1, redukce)42,1 %6,3 %
4Výčet možností50,2 %0,7 %
5Počet min67,5 %10,4 %
bez hádání nejdeněkde je nutné hádat89,7 %29,4 %
Podíly jsou ze simulace průvodce: 50 000 náhodných polí 9 × 9 s 10 minami a 20 000 polí 16 × 16 se 40 minami, první klepnutí doprostřed a vždy do prázdné oblasti (miny nejsou na prvním poli ani kolem něj). Nejistota (95 %) je u pole 9 × 9 nejvýš ±0,4 procentního bodu, u 16 × 16 nejvýš ±0,7 bodu. Hra v sekci Hledání min ve 3D vybírá jen pole z prvních pěti řádků.

Čtyři druhy rámečků

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

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

Z historie

Jak hra vznikla, kdo ji naprogramoval a co o ní dokázali matematici.

Mistrovská pomůcka

Rychlé pravidlo, zkratka nebo návyk, který používají zkušení hráči.

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 nedoporučuje žádné aplikace ani programy; historické údaje a matematické výsledky mají v příloze C zdroj a datum ověření (8. 11. 2026). Pole, počty, pravděpodobnosti a simulace v laboratořích jsou spočítané přímo v prohlížeči nebo skriptem nad stejným kódem.

Rozsahem odpovídá: matematika – pravděpodobnost a kombinatorika na úrovni úvodních vysokoškolských kurzů (kombinační čísla, podmíněná pravděpodobnost, vážení případů, odhad podílu ze simulace s intervalem spolehlivosti); informatika – úvod do úloh s omezeními (constraint satisfaction: proměnné, omezení, propagace, prohledávání s rozkladem na nezávislé části) a do teorie složitosti (NP-úplnost a co-NP-úplnost, převody z SAT); pravidla – klasické hledání min podle pramenů uvedených v příloze C.

Hrajte

Hledání min ve 3D

Hledejte miny na louce z travnatých kostek. Odkrytá kostka vyskočí a zmizí a odhalí pískové dno s číslem, vlajky jsou malé praporky. Louku jde zvětšit lupou a v nastavení přepnout Pohled 3D / 2D shora. Na výběr je Klasické (velikost pole a hustota min podle obtížnosti), Denní výzva (v daný den stejné pole pro všechny, obtížnost podle dne v týdnu), Pro děti (malá pole s málo minami) a Velké (16 × 30, klasický rozměr pro zkušené; na mobilu se pole otočí na výšku). Obtížnost 1 až 5 odpovídá technikám z průvodce: 1 splněné a plné číslo z kapitoly 2, 2 navíc podmnožina z kapitoly 3, 3 překryv čísel z kapitoly 4, 4 výčet možností z kapitoly 5 a 5 počet min z kapitoly 6. Ovládání v kostce: klepnutí odkryje pole, dlouhý stisk nebo přepínač ⛏/🚩 dá vlajku a klepnutí na číslo, které má kolem sebe všechny vlajky, odkryje jeho zbylé sousedy (akord, kapitola 7). Myší levé tlačítko odkrývá a pravé dává vlajku; na klávesnici šipky, mezerník odkrýt, V vlajka, T nápověda a Z zpět. Lupa: roztažení dvěma prsty nebo kolečko myši.

Jak to funguje: hra je bez hádání – každé pole jde od prvního klepnutí dořešit logikou a první klepnutí vždy otevře prázdnou oblast; ověřuje to stejný druh řešiče, jaký popisuje kapitola 12. Šlápnete-li přesto na minu, louka vybuchne, chyba se započítá a tah jde vrátit (↶), nebo můžete začít znovu. Nápověda trenéra má tři stupně: první klepnutí ukáže, kam se dívat, druhé pojmenuje techniku a ukáže bezpečná pole a miny, třetí ji provede; vždy s odkazem na kapitolu, kde se technika vykládá. Za rychlé vyřešení bez nápovědy a bez chyby jsou tři hvězdy, po výhře hra ukáže 3BV a efektivitu (kapitola 7). Rekordy, hvězdy a série denních výzev se ukládají jen ve vašem prohlížeči. Po výhře na místech min vykvetou květiny a kamera obletí louku.
Část IZáklady
1

Pravidla, pojmy a historiezáklady

Hrací pole je obdélník zakrytých polí; pod některými z nich jsou miny a jejich počet hra prozradí předem. Klepnutím pole odkryjete. Je-li pod ním mina, hra končí. Jinak se na odkrytém poli ukáže číslo: kolik min leží v jeho osmi sousedních polích – vodorovně, svisle i úhlopříčně. Pole bez min v sousedství (nula) se obvykle ukáže prázdné a hra rovnou odkryje i jeho sousedy; tak vznikají prázdné oblasti. Vyhráváte, když odkryjete všechna pole bez min. Vlajky si dáváte na pole, kde mina jistě je – k výhře nejsou nutné, jsou to poznámky.

🔢

Každé číslo je svědek, který ví, kolik min stojí kolem něj, ale neřekne které. Jeden svědek většinou nestačí. Pravdu poskládáte z výpovědí sousedních čísel – a právě o tom je celý průvodce.

První partie: pole 9 × 9 s 10 minami
Klepněte kamkoli. První klepnutí vždy otevře prázdnou oblast a celé pole jde dořešit technikami z kapitol 2 a 3, bez hádání. Vlajku dáte přepínačem ⛏/🚩, dlouhým stiskem nebo pravým tlačítkem myši; klepnutí na číslo, které už má kolem sebe všechny vlajky, odkryje jeho zbylé sousedy (akord). Tlačítko Nápověda ukáže další jistý krok a pojmenuje techniku. Za vyřešené pole získáte 15 XP.
LABORATOŘ
Model: miny se rozmístí náhodně až po prvním klepnutí, mimo klepnuté pole a jeho sousedy. Řešič z kapitoly 11 pak pole zkusí dořešit technikami úrovně 1 a 2; když se zasekne, generátor z kapitoly 12 přesune minu a zkusí to znovu. Proto na tomto poli nikdy nemusíte hádat. Šlápnete-li na minu, můžete tah vrátit.
+Teorie: pravidla přesně, osm sousedů, první klepnutí, pojmy, historie a varianty

1.1Pravidla přesně

Pole má W sloupců, H řádků a M min, nejvýš jednu na poli. Pro odkryté pole p označme N(p) množinu jeho sousedů. Číslo na poli je počet min mezi sousedy:

Co znamená číslo\[ \text{číslo}(p) = \#\{\, q \in N(p) : \text{na } q \text{ je mina} \,\}, \qquad |N(p)| \in \{3,\ 5,\ 8\} \]

Hráč smí pole odkrýt, nebo na něj dát (a zase sundat) vlajku. Hra končí prohrou odkrytím miny a výhrou, když jsou odkrytá všechna W · H − M bezpečná pole. Počítadlo min v rohu ukazuje M minus počet vlajek – nekontroluje, zda vlajky stojí správně.

po prvním klepnutí
122111111111111211121111223123456789123456789
vyřešeno (vlajky na minách)
11111122111111111111121112111122321111211111221123456789123456789
Obr. 1.1Pole 9 × 9 s 10 minami. Vlevo stav po prvním klepnutí na ř1s8 (oranžový rámeček): prázdná oblast odkryla 49 ze 71 bezpečných polí. Vpravo totéž pole vyřešené. Řešič průvodce potřeboval 22 kroků – 12× splněné číslo a 10× plné číslo, nic těžšího (úroveň 1).

1.2Osm sousedů – a někdy méně

Pole uvnitř má osm sousedů, pole na okraji pět a pole v rohu jen tři. Na to se snadno zapomene: jednička v rohu „hlídá“ tři pole, jednička uprostřed osm. Číslo 3 v rohu proto znamená, že všichni tři sousedé jsou miny, kdežto trojka uprostřed nic takového neříká.

uvnitř: 8 sousedů
12345678
u okraje: 5 sousedů
12345
v rohu: 3 sousedé
123
Obr. 1.2Sousedé pole (oranžový rámeček) uvnitř, u okraje a v rohu. Číslo na poli počítá miny jen v modře označených polích.
Tab. 1.1Kolik polí má 8, 5 a 3 sousedy na klasických rozměrech
PoleUvnitř (8 sousedů)U okraje (5)V rohu (3)Celkem
9 × 94928481
16 × 16196564256
30 × 16392844480
Obecně (W − 2)(H − 2) polí uvnitř, 2(W − 2) + 2(H − 2) u okraje a 4 rohy.

1.3První klepnutí

Při prvním klepnutí nemáte žádnou informaci. Běžné verze proto zaručují, že první pole není mina; starší počítačové verze to řešily tak, že minu z prvního pole potichu přesunuly jinam. Novější verze (podle přehledu na stránce minesweepergame.com od verze ve Windows Vista) zaručují i to, že první klepnutí otevře prázdnou oblast – miny nejsou ani v sousedství. Tak to dělá i hra v tomto průvodci. Kdyby platila jen záruka bezpečného pole, otevřela by se prázdná oblast jen s pravděpodobností z tabulky 1.2.

Tab. 1.2Pravděpodobnost, že bezpečné první klepnutí trefí nulu (otevře prázdnou oblast)
PoleHustota minUvnitřU okrajeV rohu
9 × 9, 10 min12,3 %32,6 %50,3 %66,6 %
16 × 16, 40 min15,6 %25,0 %42,3 %59,8 %
30 × 16, 99 min20,6 %15,4 %31,3 %49,8 %
Pole uvnitř: nula znamená, že všech 10 (40, 99) min leží mimo klepnuté pole a jeho 8 sousedů, tedy C(n − 9, M) / C(n − 1, M); u okraje a v rohu místo 9 stojí 6 a 4. Spočítáno skriptem; simulace 50 000 her 9 × 9 dala pro klepnutí doprostřed 32,7 %.

Proto zkušení hráči v klasické verzi často začínají v rohu: roh má nejvíc šancí na nulu. Prázdná oblast z rohu bývá ale menší a otevírá jen kousek pole. V této hře na tom nezáleží – nula je zaručená, kamkoli klepnete.

1.4Pojmy, které průvodce používá

  • Zakryté pole a odkryté pole – stav pole; odkryté ukazuje číslo nebo je prázdné.
  • Číslo – kolik min je v osmi (u okraje pěti, v rohu třech) sousedních polích.
  • Soused – pole, které se s daným polem dotýká stranou nebo rohem.
  • Vlajka – vaše označení jisté miny. Číslo, kterému „chybí“ miny, počítá s vlajkami jako s nalezenými minami.
  • Hranice – zakrytá pole, která sousedí s některým odkrytým číslem. Jen o nich čísla něco říkají; pole dál od hranice jsou zatím neznámá.
  • Prázdná oblast – souvislá skupina nul i s čísly na jejím okraji; hra ji odkryje jedním klepnutím.
  • Akord – klepnutí na číslo, které má kolem sebe tolik vlajek, kolik ukazuje: odkryje všechny jeho zbylé zakryté sousedy (kapitola 2 a 7).
  • Hustota min – podíl min na všech polích, M / (W · H); 12,3 % u 9 × 9, 15,6 % u 16 × 16 a 20,6 % u 30 × 16.
  • 3BV – nejmenší počet klepnutí, kterým jde pole odkrýt bez vlajek (přesná definice v kapitole 7).
Pozor

Vlajka není důkaz. Hra vlajku nekontroluje a počítadlo min klesá i za vlajku na špatném místě. Číslo „splněné“ špatnou vlajkou pak vede k odkrytí miny. Dávejte vlajky jen tam, kde je mina jistá – a při pochybnostech raději žádnou.

1.5Z historie

Z historie

Hry s minovým polem a čísly vznikaly v 80. letech. Mined-Out (Ian Andrew, vydavatel Quicksilva, 1983) pro počítač ZX Spectrum vedl hráče přes minové pole a detektor ukazoval počet min ve vodorovně a svisle sousedních polích. Logickou hru Relentless Logic pro MS-DOS (autoři uvádění jako Conway, Hong a Smith) datují databáze her do roku 1984 nebo 1985. Hru Mines pro systém SunOS (Unix) napsal Tom Anderson v roce 1987. Nejznámější verzi napsali Curt Johnson (původně pro OS/2) a Robert Donner, který ji převedl do Windows: v roce 1990 vyšla v balíku Microsoft Entertainment Pack a od roku 1992 byla standardní součástí Windows 3.1. Česká verze nese jméno Hledání min. Ve Windows Vista přibyl vzhled s květinami místo min a od Windows 8 (2012) hra přestala být součástí systému. Klasické obtížnosti 9 × 9 s 10 minami, 16 × 16 se 40 minami a 30 × 16 s 99 minami se od té doby drží ve většině verzí.

198519901995200020052010201520202025Mined-Out1983 · ZX Spectrum, I. AndrewRelentless Logic1985 · MS-DOS, 1984/1985Mines1987 · Unix, T. AndersonEntertainment Pack1990 · C. Johnson, R. DonnerWindows 3.11992 · součást systémuKaye: NP-úplnost2000 · Math. IntelligencerScott, Stege, van Rooij2011 · co-NP-úplnostHendrickson, Tockman2024 · FUN 2024
Obr. 1.3Časová osa: předchůdci, počítačové verze a matematické výsledky o složitosti hry (kapitola 10). Rok Relentless Logic se v pramenech liší.

1.6Varianty

Pravidlo „číslo = počet min v sousedství“ jde přenést na jiná pole. Existují verze na šestiúhelníkových a trojúhelníkových polích, prostorové verze ve 3D a verze, kde na jednom poli může být víc min. Ve výzkumu se používá i pole „zabalené“ do anuloidu: levý okraj sousedí s pravým a horní s dolním, takže každé pole má osm sousedů a okraje nic nezvýhodňují (tak počítali Dempsey a Guinn, kapitola 9). Pro hráče je nejdůležitější varianta bez hádání: pole je předem ověřené řešičem a jde dořešit logikou. Jak se taková pole vyrábějí, ukazuje kapitola 12.

Mistrovská pomůcka

Než klepnete, řekněte si nahlas, proč je pole bezpečné: „tahle jednička už má vlajku“. Pokud důvod nenajdete, neklepejte – hledejte jinde. Ve hře bez hádání jistý tah vždy existuje.

1.7Procvičení

1
Kolik sousedů má pole ř1s5 na poli 9 × 9?
Leží v horním řádku, ale ne v rohu: 5 sousedů (dva vedle sebe v řádku a tři pod sebou).
2
Může v rohu stát číslo 4?
Ne. Pole v rohu má jen tři sousedy, takže jeho číslo je nejvýš 3. U okraje je největší možné číslo 5, uvnitř 8.
3
Kolik polí na poli 16 × 16 má právě pět sousedů?
Okraj bez rohů: 2 · 14 + 2 · 14 = 56 polí.
4
Proč hra po odkrytí nuly sama odkryje i sousední pole?
Nula znamená, že v žádném sousedním poli mina není – všechna jsou bezpečná. Hra jen ušetří klepání. Je-li některý soused zase nula, pokračuje dál; tak vznikne celá prázdná oblast s čísly po okraji.
5
Klasické pravidlo: první pole je jen bezpečné. S jakou pravděpodobností klepnutí doprostřed pole 9 × 9 s 10 minami otevře prázdnou oblast?
Všech 10 min musí ležet mimo klepnuté pole a jeho 8 sousedů: C(72, 10) / C(80, 10) ≈ 32,6 %. Ve dvou případech ze tří tedy dostanete jen jedno číslo a další tah je hádání.
Co si odnést
  • Číslo = počet min v sousedních polích; uvnitř je sousedů 8, u okraje 5, v rohu 3.
  • Výhra = všechna bezpečná pole odkrytá; vlajky jsou jen poznámky a hra je nekontroluje.
  • Hra v tomto průvodci zaručuje prázdnou oblast po prvním klepnutí a pole bez hádání.
Část IZáklady
2

První tahyzáklady

Po prvním klepnutí se otevře prázdná oblast a po jejím okraji stojí čísla. Dvě nejjednodušší techniky stačí na většinu malých polí. Splněné číslo: kolem čísla už je tolik vlajek, kolik ukazuje – ostatní zakrytí sousedé jsou bezpeční. Plné číslo: číslu chybí stejně min, kolik má zakrytých sousedů – všichni jsou miny. Obě techniky se dívají jen na jedno číslo a jeho sousedy. V simulaci 50 000 polí 9 × 9 s 10 minami stačily samy na 64,5 % polí.

🧮

Počítejte jako pokladní: číslo minus vlajky je, kolik min ještě chybí. Chybí nula? Zbytek je bezpečný. Chybí přesně tolik, kolik je kolem zakrytých polí? Všechna jsou miny. Všechno ostatní je zatím „nevím“ – a na to jsou další kapitoly.

Rozbor čísla
Vyberte rozehranou partii a klepněte na libovolné číslo. Laboratoř spočítá jeho vlajky a zakryté sousedy a řekne, jestli je číslo splněné, plné, nebo zatím nic neříká. Modře se označí zakrytí sousedé, zeleně jistě bezpečná pole, červeně jisté miny.
LABORATOŘ
Model: u čísla c se spočítá m = c − počet vlajek (kolik min chybí) a z = počet zakrytých sousedů bez vlajky. m = 0 → splněné číslo, m = z → plné číslo, jinak samo číslo nerozhodne. Partie jsou skutečná pole 8 × 8 s 10 minami ze stejné banky jako minihra níže.
Minihra: Kde je jistě mina, kde bezpečno?
Laboratoř ukáže rozehranou partii a oranžovým rámečkem s otazníkem označí jedno zakryté pole. Rozhodněte: je tam jistě mina, je jistě bezpečné, nebo se to zatím nedá určit? Správná odpověď a důvod se ukážou až po volbě. Kolo má osm polí a za aspoň šest správných odpovědí získáte 15 XP.
MINIHRA
0 / 8
Jak je minihra ověřená: u každé situace řešič prošel všechna rozmístění min, která neodporují číslům ani celkovému počtu min. „Jistě“ znamená, že pole je stejné ve všech rozmístěních, a v této minihře to vždy plyne z jediného splněného nebo plného čísla. „Nedá se určit“ znamená, že v tu chvíli existují rozmístění s minou i bez ní – nepomůže ani technika z pozdějších kapitol.
+Teorie: prázdná oblast, splněné a plné číslo, vlajky a akord, typické omyly

2.1Kde začít

Prázdná oblast je ohraničená čísly a za nimi leží hranice – zakrytá pole, o kterých čísla něco říkají. Jisté tahy se nejčastěji najdou v „koutech“ hranice: tam, kde se okraj prázdné oblasti láme, a u stěn pole. Číslo, které má málo zakrytých sousedů, je silné: jednička se dvěma zakrytými sousedy říká mnohem víc než jednička s pěti.

Co číslu chybí\[ m(p) = \text{číslo}(p) - v(p), \qquad z(p) = \#\{\text{zakrytí sousedé } p \text{ bez vlajky}\}, \qquad 0 \le m(p) \le z(p) \]

Tady v(p) je počet vlajek (jistých min) kolem p. Nerovnost vpravo platí v každé správné situaci: kdyby číslu chybělo víc min, než má zakrytých sousedů, někde je chyba – nejspíš špatná vlajka.

2.2Splněné číslo

Je-li m(p) = 0, číslo už má kolem sebe všechny své miny a každý další zakrytý soused je bezpečný. Nejčastější případ: jednička, vedle které už stojí vlajka.satisfied number

Splněné číslo (úroveň 1)\[ m(p) = 0 \ \Rightarrow\ \text{všech } z(p) \text{ zakrytých sousedů je bezpečných} \]

2.3Plné číslo

Je-li m(p) = z(p), každé zakryté pole kolem musí být mina – jinak by jich nebylo dost. Nejčastější případy: jednička s jediným zakrytým sousedem, dvojka se dvěma, a čísla v rozích prázdné oblasti.full number

Plné číslo (úroveň 1)\[ m(p) = z(p) > 0 \ \Rightarrow\ \text{všech } z(p) \text{ zakrytých sousedů jsou miny} \]
splněné číslo: 2 už má dvě vlajky
✓✓✓11211
plné číslo: 3 má jen tři zakryté sousedy
12321
Obr. 2.1Vlevo splněná čísla: dvojka v modrém rámečku už má dvě vlajky, takže pole mezi nimi je bezpečné; stejně jsou splněné obě krajní jedničky. Vpravo plné číslo: trojce chybějí tři miny a má jen tři zakryté sousedy – všichni jsou miny. Jedničky na krajích jsou tím splněné, a proto jsou krajní pole bezpečná. Obě situace ověřil výčet: mají jediné rozmístění min.
Příklad Řetěz jednoduchých kroků

V obr. 2.1 vpravo nejdřív plné číslo 3 dá tři vlajky. Pak se každá jednička na kraji stane splněným číslem: její jediná mina už má vlajku, takže krajní pole je bezpečné. Takhle se úroveň 1 obvykle hraje – jedno plné číslo „spustí“ několik splněných a naopak. V obr. 1.1 stačilo 22 takových kroků na celé pole 9 × 9.

2.4Vlajky a akord

Vlajky slouží jako paměť: číslo, které má kolem sebe všechny vlajky, poznáte na první pohled jako splněné. Pak jde použít akord – klepnutí na samotné číslo odkryje všechny jeho zbylé zakryté sousedy najednou. V řadě počítačových verzí se akord dělá současným stiskem obou tlačítek myši, ve hře v tomto průvodci a v laboratoři v kapitole 1 klepnutím na číslo.chord

před akordem: 2 má obě vlajky
2123451234
jedno klepnutí na 2 odkryje 13 polí
11121111123451234
Obr. 2.2Akord. Dvojka v modrém rámečku má kolem sebe dvě vlajky (je splněná). Jedno klepnutí na ni odkryje všech šest zbylých zakrytých sousedů; jeden z nich je nula, a tak se otevře i prázdná oblast za ním – celkem 13 polí.
Pozor

Akord věří vašim vlajkám. Stojí-li některá vlajka kolem čísla špatně, akord odkryje skutečnou minu. Akord proto používejte jen u čísel, jejichž vlajky jste dali na základě jistoty, ne odhadu.

2.5Typické omyly

  • Zapomenutá vlajka v počtu. Dvojka s jednou vlajkou potřebuje už jen jednu minu – ne dvě. Vždy počítejte m = číslo − vlajky.
  • Okraj a roh. Pole za okrajem neexistuje; jednička v rohu prázdné oblasti u stěny má často jen jednoho nebo dva zakryté sousedy.
  • Odkryté sousedy počítat jako zakryté. Do z patří jen zakrytá pole bez vlajky; odkrytá čísla a prázdná pole kolem nejsou miny.
  • „Asi tam bude.“ Plné číslo platí, jen když zakrytých polí je přesně tolik, kolik chybí min. Dvojka se třemi zakrytými poli neříká nic jistého o žádném z nich.
  • Unáhlené klepnutí. Většina proher zkušených hráčů není chyba logiky, ale klepnutí vedle. O přesnosti a rychlosti je kapitola 7.
Mistrovská pomůcka

Procházejte hranici systematicky – po obvodu prázdné oblasti, jedním směrem – a u každého čísla si řekněte jen dvě čísla: kolik chybí a kolik je zakrytých. Kdo „skáče očima“, přehlédne splněné číslo hned vedle místa, kde se zasekl.

2.6Procvičení

1
Číslo 2 má kolem sebe jednu vlajku a dvě zakrytá pole. Co víte o zakrytých polích?
Chybí m = 2 − 1 = 1 mina ve z = 2 polích. Číslo není ani splněné, ani plné – samo nerozhodne. Pomůže až sousední číslo (kapitola 3).
2
Jednička u okraje má jediného zakrytého souseda bez vlajky a žádnou vlajku. Co s ním?
m = 1 = z: plné číslo, soused je mina. Dejte na něj vlajku – ostatní čísla kolem se tím možná stanou splněnými.
3
Trojka uprostřed má tři vlajky a dva zakryté sousedy. Co uděláte?
m = 0: splněné číslo. Oba zakrytí sousedé jsou bezpeční; nejrychleji je odkryje akord – klepnutí na trojku.
4
Může být číslo zároveň splněné i plné?
Jen když m = z = 0, tedy když kolem už nic zakrytého není. Takové číslo je „vyřízené“ a dál se jím nemusíte zabývat.
5
Dvojka má kolem sebe tři vlajky. Co to znamená?
m = 2 − 3 = −1 < 0, což v pořádku nastat nemůže: aspoň jedna vlajka je špatně. Sundejte vlajky, které nemáte podložené jistotou, a projděte okolí znovu – a hlavně tu dvojku nepoužívejte k akordu.
Co si odnést
  • U každého čísla počítejte m = číslo − vlajky a z = zakrytí sousedé bez vlajky.
  • m = 0 → splněné číslo (sousedé bezpeční); m = z → plné číslo (sousedé jsou miny).
  • Akord odkryje sousedy splněného čísla jedním klepnutím – ale jen se správnými vlajkami.
Část IZáklady
3

Podmnožinazáklady

Když už žádné číslo není splněné ani plné, pomůže dívat se na dvě čísla najednou. Jsou-li všichni zakrytí sousedé čísla A zároveň sousedy čísla B, tvoří jejich pole podmnožinu. Miny, které chybí číslu A, leží ve společných polích, a jsou tedy započítané i v čísle B. Co B chybí navíc, musí ležet v polích, která vidí jen B. Rozdíl min leží v rozdílu polí. Nejznámější podoby jsou vzory 1-1 (rozdíl je nula min → pole jsou bezpečná) a 1-2 (rozdíl je tolik min, kolik polí → jsou to miny).

🧺

Malý košík leží celý uvnitř velkého. V malém je jedno jablko a ve velkém taky jedno – takže mimo malý košík už žádné není. Kdyby ve velkém byla jablka dvě, druhé musí ležet mimo malý košík.

Laboratoř množin
Vyberte situaci a klepněte postupně na dvě čísla (A a B). Laboratoř rozkreslí jejich zakryté sousedy: modře pole jen čísla A, tyrkysově pole jen čísla B, oranžově společná pole. Pak spočítá, kolik min musí ležet v rozdílu, a řekne, co z toho plyne. Třetí klepnutí začne výběr znovu.
LABORATOŘ
jen Ajen Bspolečnájistě bezpečnéjistě mina
Model: pro čísla A a B jsou ZA a ZB jejich zakrytí sousedé bez vlajky a mA, mB chybějící miny. Je-li ZA ⊂ ZB, leží v rozdílu ZB ∖ ZA přesně mB − mA min. Situace „v partii“ jsou výřezy ze skutečných polí 9 × 9; světle šedá pole jsou odkrytá čísla, která pro závěr nejsou potřeba.
+Teorie: podmnožina přesně, vzory 1-1 a 1-2 u stěny i uprostřed, jak podmnožinu vidět

3.1Proč rozdíl min leží v rozdílu polí

Každé číslo je rovnice: součet min v jeho zakrytých sousedech je m. Když pole čísla A leží všechna mezi poli čísla B, rozpadne se rovnice čísla B na dvě části – společná pole (tam jsou přesně mA min, to říká číslo A) a zbytek.subset rule

Podmnožina (úroveň 2)\[ Z_A \subset Z_B \ \Rightarrow\ \#\text{min v } Z_B \setminus Z_A = m_B - m_A; \qquad m_B - m_A = 0 \Rightarrow \text{bezpečná}, \quad m_B - m_A = |Z_B \setminus Z_A| \Rightarrow \text{miny} \]

Je-li rozdíl min mezi 0 a počtem polí, technika samotná nic neodhalí, ale informace „v těchto polích jsou právě dvě miny“ se hodí dál – s ní pracuje překryv čísel (kapitola 4) a výčet možností (kapitola 5).

3.2Vzory u stěny

Stěna pole je nejčastější místo, kde podmnožina vznikne: jednička u stěny vidí jen dvě zakrytá pole, kdežto její soused vidí tři. V obr. 3.1 vidí jednička vlevo dole pole a, b a jednička vedle ní a, b, c. Mina první jedničky je v {a, b} – a ta už stačí i druhé jedničce. Pole c je bezpečné. Je-li druhé číslo 2, chybí mu druhá mina a ta může ležet jen v c.

1-1 u levé stěny: c je bezpečné
abc11
1-2 u levé stěny: c je mina
abc12
Obr. 3.1Vzor 1-1 a vzor 1-2 u levé stěny. Modře pole menšího čísla (a, b), která jsou zároveň poli většího. Vlevo je c bezpečné, vpravo je c mina. O polích a, b ani o polích vpravo od c vzor nic neříká.
Příklad Vzor 1-1 svisle u horní stěny

Vzor nemusí ležet vodorovně. V laboratoři „1-1 v partii“ stojí dvě jedničky pod sebou u horní stěny: horní vidí dvě zakrytá pole vlevo, dolní tatáž dvě a navíc jedno pod nimi. Rozdíl min je 1 − 1 = 0, takže pole pod nimi je bezpečné. Situace je výřez ze skutečného pole 9 × 9, kde to byl hned první krok po prvním klepnutí.

3.3Podmnožina uprostřed

Uprostřed pole se podmnožina objeví tam, kde jedno číslo má zakrytá pole „schovaná“ za odkrytými. V obr. 3.2 vidí horní jednička jen dvě zakrytá pole vpravo (modře), dolní jednička tatáž dvě a navíc tři pole pod sebou. Obě chybí jedna mina, rozdíl je nula – všechna tři spodní pole jsou bezpečná.

111✓✓✓
Obr. 3.2Podmnožina uprostřed (výřez 5 × 5 ze skutečného pole 9 × 9). Horní jednička (modrý rámeček) vidí dvě modrá pole, dolní jednička (zelený rámeček) tatáž dvě a tři pole pod sebou. Rozdíl min 1 − 1 = 0, takže tři pole se značkou ✓ jsou bezpečná.

3.4Jak podmnožinu vidět

  • Hledejte dvojice sousedních čísel podél rovného úseku hranice – mají nejvíc společných polí.
  • Začněte u čísla, které má nejméně zakrytých polí (u stěny, v koutě, vedle vlajek). To bývá ta menší množina.
  • Nejdřív odečtěte vlajky: dvojka s jednou vlajkou se chová jako jednička. Vzor 1-1 se tak často skrývá jako 2-2, 2-3 nebo 3-3.
  • Pole menšího čísla musí být všechna i poli většího. Jediné pole navíc u menšího čísla vzor ruší – pak jde o překryv (kapitola 4).
Pozor

Vzor 1-1 neříká, kde je mina, jen kde není. Častá chyba je dát vlajku „na jistotu“ do společné dvojice polí – mina tam je, ale nevíte, ve kterém z nich. Rozhodne až další číslo nebo počet min na konci hry.

Mistrovská pomůcka

Vzor 1-1 u stěny čtěte jako „jednička u stěny odpovídá i za souseda“: pole třetí od stěny je bezpečné. Vzor 1-2 jako „dvojka potřebuje ještě jednu minu a jinam ji dát nemůže“: pole třetí od stěny je mina. Zkušení hráči vidí tyto dvojice na první pohled po celé hranici.

V simulaci 50 000 polí 9 × 9 (první klepnutí do prázdné oblasti) byla podmnožina nejtěžší potřebnou technikou u 16,0 % polí, u polí 16 × 16 se 40 minami u 28,3 %. Na větších polích je to nejčastější úroveň: hranice je delší a dvojic čísel je víc.

3.5Procvičení

1
Jednička vidí zakrytá pole a, b. Dvojka vedle ní vidí a, b, c, d. Co víte o c a d?
{a, b} ⊂ {a, b, c, d}, rozdíl min 2 − 1 = 1 v rozdílu {c, d} o dvou polích. Ani 0, ani 2 – jistě nic, jen „v c, d je právě jedna mina“.
2
Dvojka s jednou vlajkou vidí zakrytá pole a, b. Trojka s jednou vlajkou vidí a, b, c. Co je c?
Po odečtení vlajek chybí dvojce 1 mina a trojce 2 miny. {a, b} ⊂ {a, b, c}, rozdíl 2 − 1 = 1 = počet polí rozdílu: c je mina (vzor 1-2 skrytý pod vlajkami).
3
Jednička vidí a, b, c. Jednička vedle ní vidí a, b. Co víte?
Menší množina je {a, b} u druhé jedničky. Rozdíl min 1 − 1 = 0 v poli c: c je bezpečné. Na pořadí, které číslo jste viděli první, nezáleží.
4
Jednička vidí a, b. Dvojka vidí b, c. Je to podmnožina?
Ne – pole a vidí jen jednička. Taková dvojice sdílí jen část polí; pracuje s ní překryv čísel (kapitola 4). Tady z ní plyne: dvojka má v {b, c} dvě miny, takže b i c jsou miny a a je bezpečné.
5
Proč se vzory 1-1 a 1-2 nejčastěji objevují u stěny?
Číslo u stěny má jen pět sousedů a po odkrytí prázdné oblasti mu často zbudou jen dvě zakrytá pole. Jeho soused dál od stěny vidí tatáž pole a navíc jedno – vzniká podmnožina. Uprostřed pole mají čísla víc sousedů a podmnožina vzniká méně často.
Co si odnést
  • Leží-li zakrytá pole čísla A všechna mezi poli čísla B, je v rozdílu polí právě m_B − m_A min.
  • 1-1: rozdíl je nula min → pole jsou bezpečná; 1-2: rozdíl je tolik min, kolik polí → jsou to miny.
  • Nejdřív odečtěte vlajky – vzory se často skrývají ve větších číslech.
Část IZáklady
4

Překryv číselzáklady

Často dvě čísla sdílejí jen část svých zakrytých polí a žádné neleží celé uvnitř druhého. I pak jde o společné části něco říct: kolik min v ní nejméně musí být a kolik nejvýš může být. Když se meze sejdou, rozhodnou o polích, která vidí jen jedno z čísel. Tak vznikají slavné vzory 1-2-1 a 1-2-2-1 podél rovné hranice. V této kapitole je odvodíme, ne jen ukážeme – pak je poznáte i otočené, u stěny i „schované“ pod vlajkami (redukce).

🤝

Dva sousedé se dělí o plot. Jeden ví, že na jeho pozemku je jeden pes, druhý, že na jeho jsou dva. Když je plot úzký a pes na něm může být nejvýš jeden, druhý soused musí mít psa i jinde. Přesně tak se čtou meze ve společné části.

Minihra: Vzory v různém natočení
Laboratoř ukáže vzor z této nebo předchozí kapitoly v náhodném natočení a zrcadlení. Klepnutím označte pole, kde jsou miny (dalším klepnutím značku zrušíte), a stiskněte Vyhodnotit. Správné řešení a jeho odvození se ukážou až po vyhodnocení. Kolo má šest vzorů a za aspoň pět správných získáte 15 XP.
MINIHRA
0 / 6
Jak je minihra ověřená: u každého vzoru prošel řešič všechna rozmístění min; vzor 1-2-1, 1-2-2-1 a 2-3-2 s vlajkou mají jediné, takže řešení je jednoznačné. U vzorů 1-1 a 1-2 u stěny je jisté jen třetí pole od stěny – označte miny jen tam, kde jsou jistě. Šedá pole jsou odkrytá čísla mimo vzor.
+Teorie: meze ve společné části, odvození 1-2-1 a 1-2-2-1, redukce, souměrnosti

4.1Meze ve společné části

Mějme dvě čísla A a B se zakrytými poli ZA, ZB a chybějícími minami mA, mB. Rozdělme pole na tři části: společnou S = ZA ∩ ZB, jen A (A′) a jen B (B′). Ve společné části je s min. Číslo A má zbytek mA − s min v A′ a těch nemůže být víc než |A′|; podobně pro B.overlap of numbers

Překryv čísel (úroveň 3)\[ \max\big(0,\ m_A - |A'|,\ m_B - |B'|\big) \ \le\ s\ \le\ \min\big(|S|,\ m_A,\ m_B\big) \]

Z mezí smin ≤ s ≤ smax plyne, kolik min je v A′: nejméně mA − smax, nejvýš mA − smin. Je-li horní mez 0, jsou pole A′ bezpečná; je-li dolní mez rovna |A′|, jsou to miny. Totéž pro B′. Podmnožina z kapitoly 3 je zvláštní případ, kdy A′ je prázdná.

4.2Odvození vzoru 1-2-1

Nad řadou čísel 1, 2, 1 leží pět zakrytých polí a až e; jednička vlevo vidí a, b, c, dvojka b, c, d a jednička vpravo c, d, e. Jiná zakrytá pole kolem nejsou.

  1. Levá jednička a dvojka: společná pole jsou b, c. Dvojka potřebuje dvě miny a mimo společnou část má jen d – ve společné části je tedy aspoň jedna mina. Jednička jich víc než jednu nemá. Ve společné části je právě jedna mina; jedničce tím nic nezbývá, takže a je bezpečné, a dvojce chybí ještě jedna mina, takže d je mina.
  2. Dvojka a pravá jednička: zrcadlově – ve společné části c, d je právě jedna mina, e je bezpečné a b je mina.
  3. Dvojka: má už miny b a d, je splněná – c je bezpečné.
1. krok: 1 a 2 vlevo → d mina, a bezpečné
abcde121
2. krok: 2 a 1 vpravo → b mina, e bezpečné
abcde121
3. krok: 2 má b a d → c bezpečné
abcde121
Obr. 4.1Odvození vzoru 1-2-1 ve třech krocích. Modře společná pole dvojice čísel v rámečcích, zeleně bezpečná pole, červeně miny. Výsledek: miny nad jedničkami, nad dvojkou a na krajích bezpečno. Výčet všech 32 možností potvrdil, že vyhovuje jediné rozmístění.

4.3Vzor 1-2-2-1

Nad čísly 1, 2, 2, 1 leží šest zakrytých polí a až f. Stejný krok jako v 1-2-1 udělejte z obou konců: levá jednička s dvojkou dají „a bezpečné, d mina“, pravá jednička s dvojkou „f bezpečné, c mina“. Každá dvojka má pak obě miny (c, d) a zbylá pole b, e jsou bezpečná. Miny leží nad oběma dvojkami.

4.4Redukce o vlajky

Číslo s vlajkami se chová jako menší číslo: místo „čísla“ čtěte „kolik ještě chybí“. Řada 2-3-2, pod kterou leží vlajka sousedící se všemi třemi čísly, je po odečtení vlajky 1-2-1. Hráči tomu říkají redukce. Stejně se z 2-3-3-2 s vlajkami stane 1-2-2-1, z 2-2 vzor 1-1 a podobně.

1-2-2-1: miny pod oběma dvojkami
1221
2-3-2 s vlajkou pod trojkou = 1-2-1
23211
Obr. 4.2Vlevo vzor 1-2-2-1: miny nad dvojkami, krajní a vnější pole bezpečná. Vpravo 2-3-2 s vlajkou pod trojkou (oranžový rámeček): po odečtení vlajky každému číslu chybí 1, 2, 1 mina – je to vzor 1-2-1. Obě situace mají jediné rozmístění.
Příklad Redukce v praxi

Hranice podél vlajek vypadá na první pohled jako nesmyslná směs trojek a čtyřek. Projděte ji a ke každému číslu si v duchu napište, kolik mu chybí. Z řady 3-4-3 se dvěma vlajkami pod každým číslem se stane 1-2-1 a odpověď je hned jasná. Hra v nápovědě takový krok pojmenuje jako překryv čísel a v popisu uvede, kolik které číslo ještě potřebuje.

4.5Proč vzory platí i otočené

Sousedství na čtverečkovaném poli se nezmění, když pole otočíte o 90°, 180° nebo 270° nebo ho zrcadlíte – takových souměrností čtverce je osm. Každý vzor proto platí ve všech osmi polohách: vodorovně, svisle, „zespodu“ i zprava. Na úhlopříčku se ale vzory nepřenášejí: úhlopříčná řada čísel má jiné společné sousedy.

Pozor

Vzor platí, jen když čísla nemají žádná další zakrytá pole. Stojí-li 1-2-1 na hranici, za kterou je další zakrytá řada, jsou to jiná čísla s jinými množinami polí a závěr neplatí. Než vzor použijete, zkontrolujte, že „za“ čísly je odkryto nebo stěna.

Mistrovská pomůcka

Pamatujte si jen dvě věty: „1-2-1 → miny nad jedničkami“ a „1-2-2-1 → miny nad dvojkami“. Vše ostatní je redukce: odečtěte vlajky a hledejte, kterou z obou vět řada připomíná.

V simulaci 50 000 polí 9 × 9 byl překryv čísel nejtěžší potřebnou technikou u 2,1 % polí, u polí 16 × 16 se 40 minami u 6,3 %. Ve hře se objevuje od obtížnosti 3.

4.6Procvičení

1
Jednička vidí a, b, c, dvojka b, c, d. Jiná čísla nejsou. Co je jisté?
Společná část {b, c}: dolní mez max(0, 1 − 1, 2 − 1) = 1, horní min(2, 1, 2) = 1 – právě jedna mina. Proto a je bezpečné a d je mina. O b a c zatím víte jen, že jedna z nich je mina.
2
Jednička vidí a, b, c, d, dvojka c, d, e. Co je jisté?
Společná část {c, d}: dolní mez max(0, 1 − 2, 2 − 1) = 1, horní min(2, 1, 2) = 1. Jednička má tedy minu v {c, d} a a, b jsou bezpečná; dvojce chybí ještě jedna mina mimo společnou část, a tak e je mina.
3
Řada 1-2-1 stojí svisle u pravé stěny, zakrytá pole jsou vlevo od ní. Kde jsou miny?
Vzor platí v každém natočení: vedle obou jedniček (v zakrytém sloupci), vedle dvojky a na koncích bezpečno.
4
Pod řadou 2-3-2 nejsou žádné vlajky a pod čísly je ještě jedna zakrytá řada. Platí 1-2-1?
Ne. Čísla mají zakrytá pole i pod sebou, takže jejich množiny jsou jiné a vzor neplatí. Redukce funguje jen s vlajkami (jistými minami), ne se zakrytými poli.
5
Kolik ze 32 rozmístění min v pěti polích nad 1-2-1 vyhovuje všem třem číslům?
Jen jedno – miny nad jedničkami. Proto vzor dává úplnou odpověď; u 1-1 jich jsou dvě (mina v a, nebo v b), a proto je jisté jen třetí pole.
Co si odnést
  • Ve společné části dvou čísel je nejméně max(0, m_A − |A′|, m_B − |B′|) a nejvýš min(|S|, m_A, m_B) min.
  • 1-2-1 → miny nad jedničkami; 1-2-2-1 → miny nad dvojkami; vždy jen bez dalších zakrytých polí za čísly.
  • Redukce: odečtěte vlajky a vzory poznáte i ve větších číslech a v každém natočení.
Část IIPokročilí
5

Výčet možnostípokročilí

Když nepomůže žádná dvojice čísel, vezměte malý úsek hranice – zakrytá pole kolem tří až pěti sousedních čísel – a projděte všechna rozmístění min, která neodporují žádnému číslu. Skutečné rozmístění je jedno z nich. Co platí ve všech, platí i ve skutečnosti: pole, které je ve všech rozmístěních bez miny, je bezpečné, a pole, které je ve všech minou, je mina. Výčet je nejobecnější technika z čísel; vzory z kapitol 3 a 4 jsou jen jeho zkratky.

🗂️

Detektiv si sepíše všechny verze, jak se to mohlo stát, a škrtá ty, které odporují výpovědím. Zbudou-li dvě verze a v obou byl zahradník doma, je to jisté – i když nevíme, která verze je pravdivá.

Laboratoř: výčet na úseku hranice
Vyberte rozehranou partii. Klepnutím na čísla (nejvýš pět) určíte úsek hranice – jejich zakrytá pole. Laboratoř vypíše všechna rozmístění min na úseku, která neodporují žádnému číslu, a obarví pole, která jsou ve všech rozmístěních stejná. Tlačítko Výběr řešiče vybere čísla, která použil řešič.
LABORATOŘ
úsek hraniceve všech bez minyve všech mina
Model: proměnná za každé pole úseku (1 = mina). Číslo, jehož všechna zakrytá pole leží v úseku, dává rovnost; číslo, které vidí i pole mimo úsek, dává jen meze (nejméně m minus počet polí venku, nejvýš m). Prohledávání zkouší pole postupně a větev zahodí, jakmile některé číslo nejde splnit. Partie A–D jsou skutečné stavy z polí 8 × 8 a 9 × 9, ve kterých řešič průvodce poprvé potřeboval výčet možností.
+Teorie: proč výčet platí, úsek a meze, ostrůvky, výčet v hlavě

5.1Proč výčet platí

Označme x1, …, xk pole úseku (1 = mina, 0 = bez miny). Každé číslo, které vidí jen pole úseku, je rovnice; každé, které vidí i pole mimo úsek, je nerovnost. Skutečné rozmístění min všechny splňuje. Pokud tedy ve všech řešeních platí xi = 0, platí to i ve skutečnosti.enumeration of configurations

Výčet možností (úroveň 4)\[ \mathcal{R} = \Big\{ x \in \{0,1\}^k : \ \ell_c \le \sum_{i \in Z_c} x_i \le u_c \ \text{pro každé číslo } c \Big\}, \qquad \forall x \in \mathcal{R}:\ x_i = 0 \ \Rightarrow \ \text{pole } i \text{ je bezpečné} \]

Pro číslo c, které chybí mc min a má oc zakrytých polí mimo úsek, je ℓc = max(0, mc − oc) a uc = mc. Všech možností je 2k; řešič průvodce bere úseky nejvýš 14 polí (16 384 možností), ale díky průběžnému škrtání jich skutečně projde mnohem méně.

5.2Řešený příklad

111111222111122123232211abc11d2222112e1111123456789123456789
Obr. 5.1Skutečná partie 9 × 9 (stav po 17 krocích řešiče). Úsek hranice a–e kolem čísel ř6s1, ř6s3 a ř8s2 (modré rámečky); do výčtu vstupují i další čísla, která pole úseku vidí – hlavně jednička na ř9s2. Žádná dvojice čísel tu nic neodhalí.

Čísla říkají: dvojce na ř6s1 (s vlajkou vedle) chybí jedna mina v {a, b}, trojce na ř6s3 jedna mina v {b, c}, dvojce na ř8s2 dvě miny v {a, b, c, d, e} a jedničce na ř9s2 jedna mina v {d, e}. Z 32 možností vyhovují všem číslům jen dvě:

rozmístění 1
111111222111122123232211abc11d2222112e1111
rozmístění 2
111111222111122123232211abc11d2222112e1111
Obr. 5.2Obě rozmístění min na úseku a–e, která neodporují žádnému číslu. Ve skutečné hře platí jedno z nich. V obou je b mina a a, c jsou bezpečná; o d a e (jedna z nich je mina) výčet nerozhodne.

5.3Výčet v hlavě: zkouška sporem

Hráč nevypisuje 32 řádků. Vybere jedno klíčové pole a zkusí obě možnosti – kdo zná kapitolu o důkazu sporem, pozná ji. V příkladu:

  1. Předpokládejme, že b je bez miny. Pak dvojka na ř6s1 potřebuje minu v a a trojka na ř6s3 minu v c. Dvojka na ř8s2 má tím obě miny (a, c), takže d a e jsou bez min – jenže jednička na ř9s2 jednu minu v {d, e} potřebuje. Spor.
  2. Tedy b je mina. Dvojka na ř6s1 i trojka na ř6s3 jsou tím splněné, takže a a c jsou bezpečná.
Mistrovská pomůcka

Pro zkoušku sporem vybírejte pole, které vidí nejvíc čísel – jeho předpoklad „spustí“ nejvíc důsledků a spor (nebo jistota) se ukáže nejrychleji. Když obě větve projdou bez sporu, podívejte se, co mají společného: pole stejné v obou větvích je také jisté.

5.4Nezávislé ostrůvky

Hranice se často rozpadá na části, které nesdílejí žádné číslo – ostrůvky. Rozmístění v jednom ostrůvku nijak neomezuje druhý (dokud nehraje roli celkový počet min, kapitola 6). Počet rozmístění celé hranice je proto součin počtů v ostrůvcích a každý ostrůvek jde vyčíslit zvlášť. To je hlavní trik počítačových řešičů (kapitola 11): má-li hranice 20 polí ve dvou ostrůvcích po deseti, stačí místo 220 = 1 048 576 možností projít nejvýš 2 · 210 = 2 048.

Ostrůvky se násobí\[ |\mathcal{R}_{\text{hranice}}| = \prod_{j} |\mathcal{R}_j| \qquad (\text{bez ohledu na celkový počet min}) \]
Pozor

Počet rozmístění není pravděpodobnost. Je-li pole minou ve třech rozmístěních ze čtyř, neznamená to automaticky 75 %: rozmístění s různým počtem min mají různou váhu podle toho, kolik zbývá min pro zbytek pole. Správný výpočet ukazuje kapitola 9.

5.5Kolik výčet přidá

Výčet je silný, ale na běžných polích ho potřebujete zřídka: v simulaci byl nejtěžší potřebnou technikou u 0,2 % polí 9 × 9 a 0,7 % polí 16 × 16. Překvapivě málo chybí i do „dokonalé logiky“: řešič, který vyčísluje celou hranici najednou včetně počtu min, vyřešil bez hádání jen o 0,1 procentního bodu víc polí než řešič s technikami tohoto průvodce (90,4 % proti 90,3 % u 9 × 9, 70,7 % proti 70,6 % u 16 × 16). Co techniky nevyřeší, je většinou skutečné hádání.

5.6Procvičení

1
Jednička vidí a, b, dvojka vidí a, b, c, d, jednička vidí c, d. Kolik je rozmístění?
Jedna mina v {a, b} (2 možnosti) a jedna v {c, d} (2 možnosti); dvojka má pak vždy právě dvě. Celkem 4 rozmístění a žádné pole není jisté.
2
Jednička vidí a, b, c. Dvojka vidí c, d. Jednička vidí d, e. Jiná čísla nejsou. Co je jisté?
Dvojka má jen dvě pole, je plná: c a d jsou miny. První jednička je tím splněná (a, b bezpečná) a stejně druhá (e bezpečné). Výčet dá jediné rozmístění – zde stačilo plné číslo.
3
Úsek má 12 polí. Kolik je všech možností a proč počítač přesto počítá rychle?
212 = 4 096. Prohledávání ale zkouší pole postupně a větev zahodí, jakmile některé číslo nejde splnit, takže velkou část možností vůbec nepotřebuje projít.
4
Hranice má dva ostrůvky se 2 a 5 rozmístěními. Kolik rozmístění má celá hranice?
2 · 5 = 10 (bez ohledu na celkový počet min). Kdyby ostrůvky sdílely číslo, součin by neplatil – musely by se vyčíslit společně.
5
Ve výčtu je pole minou ve 4 rozmístěních z 5. Co s ním?
Nic jistého – je jedno rozmístění, kde mina není. Hledejte jiné pole, nebo rozšiřte úsek o další číslo. Pokud nic nepomůže, rozhodne až počet min (kapitola 6), nebo se musí hádat (kapitola 8).
Co si odnést
  • Vypište rozmístění min na malém úseku hranice, která neodporují žádnému číslu; co platí ve všech, platí.
  • V hlavě: zkouška sporem na poli, které vidí nejvíc čísel.
  • Nezávislé ostrůvky se vyčíslují zvlášť a jejich počty se násobí.
Část IIPokročilí
6

Počet min a konec hrypokročilí

Čísla na poli neznají celkový počet min – ten ukazuje počítadlo. Na začátku hry je to slabá informace, na konci rozhodující. Každé rozmístění min na hranici spotřebuje nějaký počet min a zbytek musí přesně padnout do polí mimo hranici (zakrytých polí, o kterých žádné číslo nic neříká). Rozmístění, která potřebují víc min, než zbývá, nebo nechají víc min, než se vejde jinam, odpadají. Tak počet min rozhodne mezi možnostmi, které čísla nechávají otevřené – a někdy prozradí i pole uprostřed neznáma.

🧾

Na konci nákupu víte, kolik vám zbylo peněz. Když zbývá stokoruna a jedna možnost nákupu stojí dvě stě, tu škrtnete – i kdyby jinak dávala smysl. Počítadlo min je peněženka hledání min.

Laboratoř: rozhodne počet min?
Vyberte konec partie a přepínejte mezi rozborem jen z čísel a rozborem s počtem zbývajících min. Tabulka ukáže, kolik min mohou mít jednotlivé ostrůvky hranice (v závorce počet jejich rozmístění), kolik min tím leží na celé hranici a zda se zbytek vejde do polí mimo hranici. Zeleně jistě bezpečná pole, červeně jisté miny.
LABORATOŘ
hranicemimo hranicijistě bezpečnéjistě mina
Model: hranice se rozdělí na nezávislé ostrůvky, v každém se vyčíslí všechna rozmístění a seskupí podle počtu min k. Kombinace ostrůvků s celkem t minami je možná, jen když zbytek R − t padne do I polí mimo hranici: 0 ≤ R − t ≤ I. Partie A–D jsou skutečné konce her z polí 8 × 8 a 9 × 9, kde řešič průvodce potřeboval počet min.
+Teorie: zbývající miny, pole mimo hranici, vyloučení rozmístění, poslední chvíle hry

6.1Kolik min zbývá a kam se vejdou

Počítadlo ukazuje R = M − v, kde v je počet vlajek. Hrajete-li bez vlajek (kapitola 7), musíte si jisté miny počítat sami. Zakrytá pole bez vlajky se dělí na hranici (sousedí s odkrytým číslem) a pole mimo hranici – jejich počet označme I. Rozmístění hranice s t minami je možné, jen když zbylých R − t min padne do polí mimo hranici.mine count

Počet min (úroveň 5)\[ R = M - v, \qquad \text{rozmístění hranice s } t \text{ minami je možné} \iff 0 \le R - t \le I \]

Dva krajní případy jsou nejčastější: když je R rovno nejmenšímu počtu min, který hranice potřebuje, jsou všechna pole mimo hranici bezpečná; když R − t = I pro každé možné t, jsou všechna pole mimo hranici miny.

zbývá 0 min: roh je bezpečný
13113112221132142122111111221234567812345678
zbývá 1 mina na 4 polích
11111211312121112211121111111122111ab221122cd111111123456789123456789
Obr. 6.1Vlevo konec partie 8 × 8: pole v pravém horním rohu je ze všech stran obklopené vlajkami, žádné číslo o něm nic neříká. Počítadlo ukazuje 0 zbývajících min – pole je bezpečné. Vpravo konec partie 9 × 9: zbývá 1 mina, hranice a, b, d má dvě rozmístění (mina jen v b, nebo miny v a i d) a c leží mimo hranici. Rozmístění se dvěma minami odpadá: b je mina, a, c, d jsou bezpečná.

6.2Vyloučení rozmístění podle počtu

Příklad Obr. 6.1 vpravo krok za krokem

Čísla v rohu připouštějí dvě rozmístění: {b} s jednou minou a {a, d} se dvěma. Pole c nesousedí s žádným odkrytým číslem. Zbývá R = 1 mina. Rozmístění {a, d} by potřebovalo dvě – odpadá. Zbude {b}: b je mina a na pole mimo hranici zbývá 1 − 1 = 0 min, takže i c je bezpečné. Bez počítadla by šlo jen hádat mezi b a dvojicí a, d.

V partii D v laboratoři je hranice rozdělená na dva ostrůvky: první potřebuje 2 nebo 3 miny, druhý vždy 2. Zbývají 4 miny, takže první ostrůvek musí mít právě 2 a na osm polí mimo hranici nezbude nic – všechna jsou bezpečná. Takové „sečtení ostrůvků“ je typické pro poslední fázi velkých polí.

6.3Poslední chvíle hry

  • Počítejte dřív, než zbudou dvě pole. Počet min pomáhá, jakmile je zakrytých polí málo – v kódu průvodce se zkouší od 64 zakrytých polí níž.
  • Hledejte pole mimo hranici. Kout zakrytý vlajkami, díra uprostřed, pruh za řadou min. O nich rozhoduje jen počet.
  • Nejdřív dořešte, co jde z čísel. Každé jisté pole snižuje počet možností a zpřesňuje, kolik min hranice potřebuje.
  • Kontrolujte vlajky. Jediná špatná vlajka posune počítadlo o jednu a závěr z počtu min je pak chybný.
Pozor

Počet min nerozhodne situaci 50 na 50, kde obě možnosti potřebují stejný počet min: dvě pole, jedna mina, žádné další informace. Takové pozice jsou skutečně nerozhodnutelné a v klasické hře se musí hádat (kapitola 8). Hra v tomto průvodci je díky generátoru z kapitoly 12 nikdy nepoužije.

Mistrovská pomůcka

Na konci hry si napište tři čísla: kolik min zbývá, kolik nejméně a kolik nejvýš jich potřebuje hranice. Pokud „nejméně“ = „zbývá“, je všechno mimo hranici bezpečné a hranice má jen rozmístění s nejmenším počtem min. Pokud „nejvýš“ + počet polí mimo hranici = „zbývá“, jsou pole mimo hranici miny.

Počet min je překvapivě často potřeba: v simulaci byl nejtěžší potřebnou technikou u 7,5 % polí 9 × 9 a u 10,4 % polí 16 × 16 – častěji než překryv čísel a výčet možností dohromady. Konce her bývají právě takové „kouty“ a uzavřená pole.

6.4Procvičení

1
Zbývají 2 miny. Hranice má rozmístění se 2 nebo 3 minami a mimo hranici jsou 4 pole. Co víte?
Rozmístění se 3 minami potřebuje víc, než zbývá – odpadá. Hranice má právě 2 miny a na pole mimo hranici zbývá 0: všechna 4 pole mimo hranici jsou bezpečná.
2
Zbývá 5 min. Hranice potřebuje vždy právě 2 miny a mimo hranici jsou 3 pole. Co víte?
Na pole mimo hranici zbývají 3 miny a polí jsou 3: všechna jsou miny.
3
Zbývá 1 mina na dvou polích a, b, které vidí jen jedna jednička. Jiná zakrytá pole nejsou. Pomůže počet min?
Ne. Obě možnosti (mina v a, nebo v b) potřebují jednu minu. To je čistá situace 50 na 50 – v klasické hře se musí hádat.
4
Hranice má dva ostrůvky: první potřebuje 1 nebo 2 miny, druhý 1 nebo 2. Zbývají 2 miny a mimo hranici nic není. Co víte?
Součet musí být přesně 2: oba ostrůvky mají právě 1 minu. Rozmístění s 2 minami v libovolném ostrůvku odpadají – a pole, která byla minou jen v nich, jsou bezpečná.
5
Proč počet min na začátku hry skoro nic neříká?
Polí mimo hranici je mnoho a vejde se do nich téměř libovolný zbytek, takže podmínka 0 ≤ R − t ≤ I nic nevyloučí. Rozmístění s různým počtem min mají ale různou váhu – to se projeví v pravděpodobnostech (kapitola 9).
Co si odnést
  • Zbývající miny R = M − vlajky musí pokrýt hranici i pole mimo ni: 0 ≤ R − t ≤ I.
  • Rozmístění hranice, která se s počtem min nesrovnají, odpadají – a s nimi někdy i nejistota.
  • Situaci 50 na 50 se stejným počtem min nerozhodne nic; hra v průvodci ji nikdy nepoužije.
Část IIPokročilí
7

Hrát rychle a přesněpokročilí

Když logiku ovládáte, zbývá hrát svižně a bez chyb z nepozornosti. Hráči na čas mají dvě zbraně: akordy, které jedním klepnutím odkryjí všechny sousedy splněného čísla, a hraní bez vlajek, které ušetří klepání tam, kde vlajka nic nepřinese. Kolik klepnutí pole minimálně potřebuje, měří 3BV; poměr 3BV k vašim klepnutím je efektivita. A protože hledání min umí pohltit, patří sem i zdravé hraní.

⏱️

Rychlý hráč neklepe rychleji, klepe méně. Kde začátečník odkryje osm polí osmi klepnutími, zkušený hráč dá dvě vlajky a jeden akord – nebo pozná, že prázdná oblast vše odkryje sama, a klepne jen jednou.

Počítadlo 3BV a efektivity
Laboratoř ukáže vyřešené náhodné pole a obarví prázdné oblasti (každá barva = jedno klepnutí na libovolnou nulu v ní). Modrým rámečkem jsou čísla, která nesousedí s žádnou nulou – každé se musí odkrýt zvlášť. Posuvníkem zadejte, kolika klepnutími jste pole vyřešili, a laboratoř spočítá efektivitu.
LABORATOŘ
Model: 3BV = počet prázdných oblastí (souvislá skupina nul i s čísly na okraji) + počet čísel, která nesousedí s žádnou nulou. Efektivita = 3BV / počet klepnutí · 100 %. Pole se rozmístí náhodně (bez záruky řešitelnosti), protože 3BV je vlastnost rozmístění min, ne postupu řešení.
+Teorie: 3BV a efektivita přesně, akordy a hraní bez vlajek, přesnost, mobil, zdravé hraní

7.13BV přesně

Zkratka 3BV znamená Bechtel's Board Benchmark Value: nejmenší počet levých klepnutí, kterým jde pole odkrýt bez vlajek. Klepnutí na libovolnou nulu odkryje celou prázdnou oblast i s čísly na jejím okraji. Čísla, která s žádnou nulou nesousedí, se dají odkrýt jen jednotlivě. Proto:3BV

3BV a efektivita\[ \text{3BV} = \#\text{prázdných oblastí} + \#\{\text{čísla bez sousední nuly}\}, \qquad \text{efektivita} = \frac{\text{3BV}}{\text{počet klepnutí}} \cdot 100\ \% \]
221221122211111111122211221113321111121112123456789123456789
Obr. 7.1Výpočet 3BV na poli 9 × 9 s 10 minami. Tři barevné prázdné oblasti stačí odkrýt třemi klepnutími (oranžový rámeček ukazuje jednu z nul). Třináct čísel v modrém rámečku nesousedí s žádnou nulou a každé chce vlastní klepnutí. 3BV = 3 + 13 = 16.
Tab. 7.13BV klasických polí v simulaci (první klepnutí otevře prázdnou oblast)
PolePolí v simulaciPrůměr5 % polí má nejvýšMedián95 % polí má nejvýš
9 × 9, 10 min50 00014,281422
16 × 16, 40 min20 00063,2466382
30 × 16, 99 min10 000170,3140170202
Spočítáno simulací průvodce. Pole s nízkým 3BV mají velké prázdné oblasti a jdou rychle; pole s vysokým 3BV jsou „kostrbatá“. Proto se časy hráčů srovnávají spolu s 3BV a hráči na čas uvádějí i 3BV za sekundu.

7.2Efektivita, akordy a vlajky

Efektivita 100 % znamená, že jste klepli přesně tolikrát, kolik je 3BV. Do klepnutí se počítají i vlajky a akordy. Bez vlajek je 100 % strop – každé klepnutí odkryje nejvýš jednu jednotku 3BV. S akordy jde strop překonat: jeden akord může odkrýt několik izolovaných čísel najednou, a vyplatí se, když ušetří víc klepnutí, než stály vlajky kolem čísla.

Příklad Kdy se vyplatí akord

Dvojka má dvě miny a pět zakrytých bezpečných sousedů, a ti všichni jsou izolovaná čísla. Bez vlajek: 5 klepnutí. S akordem: 2 vlajky + 1 akord = 3 klepnutí. Kdyby ale bezpečný soused byl jen jeden, akord by stál 3 klepnutí místo jednoho. Pravidlo zkušených hráčů: vlajku dejte, jen když ji využije akord nebo vaše paměť.

7.3Hraní bez vlajek

Část rychlých hráčů vlajky nepoužívá vůbec. Miny si pamatují a klepou jen na bezpečná pole. Ušetří tím klepnutí i čas na přesun myši či prstu. Cenou je větší nárok na paměť a riziko omylu: splněné číslo se nepozná na první pohled a počítadlo min nepomůže – zbývající miny si musíte spočítat sami. Pro učení je lepší vlajky dávat; bez nich hrajte, až techniky z kapitol 2–4 vidíte automaticky.

7.4Přesnost a chyby z nepozornosti

  • Nejdřív důvod, pak klepnutí. Než klepnete, řekněte si technikou, proč je pole bezpečné.
  • Kontrola vlajek před akordem. Akord na číslo se špatnou vlajkou je nejčastější prohra zkušených hráčů.
  • Pozor na sousední pole. Na malém displeji se snadno klepne o pole vedle. Přibližte si pole (lupa) nebo hrajte na větším zařízení.
  • Únava zvyšuje chyby. Když prohráváte „hloupě“, není to smůla – je čas na přestávku.

7.5Na mobilu

Na dotykovém displeji je dlouhý stisk vlajka a krátké klepnutí odkrytí. Kdo se bojí omylu, přepne přepínač ⛏/🚩 a vlajky klepe jako normální tah. Lupa (roztažení dvěma prsty) zvětší pole, aby prst trefil správně. Hra v průvodci dovoluje po výbuchu vrátit tah – využijte to k pochopení chyby, ne k hádání.

Pozor

Hledání min má rychlé partie a okamžitou odměnu – snadno se z „ještě jedné“ stane hodina. Stanovte si předem počet partií nebo čas, dělejte přestávky, protáhněte se a nehrajte dlouho do noci. Hrajte pro radost, bez sázek a peněz.

Mistrovská pomůcka

Trénujte přesnost dřív než rychlost: hrajte bez časomíry, dokud nevyhráváte většinu partií bez chyby, a teprve pak zrychlujte. Efektivita kolem 100 % bez chyb je lepší trénink než rekordní čas s polovinou proher.

7.6Procvičení

1
Pole má 4 prázdné oblasti a 9 čísel bez sousední nuly. Kolik je 3BV?
4 + 9 = 13.
2
Pole má 3BV 64 a vyřešili jste ho 80 klepnutími. Efektivita?
64 / 80 · 100 % = 80 %.
3
Může mít pole 3BV menší, než je počet prázdných oblastí?
Ne. Každá prázdná oblast potřebuje aspoň jedno klepnutí a klepnutí do jedné oblasti druhou neodkryje (jinak by to byla jedna oblast). 3BV je vždy aspoň počet oblastí.
4
Jak může efektivita přesáhnout 100 %?
Jen díky akordům: jedno klepnutí na splněné číslo odkryje několik izolovaných čísel najednou, tedy několik jednotek 3BV. Bez vlajek a akordů je efektivita nejvýš 100 %.
5
Dva hráči vyřešili různá pole 16 × 16 za stejný čas. Kdo byl rychlejší?
Nedá se říct bez 3BV. Pole s 3BV 82 vyřešené za stejný čas jako pole s 3BV 46 je výkon zhruba o tři čtvrtiny lepší – proto se porovnává i 3BV za sekundu.
Co si odnést
  • 3BV = prázdné oblasti + čísla bez sousední nuly; nejmenší počet klepnutí bez vlajek.
  • Efektivita = 3BV / klepnutí · 100 %; akordy se vyplatí jen tam, kde ušetří víc, než stojí vlajky.
  • Přesnost před rychlostí, přestávky a předem daný konec – hra má být radost.
Část IIPokročilí
8

Když hádat musíšpokročilí

V klasické hře, kde miny leží zcela náhodně, se hádat musí. Někdy zbudou dvě pole a jedna mina a nic je neodliší – situace 50 na 50. Jindy se hranice zasekne a zbývají jen pole, o kterých žádné číslo nic neříká. Pak má smysl spočítat pravděpodobnost miny v každém poli a zvolit buď nejbezpečnější tah, nebo tah, který nejvíc prozradí. Hra v tomto průvodci hádání nepotřebuje: každé pole je od prvního klepnutí ověřené řešičem.

🎲

Dobrý hráč hádá, až když musí, a i pak počítá. V simulaci klasické hry na poli 9 × 9 šlo bez hádání vyhrát jen 30 her ze sta; hráč, který při každém zaseknutí počítal pravděpodobnosti, vyhrál 86.

Mapa pravděpodobností
Vyberte zaseknutou pozici z klasické hry (miny zcela náhodně, první pole jen bezpečné). Čím červenější pole, tím vyšší pravděpodobnost miny; číslo v poli je pravděpodobnost v procentech. Zelený rámeček označuje nejbezpečnější pole. Tlačítko „Co prozradí?“ spočítá u každého pole, kolik nových jistých polí by v průměru přineslo jeho odkrytí.
LABORATOŘ
pravděpodobnost miny 0–100 %
Model: přesné pravděpodobnosti z výčtu všech rozmístění hranice, vážených počtem možností, jak rozmístit zbylé miny do polí mimo hranici (kapitola 9). „Co prozradí“: pro pole p a každé číslo v, které by se na něm mohlo ukázat, se spočítá pravděpodobnost v (za předpokladu, že p je bezpečné) a kolik polí by pak bylo jistých včetně počtu min; výsledek je průměr. Kaskádu prázdných oblastí model nepočítá.
Minihra: Kam klepnete?
Ukáže se zaseknutá pozice z klasické hry. Klepněte na pole, které má podle vás nejmenší pravděpodobnost miny. Pravděpodobnosti se ukážou až po volbě. Pokud má stejnou nejmenší pravděpodobnost víc polí, platí kterékoli z nich. Kolo má pět pozic a za aspoň čtyři správné volby získáte 15 XP.
MINIHRA
0 / 5
Jak je minihra ověřená: pozice vznikly simulací klasické hry na poli 9 × 9 s 10 minami, kdy řešič průvodce došel do bodu, kde žádná technika ani počet min nic neodhalí. Vybrané jsou jen pozice, kde se nejmenší pravděpodobnost liší od druhé nejmenší aspoň o 3 procentní body.
+Teorie: kdy se hádat musí, pravděpodobnost pole, nejbezpečnější tah a tah, který nejvíc prozradí, proč tato hra hádání nepotřebuje

8.1Kdy se hádat musí

Pole je pro logiku nerozhodnutelné, když existují dvě rozmístění min, která odpovídají všem číslům i počtu min, a v jednom je na poli mina a ve druhém ne. Nejčistší podoba je situace 50 na 50: dvě pole, jedna mina, obě vidí stejná čísla.

ab213211112341234
Obr. 8.1Situace 50 na 50 na poli 4 × 4 se 3 minami. Obě vlajky jsou jisté a zbývá jedna mina pro pole a nebo b. Obě pole vidí jen jednička a trojka a každé z obou rozmístění dává přesně tatáž čísla – rozhodnout nejde ani podle počtu min.

V simulaci klasické hry (první pole jen bezpečné, klepnutí doprostřed) šlo bez jediného hádání vyhrát jen 29,6 % her 9 × 9, 17,2 % her 16 × 16 a 2,4 % her 30 × 16. Většina her potřebuje hádat hned po prvním klepnutí, protože se neotevře prázdná oblast (kapitola 1). Když první klepnutí prázdnou oblast otevře vždy, stoupnou podíly na 90,3 %, 70,6 % a 16,3 % (kapitola 9).

8.2Pravděpodobnost miny v poli

Pravděpodobnost není podíl rozmístění hranice. Rozmístění, které použije méně min, nechá víc min pro pole mimo hranici – a těch způsobů je obvykle mnohem víc. Každé rozmístění hranice s t minami proto váží tolik, kolika způsoby jde rozmístit zbylých R − t min do I polí mimo hranici.

Pravděpodobnost miny (podrobně v kapitole 9)\[ P(\text{mina v } p) = \frac{\sum_{x \in \mathcal{R},\ x_p = 1} \binom{I}{R - t(x)}}{\sum_{x \in \mathcal{R}} \binom{I}{R - t(x)}}, \qquad P(\text{pole mimo hranici}) = \frac{\mathrm{E}[R - t]}{I} \]
b2ac212345678123
Obr. 8.2Hranice má dvě rozmístění: mina v a, nebo miny v b a c. Vpravo za odkrytým sloupcem je 15 zakrytých polí, o kterých nic nevíme, a zbývají 4 miny. První rozmístění nechá 3 miny na 15 polí (455 způsobů), druhé 2 miny (105 způsobů). Proto P(a) = 455 / 560 ≈ 81 %, i když „podle rozmístění“ by to bylo 50 %. Pole b, c i každé pole vpravo mají po 18,75 %.
Pozor

Intuice „dvě možnosti, tedy 50 %“ selhává, kdykoli se možnosti liší počtem min. V obr. 8.2 je klepnutí na a čtyřikrát nebezpečnější než klepnutí na b – i když obě pole vidí stejné číslo.

8.3Nejbezpečnější tah, nebo tah, který nejvíc prozradí?

Nejbezpečnější tah je pole s nejmenší pravděpodobností miny. Jenže hra pokračuje: dobré je i pole, jehož odkrytí přinese nové jistoty, takže příští hádání odpadne. V laboratoři to měří „Co prozradí?“ – průměrný počet polí, která by po odkrytí byla jistá.

Příklad Pozice 1 a 2 v laboratoři

V pozici 1 má nejmenší pravděpodobnost pole ř8s3 (5,9 %) a jeho odkrytí přinese průměrně 2,25 nové jistoty. Pole ř6s2 by přineslo 3,53 jistoty, ale s dvojnásobným rizikem 11,8 %. V pozici 2 mají čtyři pole stejnou nejmenší pravděpodobnost 5,7 % – a tam rozhoduje informace: ř6s7 přinese průměrně 5,35 jistoty, ř9s7 jen 4,47. Pole, která by prozradila nejvíc (přes 9 jistot), jsou téměř jistě miny – vysoká informace je k ničemu, když pole nepřežijete.

Mistrovská pomůcka

Rozumné pravidlo: vyberte pole s nejmenší pravděpodobností miny a mezi poli, která jsou skoro stejně bezpečná (rozdíl do jednoho až dvou procentních bodů), to, které nejvíc prozradí. V koutě nebo u stěny mívá pole méně sousedů a větší šanci na nulu, která otevře prázdnou oblast.

Jak moc pomáhá dobré hádání? Simulovaný hráč, který při každém zaseknutí klepl na pole s nejmenší pravděpodobností miny, vyhrál v klasické hře 85,9 % her 9 × 9, 69,8 % her 16 × 16 a 34,2 % her 30 × 16 (nejistota nejvýš ±0,9 procentního bodu). Mezi hrami, ve kterých hádat musel, vyhrál 79,9 %, 63,6 % a 32,6 %. Průměrný vítěz hádal 1,18× na poli 9 × 9, 2,10× na 16 × 16 a 4,66× na 30 × 16. Nejde o nejlepší možnou strategii – ta by hleděla i na budoucí tahy – ale ukazuje, kolik dává počítání.

8.4Proč tato hra hádání nepotřebuje

Hra v sekci Hledání min ve 3D i laboratoře průvodce používají jen pole, která řešič z kapitoly 11 dořešil od prvního klepnutí technikami úrovní 1 až 5. Kde se zasekl, generátor z kapitoly 12 přesunul minu a zkusil to znovu. Na takovém poli vždy existuje jistý tah. Když se vám zdá, že musíte hádat, některou techniku jste přehlédli – zeptejte se trenéra.

8.5Procvičení

1
Zbývá jedna mina ve dvou polích, která vidí jen jedna jednička, a jiná zakrytá pole nejsou. Jaká je šance, že klepnutí na jedno z nich vyjde?
50 %. Obě rozmístění mají stejný počet min a stejnou váhu; nic je neodliší.
2
Hranice má rozmístění {a} a {b, c}. Mimo hranici nejsou žádná pole a zbývá 1 mina. Jaká je pravděpodobnost miny v a?
100 % – rozmístění {b, c} potřebuje 2 miny a odpadá. To už není hádání, ale technika Počet min (kapitola 6).
3
Proč mají všechna pole mimo hranici stejnou pravděpodobnost miny?
Žádné číslo je neodlišuje: pro každé rozmístění hranice je každé rozmístění zbylých min mimo hranici stejně možné, takže každé z I polí je minou ve stejném podílu případů – střední počet zbylých min děleno I.
4
Pole na hranici má pravděpodobnost miny 12 %, pole mimo hranici 15 %. Kam klepnout?
Bezpečnější je pole na hranici (12 %). Pole mimo hranici má smysl volit, jen když je skoro stejně bezpečné a má naději otevřít novou prázdnou oblast – např. v rohu. Rozdíl tří procentních bodů je ale na pěti hádáních už znát.
5
Proč klasická hra s náhodnými minami nemůže zaručit, že hádat nebudete muset?
Náhodné rozmístění nebere ohled na to, co půjde odvodit. Situace 50 na 50 vzniká zcela přirozeně – např. dvě pole v rohu oddělená od zbytku minami. Zaručit hru bez hádání jde jen tak, že pole před hrou ověří řešič (kapitola 12).
Co si odnést
  • V klasické hře se hádat musí; s náhodným prvním klepnutím se 9 × 9 vyhraje bez hádání jen asi ve 30 % her.
  • Pravděpodobnost pole = vážený podíl rozmístění; váha = počet způsobů, jak rozmístit zbylé miny mimo hranici.
  • Volte nejbezpečnější pole a mezi skoro stejně bezpečnými to, které nejvíc prozradí.
Část IIIMistr a věda
9

Kombinatorika a pravděpodobnostmistr a věda

Kolika způsoby jde rozmístit 10 min do 81 polí? Proč má pole na hranici jinou pravděpodobnost, než napovídá počet rozmístění? A kolik her vůbec jde vyhrát bez hádání? Odpovědi dává kombinatorika – kombinační čísla C(n, m) a podmíněná pravděpodobnost – a tam, kde vzorec nestačí, simulace: tisíce náhodných polí, která řešič zkusí vyřešit. Všechny podíly v této kapitole jsou z vlastní simulace průvodce s uvedeným počtem her a nejistotou.

📊

Kdyby každý člověk na Zemi zkoušel tisíc rozmístění min za sekundu, prošlo by lidstvo všech 1,9 bilionu rozmístění na malém poli 9 × 9 za necelou sekundu. Na poli 16 × 16 by ani za celou dobu existence vesmíru neprošlo víc než nepatrný zlomek všech rozmístění. Proto se počítá chytře, ne hrubou silou.

Simulace: kolik her jde vyhrát bez hádání?
Zvolte rozměr, pravidlo prvního klepnutí a počet min. Laboratoř rozmístí miny náhodně, klepne doprostřed a zkusí pole dořešit technikami z kapitol 2 až 6. Výsledek je podíl her bez hádání s 95% intervalem. Každý běh přidá do grafu bod; u pole 16 × 16 s pravidlem „prázdná oblast“ je pro srovnání křivka z velké simulace průvodce (4 000 her na bod).
LABORATOŘ
Model: miny se rozmístí rovnoměrně náhodně mimo první pole (pravidlo „jen bezpečné“), nebo mimo první pole a jeho sousedy (pravidlo „prázdná oblast“). Hra „jde bez hádání“, když řešič průvodce odkryje všechna bezpečná pole bez jediného tahu naslepo. 95% interval: p̂ ± 1,96 √(p̂(1 − p̂)/N). Velké pole 30 × 16 se počítá pomaleji (desítky milisekund na hru).
+Teorie: počet rozmístění, vážení rozmístění, hustota a obtížnost, simulace s nejistotou

9.1Kolik je rozmístění min

Rozmístění M min do n = W · H polí je výběr M-prvkové podmnožiny; na pořadí nezáleží. Jejich počet je kombinační číslo:

Počet rozmístění\[ \binom{n}{M} = \frac{n!}{M!\,(n-M)!}, \qquad \binom{81}{10} = 1\,878\,392\,407\,320 \]
Tab. 9.1Klasické rozměry: hustota a počet rozmístění min
PolePolíMinHustotaRozmístění C(n, M)Cifer
9 × 9811012,3 %≈ 1,88 · 101213
16 × 162564015,6 %≈ 1,05 · 104748
30 × 164809920,6 %≈ 5,60 · 10104105
Spočítáno přesně v celých číslech (Python). Kód průvodce pracuje s logaritmy ln C(n, k), aby velká čísla nepřetekla.

9.2Proč se rozmístění váží

Na začátku je každé z C(n, M) rozmístění stejně pravděpodobné. Odkrytá čísla vyřadí rozmístění, která jim odporují; mezi zbylými zůstává rozdělení rovnoměrné (podmíněná pravděpodobnost rovnoměrného rozdělení je zase rovnoměrná). Rozmístění celého pole se ale skládá z rozmístění hranice x s t(x) minami a z rozmístění zbylých R − t(x) min do I polí mimo hranici – a těch je C(I, R − t(x)). Rozmístění hranice proto nejsou stejně pravděpodobná:

Váha rozmístění hranice\[ P(x \mid \text{čísla}) = \frac{\binom{I}{R - t(x)}}{\sum_{y \in \mathcal{R}} \binom{I}{R - t(y)}}, \qquad P(\text{mina v } p) = \sum_{x \in \mathcal{R},\ x_p = 1} P(x \mid \text{čísla}) \]

Poměr vah dvou rozmístění, která se liší o jednu minu, je C(I, r) / C(I, r − 1) = (I − r + 1) / r. Je-li mimo hranici mnoho polí a málo min (začátek hry), jsou rozmístění s méně minami na hranici výrazně pravděpodobnější. V příkladu z obr. 8.2 (I = 15, R = 4) je to 455 : 105, tedy asi 4,3 : 1.

Příklad Ostrůvky a konvoluce

Má-li hranice víc nezávislých ostrůvků, nemusí se procházet všechny jejich kombinace. Stačí u každého ostrůvku spočítat, kolik rozmístění má s 0, 1, 2, … minami, a tyto počty „vynásobit“ jako mnohočleny (konvoluce): koeficient u t v součinu je počet rozmístění celé hranice s t minami. Tak počítá i laboratoř v kapitole 8 – i u 45 zakrytých polí to trvá desítky milisekund.

9.3Hustota a obtížnost

Čím hustěji leží miny, tím menší jsou prázdné oblasti a tím víc čísel nic neříká. Podíl her bez hádání proto s hustotou prudce klesá. Na poli 16 × 16 (první klepnutí do prázdné oblasti) jde pole s 13 minami (5,1 %) vyřešit bez hádání skoro vždy, s 40 minami asi ve 71 % případů a s 64 minami (25 %) jen ve 2 %.

0 %20 %40 %60 %80 %100 %0 %5 %10 %15 %20 %25 %30 %hustota min (miny / pole) · pole 16 × 16 · první klepnutí otevře prázdnou oblast40 min (15,6 %)jde vyřešit bez hádánívyhraje hráč, který při zaseknutí volípole s nejnižší pravděpodobností miny
Obr. 9.1Podíl her 16 × 16, které řešič průvodce dořešil bez hádání (modře, svislé úsečky = 95% interval), a podíl výher hráče, který při zaseknutí klepne na pole s nejnižší pravděpodobností miny (oranžově). 4 000 her na bod.
Tab. 9.2Hustota min a podíl her bez hádání, pole 16 × 16
MinHustotaBez hádáníVýhra s počítánímPrůměrné 3BV
135,1 %99,6 ± 0,2 %99,9 ± 0,1 %10,1
207,8 %97,8 ± 0,5 %99,1 ± 0,3 %20,6
2610,2 %94,2 ± 0,7 %97,8 ± 0,5 %32,0
3212,5 %86,8 ± 1,0 %94,2 ± 0,7 %45,2
3814,8 %75,9 ± 1,3 %89,7 ± 0,9 %58,6
4517,6 %54,9 ± 1,5 %79,3 ± 1,3 %73,8
5119,9 %31,7 ± 1,4 %64,2 ± 1,5 %85,8
5822,7 %9,8 ± 0,9 %41,9 ± 1,5 %98,4
6425,0 %2,3 ± 0,5 %23,0 ± 1,3 %107,3
7730,1 %0 z 4 0002,2 ± 0,5 %120,5
Simulace průvodce, 4 000 her na řádek, první klepnutí doprostřed a do prázdné oblasti. „Výhra s počítáním“: při každém zaseknutí klepnutí na pole s nejnižší přesnou pravděpodobností miny.
Z výzkumu

Dempsey a Guinn (sborník konference FUN 2021) zkoumali pole N × N „zabalená“ do anuloidu (okraje sousedí) pro N = 20, 40 a 80. Podíl min, které jde najít logickým odvozením, podle nich rychle klesá k nule zhruba v pásmu hustot 0,2 až 0,3 a s rostoucím N je pokles strmější – podobně jako fázový přechod u náhodných formulí SAT. Naše simulace má jiné pole i pravidla, ale prudký pokles mezi 15 a 25 % hustoty ukazuje totéž.

9.4Simulace a nejistota

Podíl her bez hádání nejde spočítat vzorcem, a tak ho odhadujeme: N náhodných polí, u každého zkusí řešič dohrát bez hádání. Odhad p̂ je podíl úspěchů a jeho nejistotu popisuje interval spolehlivosti.

95% interval pro podíl\[ \hat p \pm 1{,}96\,\sqrt{\frac{\hat p\,(1-\hat p)}{N}} \qquad (\text{např. } \hat p = 0{,}706,\ N = 20\,000 \Rightarrow \pm 0{,}006) \]
Tab. 9.3Klasické rozměry v simulaci průvodce (klepnutí doprostřed)
PolePrvní klepnutíHerBez hádání (techniky)Dokonalá logikaVýhra s počítáním
9 × 9, 10 minjen bezpečné50 00029,6 ± 0,4 %29,7 %85,9 ± 0,3 %
16 × 16, 40 minjen bezpečné20 00017,2 ± 0,5 %17,2 %69,8 ± 0,6 %
30 × 16, 99 minjen bezpečné10 0002,4 ± 0,3 %2,4 %34,2 ± 0,9 %
9 × 9, 10 minprázdná oblast50 00090,3 ± 0,3 %90,4 %96,2 ± 0,2 %
16 × 16, 40 minprázdná oblast20 00070,6 ± 0,6 %70,7 %87,2 ± 0,5 %
30 × 16, 99 minprázdná oblast10 00016,3 ± 0,7 %16,4 %50,5 ± 1,0 %
„Dokonalá logika“: řešič, který při zaseknutí vyčíslí celou hranici najednou i s počtem min (co nevyřeší on, nevyřeší žádná logika). „Výhra s počítáním“: při zaseknutí klepnutí na pole s nejnižší přesnou pravděpodobností miny; jde o dobrou, ne nejlepší možnou strategii. Několik desítek rozhodnutí na velkých polích, kde byl ostrůvek hranice příliš velký pro přesný výčet, bylo náhradním odhadem.
0 %25 %50 %75 %100 %9 × 9, 10 min29,6 %90,3 %16 × 16, 40 min17,2 %70,6 %30 × 16, 99 min2,4 %16,3 %první klepnutí jen bezpečnéprvní klepnutí otevře prázdnou oblast
Obr. 9.2Podíl her bez hádání podle pravidla prvního klepnutí. Záruka prázdné oblasti po prvním klepnutí změní poměr nejvíc na středních polích: 16 × 16 ze 17 % na 71 %.
Pozor

Čísla z různých zdrojů se liší, protože se liší pravidla (první pole, místo prvního klepnutí, okraje) i definice „vyhrát bez hádání“. Srovnávejte jen simulace se stejnými předpoklady a vždy s počtem her a nejistotou.

9.5Procvičení

1
Kolik je rozmístění 2 min na poli 3 × 3?
C(9, 2) = 9 · 8 / 2 = 36.
2
Mimo hranici je 10 polí a zbývají 3 miny. Kolikrát je rozmístění hranice s 1 minou pravděpodobnější než rozmístění se 2 minami?
Váhy C(10, 2) = 45 a C(10, 1) = 10, poměr 4,5 : 1. Vzorec (I − r + 1)/r pro r = 2: 9 / 2 = 4,5.
3
Simulace 400 her dala 280 výher. Jaký je 95% interval?
p̂ = 0,70, ±1,96 · √(0,7 · 0,3 / 400) ≈ ±0,045: 65,5 % až 74,5 %. Pro dvakrát užší interval je potřeba čtyřikrát víc her.
4
Proč je pravděpodobnost miny v poli mimo hranici na začátku hry zhruba rovna podílu zbývajících min na zakrytých polích?
Na začátku je mimo hranici většina zakrytých polí a hranice spotřebuje jen pár min; zbylé miny se rozprostřou rovnoměrně po polích mimo hranici. Přesně je to střední počet zbylých min (vážený podle kapitoly 9.2) děleno I; čím je hranice menší vůči zbytku, tím blíž je to prostému podílu zbývajících min na zakrytých polích.
5
Kolik her 30 × 16 s 99 minami jde podle simulace vyřešit bez hádání, když první klepnutí otevře prázdnou oblast?
Asi 16 % (16,3 ± 0,7 % z 10 000 her). Proto hra v průvodci nabízí velké pole jen s ověřenými rozmístěními – náhodné pole by bez hádání šlo jen zřídka.
Co si odnést
  • Rozmístění je C(n, M); u 9 × 9 s 10 minami asi 1,9 bilionu.
  • Rozmístění hranice s t minami váží C(I, R − t); méně min na hranici bývá pravděpodobnější.
  • Podíl her bez hádání prudce klesá s hustotou; uvádějte ho vždy s počtem her a intervalem.
Část IIIMistr a věda
10

Složitostmistr a věda

Hledání min je malá hra s velkou matematikou. V roce 2000 R. Kaye dokázal, že rozhodnout, zda čísla na poli vůbec připouštějí nějaké rozmístění min, je NP-úplná úloha – stejně těžká jako slavná úloha splnitelnosti logických formulí (SAT). Pro hráče je ale důležitější jiná otázka: je toto pole jistě bezpečné? Tu Scott, Stege a van Rooij v roce 2011 ukázali jako co-NP-úplnou. Co to znamená, a proč se přesto dá hrát rychle a přesně?

🔌

Z čísel a zakrytých polí se dá postavit drát, kterým běží signál „mina / bez miny“, a z drátů logická hradla. Kdo umí rychle vyřešit libovolné pole hledání min, umí rychle vyhodnotit libovolný logický obvod – a to nikdo neumí.

Laboratoř: drát z čísel
Řada zakrytých polí mezi dvěma řadami jedniček funguje jako drát. Zvolte, zda je v prvním poli mina, a laboratoř dopočítá všechna ostatní pole. Signál se přenese až na konec drátu: pole x mají všechna stejnou hodnotu, pole x̄ opačnou. Délku drátu jde měnit.
LABORATOŘ
Model: každá jednička nad drátem vidí dvě nebo tři pole drátu, takže sousední pole drátu dávají součet 1: a1 + b1 = 1, b1 + a2 = 1, … Z toho a1 = a2 = … a bk = 1 − ak. Laboratoř to ověřuje výčtem: drát má vždy právě dvě rozmístění. Kayeho důkaz používá podobné, jen složitější stavebnice.
Minihra: Konzistentní?
Ukáže se výřez z pole. Část výřezů je ze skutečných her, v části je jedno číslo pozměněné. Rozhodněte, zda existuje aspoň jedno rozmístění min, které odpovídá všem číslům ve výřezu – to je přesně Kayeho úloha konzistence. Odpověď a vysvětlení se ukážou až po volbě. Kolo má šest výřezů a za aspoň pět správných získáte 15 XP.
MINIHRA
0 / 6
Jak je minihra ověřená: každý výřez prošel výčtem všech rozmístění min v jeho zakrytých polích; „konzistentní“ znamená aspoň jedno rozmístění, které odpovídá všem číslům. Šedá pole jsou odkrytá čísla, jejichž sousedé sahají mimo výřez – ta se nekontrolují. Vlajky jsou jisté miny.
+Teorie: konzistence, odvoditelnost a řešitelnost, NP a co-NP, co z toho plyne pro hráče

10.1Tři otázky o poli

  • Konzistence: Je k daným číslům (a vlajkám) aspoň jedno rozmístění min, které jim odpovídá? Odpověď „ano“ jde snadno ověřit – stačí ukázat rozmístění.
  • Odvoditelnost (inference): Dá se z čísel dokázat, že dané pole je bezpečné (nebo mina)? Pole je jistě bezpečné, právě když rozmístění s minou na něm je nekonzistentní.
  • Řešitelnost: Jde známé pole dohrát od daného stavu až do konce bez hádání? To je otázka, kterou si klade generátor v kapitole 12.

10.2Kaye 2000: konzistence je NP-úplná

Úloha patří do třídy NP, když jde odpověď „ano“ ověřit rychle (v polynomiálním čase), jakmile ji někdo předloží – u konzistence stačí rozmístění min a kontrola všech čísel. NP-úplná je, když se na ni dá rychle převést každá úloha z NP. Kaye převedl na konzistenci hledání min splnitelnost logických obvodů: z čísel a zakrytých polí sestavil dráty (řada polí, kterou se přenáší hodnota „mina / bez miny“), negaci a hradla AND a OR. Obvod je splnitelný, právě když je sestavené pole konzistentní.NP-complete

11111111xx̄1xx̄1xx̄11111111
Obr. 10.1Nejjednodušší stavebnice – drát. Pole x (modře) mají všechna stejnou hodnotu, pole x̄ (oranžově) opačnou. Výčet potvrdil, že drát má právě dvě rozmístění: buď jsou miny ve všech x, nebo ve všech x̄. Kayeho skutečné stavebnice pro hradla jsou složitější a zde je nereprodukujeme.
logický obvodsplnitelnost (SAT)pole hledání mindrát, NOT, AND, ORkonzistenceNP-úplná (Kaye 2000)nesplnitelnostUNSAT, co-NP-úplnápole + vybrané polepodobné stavebniceodvoditelnostco-NP-úplná (2011)
Obr. 10.2Dva převody. Nahoře: splnitelnost obvodu → konzistence pole (NP-úplnost, Kaye 2000). Dole: nesplnitelnost → odvoditelnost pole (co-NP-úplnost, Scott, Stege a van Rooij 2011; opravený důkaz Hendrickson a Tockman 2024).

Důsledek: kdyby existoval rychlý (polynomiální) algoritmus na konzistenci libovolně velkých polí, existoval by i pro SAT a platilo by P = NP. Otázka P = NP patří k nejslavnějším otevřeným problémům matematiky; převládá názor, že P ≠ NP. Článek popularizoval Ian Stewart ve sloupku v časopise Scientific American (říjen 2000).

Z historie

Kaye se k hře vrátil i v rukopisu o nekonečných verzích hledání min, ve kterém podle přehledů ukazuje, že na nekonečném poli lze sestavit výpočetně univerzální (Turingovsky úplný) systém. Rukopis jsme nečetli celý, uvádíme ho jen jako zajímavost.

10.3Scott, Stege a van Rooij 2011: hráčova otázka je co-NP-úplná

Hráč nikdy neřeší konzistenci – ví, že pole konzistentní je (miny tam opravdu leží). Ptá se, zda je nějaké pole jistě bezpečné. Odpověď „ano“ znamená „žádné rozmístění s minou na tom poli neexistuje“ a dokazuje se těžko – to je typ otázky z třídy co-NP. Scott, Stege a van Rooij v článku s výmluvným názvem „Minesweeper May Not Be NP-Complete but Is Hard Nonetheless“ ukázali převodem z nesplnitelnosti (UNSAT), že odvoditelnost je co-NP-úplná. Pro hráče je to přesnější model než Kayeho konzistence.

10.4Hendrickson a Tockman 2024: oprava a řešitelnost

Práce MIT Hardness Group, D. Hendricksona a A. Tockmana (konference FUN 2024) přinesla dvě novinky. Autoři našli chybu, která je podle nich ve všech dosud publikovaných důkazech co-NP-úplnosti odvoditelnosti, a dali opravený důkaz. A poprvé zkoumali řešitelnost: je-li známý celý stav hry (včetně min), jde pole dohrát bezpečným klepáním? I tato úloha je podle nich co-NP-úplná.

10.5Co to znamená pro hráče

  • Složitost mluví o nejhorším případě. Na zlomyslně sestaveném obřím poli žádný známý postup rychle nerozhodne, zda je pole jisté. Na běžném poli je hranice rozdělená do malých ostrůvků a výčet je rychlý (kapitola 11).
  • Techniky průvodce stačí skoro na všechno. V simulaci řešič s pěti úrovněmi technik vyřešil bez hádání o nejvýš 0,1 procentního bodu méně polí než „dokonalá logika“ (kapitola 9).
  • Těžké jsou husté pozice. Dempsey a Guinn ukázali, že obtížnost odvozování je největší kolem kritické hustoty min, kde podíl odvoditelných min padá k nule (kapitola 9).
  • Hra bez hádání je ověřená, ne zaručená vzorcem. Protože obecná řešitelnost je těžká, generátor v kapitole 12 nezkouší „všechnu logiku“, ale konkrétní řešič. Pole, které přijme, jistě jde; některá řešitelná pole tím zahodí.
Pozor

NP-úplnost neznamená „hra je nehratelná“ ani „počítač to nevyřeší“. Znamená, že pro libovolně velká a libovolně sestavená pole se nezná algoritmus, jehož čas roste jen polynomiálně. Pole 30 × 16 je pro počítač malé.

Mistrovská pomůcka

Odvoditelnost se v hlavě dělá stejně jako v důkazu: chcete ukázat, že pole je bezpečné, tak předpokládejte, že je tam mina, a hledejte spor. Najdete-li spor, máte důkaz. Najdete-li bez sporu celé rozmístění, pole jisté není – a to je zase odpověď na konzistenci.

10.6Procvičení

1
Proč konzistence patří do NP?
Je-li odpověď „ano“, existuje krátký doklad – konkrétní rozmístění min – a kontrola všech čísel trvá jen úměrně velikosti pole.
2
Jak souvisí odvoditelnost s konzistencí?
Pole p je jistě bezpečné, právě když pole s vlajkou navíc na p je nekonzistentní. Odvoditelnost je tedy „doplněk“ konzistence – proto co-NP místo NP.
3
Drát z obr. 10.1 má 3 články. Kolik má rozmístění min a proč?
Právě 2: první pole volí hodnotu x, vše ostatní je určené rovnicemi „sousední pole drátu dávají součet 1“. Délka drátu počet nezmění.
4
Znamená NP-úplnost, že pole 16 × 16 počítač nevyřeší?
Ne. Jde o růst času pro libovolně velká pole v nejhorším případě. Běžné pole 16 × 16 vyřeší řešič z kapitoly 11 v milisekundách.
5
Co je nového na řešitelnosti v práci z roku 2024?
Ptá se, zda jde známé pole dohrát bez hádání z daného stavu – přesně otázka generátoru hry bez hádání. Autoři ji jako první zkoumali a ukázali, že je co-NP-úplná.
Co si odnést
  • Konzistence pole je NP-úplná (Kaye 2000); stavebnice jsou dráty a logická hradla z čísel.
  • Hráčova otázka „je pole jistě bezpečné?“ je co-NP-úplná (Scott, Stege, van Rooij 2011; opraveno 2024).
  • Složitost mluví o nejhorším případě; na běžných polích stačí techniky a výčet malých ostrůvků.
Část IIIMistr a věda
11

Jak řeší počítačmistr a věda

Pro počítač je každé zakryté pole proměnná s hodnotou 0 (bez miny) nebo 1 (mina) a každé číslo rovnice: součet proměnných kolem něj se rovná počtu chybějících min. Řešit hledání min znamená zjistit, které proměnné mají ve všech řešeních soustavy stejnou hodnotu. Průvodce i hra k tomu používají dva řešiče: lidský, který zkouší techniky z kapitol 2–6 a pojmenuje je (nápověda trenéra, hodnocení obtížnosti), a úplný, který rozdělí hranici na nezávislé ostrůvky, každý vyčíslí a výsledky spojí s počtem min – včetně přesných pravděpodobností.

🖥️

Počítač nemá „cit“ pro vzory. Má jen rovnice, tužku na nuly a jedničky a trpělivost zkoušet. Trik je zkoušet chytře: nikdy nezkoušet to, co už odporuje číslům, a nikdy nekombinovat části, které spolu nesouvisejí.

Řešič krok za krokem
Vyberte pole 8 × 8 podle obtížnosti a klepejte na Další krok. Řešič vždy použije nejjednodušší techniku, která něco odhalí, pojmenuje ji a vysvětlí; modře označí čísla, ze kterých závěr plyne, zeleně bezpečná pole a červeně miny. Přepínač Rovnice ukáže aktuální soustavu: každé číslo s jeho zakrytými sousedy.
LABORATOŘ
Model: lidský řešič průvodce zkouší v každém kroku techniky v pořadí Splněné číslo, Plné číslo, Podmnožina, Překryv čísel, Výčet možností (úseky 3 až 5 čísel, nejvýš 14 polí) a Počet min (od 64 zakrytých polí níž) a provede první, která najde jisté pole. Úroveň pole je nejtěžší použitá technika. Pole jsou z banky ověřených polí průvodce; stejný řešič hodnotí pole ve hře.
+Teorie: soustava rovnic, techniky jako pravidla, prohledávání po ostrůvcích, SAT a celočíselné programování, pravděpodobnostní řešič

11.1Čísla jako soustava rovnic

Pro každé odkryté číslo c se zakrytými sousedy Zc a mc chybějícími minami platí jedna rovnice; k nim patří rovnice pro celkový počet min. Proměnné jsou jen 0 a 1, takže nejde o obyčejnou lineární algebru – soustava může mít mnoho řešení a hledáme, co mají společné.constraint satisfaction

Soustava hledání min\[ \sum_{i \in Z_c} x_i = m_c \ \ (\text{každé číslo } c), \qquad \sum_{i \in U} x_i = R, \qquad x_i \in \{0, 1\} \]
212111111112111111133211111123456789123456789
Obr. 11.1Pole 9 × 9 s 10 minami hned po prvním klepnutí na ř4s5. Hranice má 20 polí ve třech nezávislých ostrůvcích: 16 polí vlevo (modře), 2 pole vpravo nahoře (tyrkysově) a 2 pole vpravo dole (oranžově). Ostrůvky mají 3, 1 a 1 rozmístění, celá hranice 3 · 1 · 1 = 3. Deset zakrytých polí vpravo nahoře leží mimo hranici.
Příklad Rovnice malého ostrůvku

Ostrůvek vpravo nahoře v obr. 11.1 tvoří pole ř1s9 a ř2s9. Čísla kolem dávají: ř1s8: x(ř1s9) + x(ř2s9) = 1, ř2s8: totéž, ř3s8: x(ř2s9) = 1 a ř3s9: x(ř2s9) = 1. Soustava má jediné řešení: ř2s9 je mina, ř1s9 bezpečné. Lidský řešič to najde jako plné číslo (ř3s8 má jediné zakryté pole) a pak splněné číslo (ř1s8 už minu má).

11.2Techniky jako pravidla nad rovnicemi

  • Splněné a plné číslo – rovnice se součtem 0, nebo se součtem rovným počtu proměnných.
  • Podmnožina – odečtení dvou rovnic, kde proměnné jedné jsou podmnožinou druhé.
  • Překryv čísel – meze pro součet ve společné části dvou rovnic.
  • Výčet možností – vyřešení malé podsoustavy (3–5 rovnic) hrubou silou s prořezáváním.
  • Počet min – přidání rovnice pro všechna zakrytá pole a spojení ostrůvků.
Splněné, Plnéúroveň 1Podmnožinaúroveň 2Překryv číselúroveň 3Výčet možnostíúroveň 4Počet minúroveň 5zkouší zleva; první technika, která najde jisté pole, se provede a hledání začne znovu zlevanašla něco?odkrýt bezpečná pole, označit minyano: další krokúroveň pole = nejtěžší použitá technikane: zaseknutodál jen hádat (kap. 8) nebo opravit (kap. 12)
Obr. 11.2Lidský řešič průvodce a hry. V každém kroku zkouší techniky od nejjednodušší a provede první, která najde jisté pole. Úroveň pole je nejtěžší technika, kterou kdy potřeboval.

11.3Prohledávání po ostrůvcích

Úplný řešič nejdřív rozdělí hranici na ostrůvky: dvě pole patří do stejného ostrůvku, když je spojuje řetěz čísel, která vidí obě. Ostrůvky se najdou prohledáváním do šířky. V každém ostrůvku pak prohledávání s návratem (backtracking) zkouší pole po jednom (0, pak 1) a po každém kroku zkontroluje dotčená čísla: kolik min už má a kolik polí jí ještě zbývá. Jakmile číslo nejde splnit, větev se zahodí. Výsledek se ukládá podle počtu min v ostrůvku: kolik rozmístění má s 0, 1, 2, … minami a jak často je v nich každé pole minou.

Spojení ostrůvků s počtem min\[ N(t) = \sum_{t_1 + \dots + t_k = t} \prod_{j} n_j(t_j), \qquad \text{váha}(t) = N(t)\binom{I}{R - t} \]

Tady nj(tj) je počet rozmístění ostrůvku j s tj minami; součet přes rozklady je konvoluce. V obr. 11.1 prošlo prohledávání ostrůvků postupně 37, 4 a 3 uzly; bez rozdělení by teoretický strop byl 220 = 1 048 576 možností místo 216 + 22 + 22 = 65 544. Na velkých polích s mnoha ostrůvky je rozdíl obrovský.

11.4SAT a celočíselné programování v kostce

Soustavu jde předat obecným nástrojům. SAT: každé pole je logická proměnná a podmínka „právě m z těchto polí“ se zapíše jako formule v konjunktivní normální formě (tzv. kardinalitní omezení). Pole je jistě bezpečné, když formule s přidaným „pole je mina“ je nesplnitelná – to je přesně převod z kapitoly 10. Celočíselné programování: rovnice jsou lineární omezení nad proměnnými 0/1; pro každé pole se dá spočítat nejmenší a největší možná hodnota (dvě optimalizační úlohy). Je-li nejmenší 1, je to mina; je-li největší 0, je bezpečné. Obojí je pro malá pole zbytečně těžký kalibr, ale ukazuje, jak hledání min zapadá do obecné teorie úloh s omezeními.

11.5Pravděpodobnostní řešič

Když nic není jisté, úplný řešič má po ruce vše pro přesné pravděpodobnosti (kapitola 9): pro každé pole součet vah rozmístění, ve kterých je minou. Strategie „klepni na pole s nejmenší pravděpodobností“ vyhrála v simulaci 85,9 % klasických her 9 × 9; zlepšení přinášejí strategie, které hledí i na informaci a další tahy (kapitola 8). Váhy se počítají v logaritmech, protože C(I, r) snadno přeteče rozsah čísel s plovoucí čárkou.

Pozor

Výčet ostrůvku roste exponenciálně s jeho velikostí. Kód průvodce proto omezuje výčet v technice Počet min na ostrůvky do 24 polí a počet uzlů na 200 000; větší ostrůvky přeskočí. U technik pro člověka je to v pořádku – takové pozice člověk stejně neřeší výčtem.

Mistrovská pomůcka

I v hlavě se vyplatí „myslet po ostrůvcích“: když se zaseknete, rozdělte hranici na části oddělené odkrytými poli a řešte každou zvlášť. A počítejte, kolik min která část potřebuje – na konci hry to rozhodne (kapitola 6).

11.6Procvičení

1
Trojka má kolem sebe dvě vlajky a zakrytá pole a, b. Jaká je rovnice a co z ní plyne?
a + b = 3 − 2 = 1. Samotná rovnice nerozhodne; potřebuje další číslo.
2
Rovnice a + b + c = 1 a a + b = 1. Co plyne?
Odečtením c = 0: c je bezpečné. To je technika Podmnožina (vzor 1-1).
3
Ostrůvek A má rozmístění s 1 minou (2×) a se 2 minami (1×), ostrůvek B jen se 2 minami (3×). Kolik rozmístění má hranice s 3 minami?
3 miny = 1 v A a 2 v B: 2 · 3 = 6. (4 miny: 1 · 3 = 3.)
4
Jak SAT řešič pozná, že pole je jistě mina?
Přidá podmínku „pole je bez miny“ a zjistí, že formule je nesplnitelná. Pak je pole minou v každém řešení.
5
Proč řešič zkouší techniky od nejjednodušší, i když by výčet našel totéž?
Protože slouží člověku: nápověda má ukázat nejjednodušší cestu a hodnocení obtížnosti má odpovídat tomu, co člověk na poli opravdu potřebuje. Úplný řešič se hodí na pravděpodobnosti a na kontrolu.
Co si odnést
  • Každé číslo je rovnice nad proměnnými 0/1; techniky jsou pravidla, jak z rovnic vyvodit jistotu.
  • Úplný řešič: ostrůvky hranice zvlášť, prohledávání s prořezáváním, spojení konvolucí s počtem min.
  • SAT a celočíselné programování řeší totéž obecně; pro hru stačí chytrý výčet.
Část IIIMistr a věda
12

Tvorba hry bez hádánímistr a věda

Jak vyrobit pole, na kterém se nikdy nemusí hádat? Generátor průvodce postupuje jednoduše: náhodně rozmístí miny mimo první pole a jeho sousedy, pustí lidský řešič od prvního klepnutí a když se řešič zasekne, opraví pole přesunem min – prohodí stav jednoho pole na hranici a jednoho zakrytého pole jinde – a zkusí to znovu. Přijaté pole dostane obtížnost podle nejtěžší potřebné techniky. Stejně vznikla banka polí pro hru ve 3D i pro laboratoře průvodce.

🛠️

Tiskař hlavolamů nezačíná od prázdného listu, ale od náhodného nákresu, který opravuje: kde řešitel uvízne, posune jednu minu a zkusí to znovu. Většinou stačí jedna nebo dvě opravy.

Generátor bez hádání
Zvolte rozměr a nejvyšší dovolenou techniku a stiskněte Vyrobit. Generátor ukáže vyřešené pole, počet oprav, obtížnost a čas. Posuvníkem projdete historii oprav: oranžově jsou zakrytá pole, u kterých se řešič zasekl, modré rámečky označují dvě pole, která generátor prohodil, a zelený rámeček první klepnutí.
LABORATOŘ
Model: stejný algoritmus jako v obr. 12.2: miny mimo první pole a jeho sousedy, lidský řešič s technikami do zvolené úrovně, při zaseknutí prohození náhodného pole hranice s náhodným zakrytým polem mimo hranici (není-li žádné, s jiným polem hranice) opačného stavu; nejvýš 60 oprav, pak nové rozmístění. Hra ve 3D navíc vybírá z banky ověřených polí a pole natočí nebo zrcadlí tak, aby vaše první klepnutí padlo do prázdné startovní oblasti.
+Teorie: náhodné rozmístění, kontrola řešičem, oprava přesunem min, hodnocení obtížnosti, varianty

12.1Od náhodného pole k ověřenému

náhodné minymimo první pole a jeho sousedyřešič od 1. klepnutítechniky úrovní 1 až 5vyřešeno?ano → hotovo, určit úroveňoprava přesunem minprohodit pole hranice a vnitřkune (zaseknuto)nejvýš 60 oprav, jinak nové rozmístění od začátku
Obr. 12.2Generátor pole bez hádání. Řešič je lidský řešič z kapitoly 11; oprava přesunem min zachová počet min i první pole.
  1. Náhodné rozmístění. M min se rozmístí rovnoměrně náhodně na pole mimo první pole a jeho sousedy – první klepnutí tak vždy otevře prázdnou oblast.
  2. Kontrola řešičem. Řešič odkryje první pole a postupuje technikami úrovní 1 až 5. Dojde-li do konce, je pole přijato.
  3. Oprava přesunem min. Když se řešič zasekne, generátor vezme náhodné zakryté pole na hranici a náhodné zakryté pole mimo hranici s opačným stavem (mina ↔ bez miny) a prohodí je. Čísla kolem se změní a řešič začne znovu od prvního klepnutí.
  4. Hodnocení. Přijaté pole dostane úroveň podle nejtěžší techniky, kterou řešič potřeboval.
zaseknuto: dál jen hádat
111111122111221112132144121234567812345678
po prohození: řešitelné logikou
11111111221112311121332144121234567812345678
Obr. 12.1Oprava přesunem min na poli 8 × 8 s 10 minami. Vlevo stav, ve kterém se řešič zasekl: zbývají čtyři zakrytá pole (oranžově) a žádná technika ani počet min nic neodhalí. Generátor prohodí stav polí ř1s8 a ř2s8 (rámečky) – mina se přesune o pole níž. Vpravo výsledné pole, které už řešič dořeší; nejtěžší potřebná technika je Počet min (úroveň 5).

12.2Jak dobře to funguje

Tab. 12.1Generátor průvodce: úspěšnost, opravy a obtížnost (první klepnutí doprostřed)
PolePokusůÚspěšnýchPřijato bez opravyOprav: průměr / 90 % pokusů nejvýš / max.Čas na pokus
9 × 9, 10 min2 00096,2 %90,2 %0,09 / 0 / 60,2 ms
16 × 16, 40 min1 00088,7 %69,4 %0,33 / 1 / 62,9 ms
30 × 16, 99 min30073,7 %17,3 %2,62 / 7 / 1625 ms
Spočítáno skriptem nad stejným kódem jako laboratoř (Node.js, jeden běh; časy se liší podle počítače). Neúspěšný pokus (oprava nepomohla do 60 kroků nebo nebylo co prohodit) generátor zahodí a začne novým rozmístěním. Opravy (průměr, 90. percentil a maximum) jsou počítané přes úspěšné pokusy.
Tab. 12.2Úrovně vyrobených polí (podíl z úspěšných)
Pole12345
9 × 9, 10 min72,2 %15,5 %2,3 %0,2 %9,8 %
16 × 16, 40 min32,7 %39,0 %11,6 %1,4 %15,3 %
30 × 16, 99 min0,5 %24,0 %35,3 %6,3 %33,9 %
Úroveň 4 (výčet možností) je vzácná: většinu situací, které by vyčíslil, vyřeší už překryv čísel nebo je rozhodne až počet min na konci. Hra proto pole úrovně 4 sbírá do banky cíleně.
Pozor

Opravená pole nejsou „náhodná pole, která náhodou jdou vyřešit“. Oprava posouvá miny tak, aby řešič prošel, a mění tím rozdělení polí – třeba podíl úrovní. Pro hru to nevadí, pro statistiku ano: podíly z kapitoly 9 jsou proto počítané na neopravených náhodných polích.

12.3Obtížnost podle nejtěžší techniky

Hra i průvodce hodnotí pole podle nejtěžší techniky, kterou lidský řešič potřeboval: úroveň 1 Splněné a Plné číslo, 2 Podmnožina, 3 Překryv čísel, 4 Výčet možností, 5 Počet min. Je to jednoduché a průhledné měřítko – víte, co budete potřebovat – ale ne jediné možné. Jiné řešiče počítají i počet těžkých kroků, délku řetězců úvah nebo 3BV. Dvě pole stejné úrovně se proto mohou hrát různě těžce: jedno potřebuje podmnožinu jednou na konci, druhé desetkrát.

Příklad Proč úroveň 5 není „nejtěžší“

Na poli úrovně 5 může stačit jediný krok s počtem min v posledním koutě, zatímco pole úrovně 3 vyžaduje deset překryvů. Číslo úrovně říká, jakou techniku budete potřebovat, ne kolikrát. Pole z obr. 12.1 má úroveň 5, ale vedle devíti plných a sedmi splněných čísel potřebuje jen jednu podmnožinu a jeden krok s počtem min.

12.4Proč generátor nepotřebuje „dokonalou logiku“

Rozhodnout, zda jde známé pole dohrát bez hádání, je obecně co-NP-úplné (kapitola 10). Generátor proto nezkoumá „všechnu možnou logiku“, ale jen to, co zvládne jeho řešič. Je to postačující podmínka: co řešič vyřeší, jde jistě bez hádání. Některá řešitelná pole tím zahodí, ale v simulaci z kapitoly 9 se podíl polí bez hádání u řešiče a u „dokonalé logiky“ lišil nejvýš o 0,1 procentního bodu. Výhoda: pole je řešitelné přesně těmi technikami, které průvodce učí, a nápověda trenéra vždy najde další krok.

12.5Varianty

  • Jiné tvary polí: šestiúhelníková a trojúhelníková pole mění počet sousedů (6, resp. až 12) a s tím i vzory; prostorové verze ve 3D mají až 26 sousedů.
  • Jiné sousedství: předchůdce Mined-Out z roku 1983 počítal jen miny ve vodorovně a svisle sousedních polích, tedy čtyři sousedy.
  • Pole bez okrajů: anuloid, kde okraje sousedí, se používá ve výzkumu (kapitola 9).
  • Víc min v poli: některé verze dovolují na poli víc min a číslo pak sčítá všechny.

Generátor bez hádání funguje u všech variant stejně: stačí upravit seznam sousedů a řešič. Vzory jako 1-2-1 se ale na šestiúhelnících mění.

Mistrovská pomůcka

Chcete-li si pole bez hádání vyrobit ručně (třeba pro dítě), začněte od řešení: nakreslete miny, dopište čísla a sami ho vyřešte od zvoleného prvního pole. Kde se zaseknete, posuňte jednu minu o pole vedle a zkuste to znovu – přesně jako generátor.

12.6Procvičení

1
Proč generátor nedává miny ani na sousedy prvního pole?
Aby první pole bylo nula a otevřelo prázdnou oblast. Jinak by hráč často začínal osamoceným číslem, ze kterého nic neplyne, a musel by hned hádat znovu – při klepnutí doprostřed pole 9 × 9 se to v klasické hře stane asi ve dvou případech ze tří (kapitola 1).
2
Mění oprava přesunem min počet min?
Ne. Prohazuje se pole s minou a pole bez miny, takže celkový počet zůstává.
3
Proč se hledá pole opačného stavu mimo hranici, a ne libovolné?
Prohození dvou polí se stejným stavem nic nezmění. Pole mimo hranici se volí proto, že jeho změna neovlivní čísla, která už jsou odkrytá, a mění hlavně situaci na hranici, kde se řešič zasekl.
4
Kolik procent polí 30 × 16 s 99 minami přijme generátor bez jediné opravy?
Asi 17 % pokusů (52 ze 300). To souhlasí s kapitolou 9: bez hádání jde jen asi 16 % náhodných polí tohoto rozměru.
5
Pole má úroveň 2. Co to říká hráči?
Pole jde dořešit splněným a plným číslem a podmnožinou (vzory 1-1 a 1-2); překryv čísel, výčet ani počet min nejsou potřeba. Kolikrát bude podmnožina potřeba, úroveň neříká.
Co si odnést
  • Generátor: náhodné miny mimo první pole a sousedy, kontrola řešičem, při zaseknutí prohození pole hranice a pole mimo ni.
  • Obtížnost = nejtěžší technika, kterou řešič potřeboval; ne počet kroků.
  • Řešič je postačující test: co vyřeší, jde bez hádání – a nápověda vždy najde další krok.
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 ve 3D
ÚroveňTechniky (přesné názvy z nápovědy hry)Kapitola
1Splněné číslo, Plné číslo2
2+ Podmnožina (vzory 1-1 a 1-2)3
3+ Překryv čísel (vzory 1-2-1, 1-2-2-1, redukce o vlajky)4
4+ Výčet možností (úsek hranice kolem 3 až 5 čísel)5
5+ Počet min (konec hry, pole mimo hranici)6
bez hádání nejdeněkde rozhoduje jen pravděpodobnost8
Řešič průvodce zkouší techniky v pořadí Splněné číslo, Plné číslo, Podmnožina, Překryv čísel, Výčet možností a Počet min a vždy provede první, která najde jisté pole. Úroveň pole je nejvyšší úroveň použité techniky.

Vzorce na jednom místě

Značení: v počet vlajek kolem čísla, m kolik min číslu chybí, z počet jeho zakrytých sousedů bez vlajky, Z jejich množina, M počet min na poli, R zbývající miny, I počet zakrytých polí mimo hranici, t miny v rozmístění hranice.

Číslo a co mu chybí (kap. 1, 2)\[ \text{číslo}(p) = \#\{\, q \in N(p) : \text{na } q \text{ je mina} \,\}, \qquad m(p) = \text{číslo}(p) - v(p), \qquad 0 \le m(p) \le z(p) \]
Splněné a plné číslo (kap. 2)\[ m = 0 \ \Rightarrow\ \text{zakrytí sousedé bezpeční}, \qquad m = z > 0 \ \Rightarrow\ \text{zakrytí sousedé jsou miny} \]
Podmnožina (kap. 3)\[ Z_A \subset Z_B \ \Rightarrow\ \#\text{min v } Z_B \setminus Z_A = m_B - m_A \]
Překryv čísel (kap. 4; S společná pole, A′ a B′ vlastní pole čísel)\[ \max\big(0,\ m_A - |A'|,\ m_B - |B'|\big) \ \le\ s\ \le\ \min\big(|S|,\ m_A,\ m_B\big) \]
Výčet a ostrůvky (kap. 5)\[ \mathcal{R} = \Big\{ x \in \{0,1\}^k : \ \ell_c \le \sum_{i \in Z_c} x_i \le u_c \Big\}, \qquad |\mathcal{R}_{\text{hranice}}| = \prod_j |\mathcal{R}_j| \]
Počet min (kap. 6)\[ R = M - v, \qquad \text{rozmístění hranice s } t \text{ minami je možné} \iff 0 \le R - t \le I \]
3BV a efektivita (kap. 7)\[ \text{3BV} = \#\text{prázdných oblastí} + \#\{\text{čísla bez sousední nuly}\}, \qquad \text{efektivita} = \frac{\text{3BV}}{\text{počet klepnutí}} \cdot 100\ \% \]
Pravděpodobnost miny (kap. 8, 9)\[ P(\text{mina v } p) = \frac{\sum_{x \in \mathcal{R},\ x_p = 1} \binom{I}{R - t(x)}}{\sum_{x \in \mathcal{R}} \binom{I}{R - t(x)}}, \qquad P(\text{pole mimo hranici}) = \frac{\mathrm{E}[R - t]}{I} \]
Počet rozmístění a interval (kap. 9)\[ \binom{n}{M} = \frac{n!}{M!\,(n-M)!}, \qquad \hat p \pm 1{,}96\,\sqrt{\frac{\hat p\,(1-\hat p)}{N}} \]
Soustava hledání min (kap. 11)\[ \sum_{i \in Z_c} x_i = m_c \ \ (\text{každé číslo } c), \qquad \sum_{i \in U} x_i = R, \qquad x_i \in \{0, 1\} \]

Čísla z kapitol

Tab. B.2Přehled spočítaných údajů
ÚdajHodnotaKde
rozmístění 10 min na poli 9 × 9: C(81, 10)1 878 392 407 320kap. 9
hustota min 9 × 9 / 16 × 16 / 30 × 1612,3 / 15,6 / 20,6 %kap. 9
bezpečné první klepnutí doprostřed 9 × 9 otevře prázdnou oblast32,6 %kap. 1
hry bez hádání, první pole jen bezpečné: 9 × 9 / 16 × 16 / 30 × 1629,6 / 17,2 / 2,4 %kap. 9
hry bez hádání, první klepnutí otevře prázdnou oblast90,3 / 70,6 / 16,3 %kap. 9
výhra s počítáním pravděpodobností (prázdná oblast)96,2 / 87,2 / 50,5 %kap. 9
průměrné 3BV: 9 × 9 / 16 × 16 / 30 × 1614,2 / 63,2 / 170,3kap. 7
generátor bez hádání: úspěšné pokusy 9 × 9 / 16 × 16 / 30 × 1696,2 / 88,7 / 73,7 %kap. 12
úroveň 1 / 2 / 3 / 4 / 5 / bez hádání nejde, náhodná pole 9 × 964,5 / 16,0 / 2,1 / 0,2 / 7,5 / 9,7 %úvod, tab. 0.2
PřílohaC

Zdroje a předpoklady

Historické údaje a výsledky výzkumu byly ověřeny na uvedených zdrojích. Ověřeno 8. 11. 2026.

Historie hry

  • Encyklopedické heslo Minesweeper (video game) (Wikipedie, anglická verze) a prameny v něm citované – hra Mines pro SunOS (1987, Tom Anderson), verze pro Windows od Roberta Donnera a Curta Johnsona, Microsoft Entertainment Pack 1990, součást Windows 3.1 (1992), vzhled s květinami ve Windows Vista, Windows 8 (2012) bez hry, galerie variant (šestiúhelníková, trojúhelníková, prostorová pole, víc min v poli). Ověřeno 8. 11. 2026.
  • Encyklopedické heslo Microsoft Minesweeper (Wikipedie, anglická verze) – Curt Johnson a původní verze pro OS/2, převod do Windows, změny vzhledu ve Windows Vista. Ověřeno 8. 11. 2026.
  • Encyklopedické heslo Mined-Out (Wikipedie, anglická verze) – autor Ian Andrew, vydavatel Quicksilva, 1983, ZX Spectrum, detektor počítající miny ve vodorovně a svisle sousedních polích. Ověřeno 8. 11. 2026.
  • Encyklopedické heslo Hledání min (Wikipedie, česká verze) – české jméno hry. Ověřeno 8. 11. 2026.
  • Minesweepergame.com: přehled historie hry – Relentless Logic jako předchůdce a pravidlo prvního klepnutí v různých verzích (podle tohoto zdroje prázdná oblast od verze ve Windows Vista). Ověřeno 8. 11. 2026.
  • Komunitní stránky hráčů hledání min na čas (minesweeper.online a další) – definice 3BV, efektivity a hraní bez vlajek. Ověřeno 8. 11. 2026.

Složitost a výzkum

  • Kaye, R. (2000): Minesweeper is NP-complete. The Mathematical Intelligencer 22(2), 9–15. DOI 10.1007/BF03025367. Ověřeno 8. 11. 2026 (bibliografické údaje a abstrakt).
  • Stewart, I. (2000): sloupek Mathematical Recreations o Kayeho výsledku. Scientific American, říjen 2000. Ověřeno 8. 11. 2026 (údaj o vydání).
  • Scott, A.; Stege, U.; van Rooij, I. (2011): Minesweeper May Not Be NP-Complete but Is Hard Nonetheless. The Mathematical Intelligencer 33(4), 5–17. DOI 10.1007/s00283-011-9256-x. Ověřeno 8. 11. 2026 (bibliografické údaje a abstrakt).
  • MIT Hardness Group; Hendrickson, D.; Tockman, A. (2024): Complexity of Planar Graph Orientation Consistency, Promise-Inference, and Uniqueness, with Applications to Minesweeper Variants. In: 12th International Conference on Fun with Algorithms (FUN 2024), LIPIcs 291, 25:1–25:20. DOI 10.4230/LIPIcs.FUN.2024.25 – znovu odvozená NP-úplnost konzistence, oprava chyby v dřívějších důkazech pro odvoditelnost, co-NP-úplnost úlohy, zda jde známé pole vyhrát jen bezpečnými klepnutími. Ověřeno 8. 11. 2026.
  • Dempsey, R.; Guinn, C.: A Phase Transition in Minesweeper. In: Fun with Algorithms (FUN 2021), LIPIcs 157. DOI 10.4230/LIPIcs.FUN.2021.12 – pole na anuloidu pro N = 20, 40 a 80, podíl odvoditelných min klesá k nule zhruba mezi hustotami 0,2 a 0,3, obtížnost je největší kolem přechodu. Ověřeno 8. 11. 2026.
  • Kaye, R.: rukopis o nekonečných verzích hledání min (Turingovská úplnost). Známý jen z přehledů a citací; plný text nebyl ověřen.

Modelové předpoklady laboratoří

Všechna čísla, tabulky, pravděpodobnosti a simulace počítá kód průvodce (stejné jádro jako laboratoře). Lidský řešič zkouší techniky v pevném pořadí podle tabulky B.1; Výčet možností prohledává úseky kolem 3 až 5 čísel s nejvýš 14 poli, Počet min se zkouší od 64 zakrytých polí níž a s ostrůvky hranice do 24 polí. Jiný řešič s jinými technikami nebo limity může stejnému poli přidělit jinou úroveň. Každá úloha v textu, misích a minihrách je ověřená výčtem všech rozmístění min: „jistě“ znamená stejný stav ve všech rozmístěních, „nedá se určit“ existenci rozmístění s minou i bez ní (včetně počtu min), „konzistentní“ aspoň jedno rozmístění. Pravděpodobnosti jsou přesné: rozmístění hranice se váží počtem doplnění C(I, R − t). Údaj „co prozradí“ v kapitole 8 nepočítá s kaskádou prázdných oblastí. Simulace v úvodu a v kapitolách 1, 7 a 9 používají první klepnutí doprostřed pole a rovnoměrně náhodné rozmístění min mimo zakázaná pole; počty her jsou u tabulek. Několik desítek rozhodnutí na velkých polích ve sloupci „výhra s počítáním“ bylo náhradním odhadem, protože ostrůvek hranice byl na přesný výčet příliš velký. Generátor v kapitole 12 a hra ve 3D vyrábějí pole opravou přesunem min; taková pole nejsou rovnoměrně náhodná a jejich podíly úrovní se liší od tabulky 0.2.

Co zůstává nejisté

Rok vydání a autory hry Relentless Logic uvádějí databáze her různě (1984, nebo 1985). Rozpis zkratky 3BV a jméno Bechtel známe jen z komunitních zdrojů hráčů. Podobu Kayeho stavebnic pro logická hradla jsme převzali z popisů a přehledů, ne z plného textu článku; drát v kapitole 10 je naše zjednodušená stavebnice ověřená výčtem. Obsah článku Scotta, Stege a van Rooije známe z abstraktu a sekundárních popisů. Od které verze které hry platí pravidlo bezpečného prvního klepnutí a od které prázdné oblasti, známe jen z webu minesweepergame.com. Kayeho rukopis o nekonečných verzích hry jsme neověřili a v textu je uveden s výhradou.

Interaktivní průvodce Hledání min (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 ani programy; zmínky o verzích hry v operačních systémech jsou historické.