Návod na úlohu: Hledání min

Chci vám představit dva užitečné triky pro řešení úlohy Hledání min.

Podívejte se na následující zadání:

Úkol zní jednoduše: V obrazci se nachází přesně 25 min, v každém prázdném políčku nejvýše jedna. Zakreslete jejich pozice, když každé číslo udává, kolik min s ním sousedí (stranou nebo rohem).

Tato úloha byla předložena na jaře 2013 na FED párty. Můžete si ji zkusit vyřešit. Úplně na konci této stránky je pro kontrolu i řešení.

Na následujících dvou obrázcích chci demonstrovat dvě trochu pokročilé techniky pro řešení tohoto typu logické úlohy.

A) Využití jednoznačnosti řešení

Víme dopředu, že úloha má jediné řešení. Víme, že okolo červeně označené jedničky má být přesně jedna mina. Kdyby ve správném řešení patřila na jedno z podbarvených polí, nemohli bychom rozhodnout na které. (Protože na tato pole nezasahuje vliv jiného čísla než té jedničky.) A to je ovšem spor s jednoznačností. Ve výsledku můžeme směle obě červená políčka proškrtnout, mina tam nebude.

B) Využití přesného počtu min

Dále můžeme využít toho, že známe přesný počet min. Na obrázku je obrazec rozdělen do několika oblastí, které se vzájemně nepřekrývají (to je důležité!). Například při pravém okraji máme skupinu 5 zelených polí, které představují kompletní okolí označené trojky. Tedy víme, že se v této podoblasti vyskytují přesně 3 miny. Analogicky u dalších červených, modrých a zelených čísel.

Když sečteme všechna červená, modrá a zelená čísla, máme spotřebováno (3+2+3 + 1+6 + 3+3+2 =) 23 min. Když se podíváme na žlutou pětku, vidíme, že sousedí s jedním červeným a dvěma zelenými políčky. Tam uplatní nejvýše 3 miny a vidíme, že minimálně 2 miny se budou vyskytovat ve žlutých polích.

V obrazci má být min přesně 25, logickým důsledkem tak je, že všechna políčka, která zůstala bílá budou v řešení prázdná, bez miny. Navíc musíme miny v podbarvených oblastech rozmisťovat tak šikovně, abychom správně uspokojili i všechna čísla barevně neoznačená. (Markantní je to například u pětky vpravo dole.)

A tak dále.

Finální řešení, viz obrázek:

- 9. 1. 2014 - sepsal Krtek -