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.
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
| Kapitola | Úroveň | Co se naučíte |
|---|---|---|
| 1 Pravidla, pojmy a historie | základy | co 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í tahy | základy | prázdná oblast, kde začít, splněné a plné číslo, vlajky, akord, typické omyly u okrajů a rohů |
| 3 Podmnožina | základy | vzory 1-1 a 1-2 u stěny i uprostřed, jak podmnožinu vidět, odečítání min |
| 4 Překryv čísel | základy | vzory 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 hry | pokroč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ěpodobnost | mistr a věda | poč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žitost | mistr a věda | NP-ú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ěda | ná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šší.
| Úroveň | Nejtěžší potřebná technika | Kapitola | Podíl polí 9 × 9 | Podíl polí 16 × 16 |
|---|---|---|---|---|
| 1 | Splněné číslo, Plné číslo | 2 | 64,5 % | 24,9 % |
| 2 | Podmnožina (vzory 1-1, 1-2) | 3 | 16,0 % | 28,3 % |
| 3 | Překryv čísel (1-2-1, 1-2-2-1, redukce) | 4 | 2,1 % | 6,3 % |
| 4 | Výčet možností | 5 | 0,2 % | 0,7 % |
| 5 | Počet min | 6 | 7,5 % | 10,4 % |
| bez hádání nejde | někde je nutné hádat | 8 | 9,7 % | 29,4 % |
Čtyři druhy rámečků
Konkrétní situace na poli nebo výpočet, který si můžete ověřit v laboratoři.
Jak hra vznikla, kdo ji naprogramoval a co o ní dokázali matematici.
Rychlé pravidlo, zkratka nebo návyk, který používají zkušení hráči.
Č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.
Hledání min ve 3D
🎮 Zpět ke hře Hra je nahoře na této stránce. Tlačítkem 📲 v její liště si ji nainstalujete do telefonu nebo počítače a hrajete i bez připojení.
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.
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.
+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:
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ě.
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á.
| Pole | Uvnitř (8 sousedů) | U okraje (5) | V rohu (3) | Celkem |
|---|---|---|---|---|
| 9 × 9 | 49 | 28 | 4 | 81 |
| 16 × 16 | 196 | 56 | 4 | 256 |
| 30 × 16 | 392 | 84 | 4 | 480 |
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.
| Pole | Hustota min | Uvnitř | U okraje | V rohu |
|---|---|---|---|---|
| 9 × 9, 10 min | 12,3 % | 32,6 % | 50,3 % | 66,6 % |
| 16 × 16, 40 min | 15,6 % | 25,0 % | 42,3 % | 59,8 % |
| 30 × 16, 99 min | 20,6 % | 15,4 % | 31,3 % | 49,8 % |
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).
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
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í.
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.
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í
- Čí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í.
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.
+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.
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
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
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
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.
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í
- 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.
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.
+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
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.
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á.
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).
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.
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í
- 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.
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.
+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
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.
- 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.
- 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.
- Dvojka: má už miny b a d, je splněná – c je bezpeč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ě.
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.
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.
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í
- 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í.
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á.
+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
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
Čí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ě:
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:
- 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.
- Tedy b je mina. Dvojka na ř6s1 i trojka na ř6s3 jsou tím splněné, takže a a c jsou bezpečná.
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.
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í
- 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í.
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.
+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
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.
6.2Vyloučení rozmístění podle počtu
Čí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ý.
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.
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í
- 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.
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.
+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
| Pole | Polí v simulaci | Průměr | 5 % polí má nejvýš | Medián | 95 % polí má nejvýš |
|---|---|---|---|---|---|
| 9 × 9, 10 min | 50 000 | 14,2 | 8 | 14 | 22 |
| 16 × 16, 40 min | 20 000 | 63,2 | 46 | 63 | 82 |
| 30 × 16, 99 min | 10 000 | 170,3 | 140 | 170 | 202 |
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.
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í.
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.
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í
- 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.
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.
+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.
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.
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á.
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.
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í
- 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í.
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.
+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:
| Pole | Polí | Min | Hustota | Rozmístění C(n, M) | Cifer |
|---|---|---|---|---|---|
| 9 × 9 | 81 | 10 | 12,3 % | ≈ 1,88 · 1012 | 13 |
| 16 × 16 | 256 | 40 | 15,6 % | ≈ 1,05 · 1047 | 48 |
| 30 × 16 | 480 | 99 | 20,6 % | ≈ 5,60 · 10104 | 105 |
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á:
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.
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 %.
| Min | Hustota | Bez hádání | Výhra s počítáním | Průměrné 3BV |
|---|---|---|---|---|
| 13 | 5,1 % | 99,6 ± 0,2 % | 99,9 ± 0,1 % | 10,1 |
| 20 | 7,8 % | 97,8 ± 0,5 % | 99,1 ± 0,3 % | 20,6 |
| 26 | 10,2 % | 94,2 ± 0,7 % | 97,8 ± 0,5 % | 32,0 |
| 32 | 12,5 % | 86,8 ± 1,0 % | 94,2 ± 0,7 % | 45,2 |
| 38 | 14,8 % | 75,9 ± 1,3 % | 89,7 ± 0,9 % | 58,6 |
| 45 | 17,6 % | 54,9 ± 1,5 % | 79,3 ± 1,3 % | 73,8 |
| 51 | 19,9 % | 31,7 ± 1,4 % | 64,2 ± 1,5 % | 85,8 |
| 58 | 22,7 % | 9,8 ± 0,9 % | 41,9 ± 1,5 % | 98,4 |
| 64 | 25,0 % | 2,3 ± 0,5 % | 23,0 ± 1,3 % | 107,3 |
| 77 | 30,1 % | 0 z 4 000 | 2,2 ± 0,5 % | 120,5 |
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.
| Pole | První klepnutí | Her | Bez hádání (techniky) | Dokonalá logika | Výhra s počítáním |
|---|---|---|---|---|---|
| 9 × 9, 10 min | jen bezpečné | 50 000 | 29,6 ± 0,4 % | 29,7 % | 85,9 ± 0,3 % |
| 16 × 16, 40 min | jen bezpečné | 20 000 | 17,2 ± 0,5 % | 17,2 % | 69,8 ± 0,6 % |
| 30 × 16, 99 min | jen bezpečné | 10 000 | 2,4 ± 0,3 % | 2,4 % | 34,2 ± 0,9 % |
| 9 × 9, 10 min | prázdná oblast | 50 000 | 90,3 ± 0,3 % | 90,4 % | 96,2 ± 0,2 % |
| 16 × 16, 40 min | prázdná oblast | 20 000 | 70,6 ± 0,6 % | 70,7 % | 87,2 ± 0,5 % |
| 30 × 16, 99 min | prázdná oblast | 10 000 | 16,3 ± 0,7 % | 16,4 % | 50,5 ± 1,0 % |
Čí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í
- 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.
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í.
+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
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).
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í.
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é.
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í
- 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ů.
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í.
+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
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ů.
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.
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.
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.
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í
- 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.
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.
+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é 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.
- Kontrola řešičem. Řešič odkryje první pole a postupuje technikami úrovní 1 až 5. Dojde-li do konce, je pole přijato.
- 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í.
- Hodnocení. Přijaté pole dostane úroveň podle nejtěžší techniky, kterou řešič potřeboval.
12.2Jak dobře to funguje
| Pole | Pokusů | Úspěšných | Přijato bez opravy | Oprav: průměr / 90 % pokusů nejvýš / max. | Čas na pokus |
|---|---|---|---|---|---|
| 9 × 9, 10 min | 2 000 | 96,2 % | 90,2 % | 0,09 / 0 / 6 | 0,2 ms |
| 16 × 16, 40 min | 1 000 | 88,7 % | 69,4 % | 0,33 / 1 / 6 | 2,9 ms |
| 30 × 16, 99 min | 300 | 73,7 % | 17,3 % | 2,62 / 7 / 16 | 25 ms |
| Pole | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 9 × 9, 10 min | 72,2 % | 15,5 % | 2,3 % | 0,2 % | 9,8 % |
| 16 × 16, 40 min | 32,7 % | 39,0 % | 11,6 % | 1,4 % | 15,3 % |
| 30 × 16, 99 min | 0,5 % | 24,0 % | 35,3 % | 6,3 % | 33,9 % |
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.
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í.
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í
- 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.
Slovníček
Česká hesla s anglickým termínem. Hledat lze v obou jazycích.
Vzorce a přehledy
Techniky podle úrovní
| Úroveň | Techniky (přesné názvy z nápovědy hry) | Kapitola |
|---|---|---|
| 1 | Splněné číslo, Plné číslo | 2 |
| 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í nejde | někde rozhoduje jen pravděpodobnost | 8 |
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.
Čísla z kapitol
| Údaj | Hodnota | Kde |
|---|---|---|
| rozmístění 10 min na poli 9 × 9: C(81, 10) | 1 878 392 407 320 | kap. 9 |
| hustota min 9 × 9 / 16 × 16 / 30 × 16 | 12,3 / 15,6 / 20,6 % | kap. 9 |
| bezpečné první klepnutí doprostřed 9 × 9 otevře prázdnou oblast | 32,6 % | kap. 1 |
| hry bez hádání, první pole jen bezpečné: 9 × 9 / 16 × 16 / 30 × 16 | 29,6 / 17,2 / 2,4 % | kap. 9 |
| hry bez hádání, první klepnutí otevře prázdnou oblast | 90,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 × 16 | 14,2 / 63,2 / 170,3 | kap. 7 |
| generátor bez hádání: úspěšné pokusy 9 × 9 / 16 × 16 / 30 × 16 | 96,2 / 88,7 / 73,7 % | kap. 12 |
| úroveň 1 / 2 / 3 / 4 / 5 / bez hádání nejde, náhodná pole 9 × 9 | 64,5 / 16,0 / 2,1 / 0,2 / 7,5 / 9,7 % | úvod, tab. 0.2 |
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.