Star battle (Hvězdy)

Text zadání:

Zakreslete do některých políček rastru jednu hvězdu tak, aby se ve všech řádcích, sloupcí a vyznačených podoblastech vyskytoval (zadaný) stejný počet hvězd. Hvězdy se navíc nedotýkají, ani rohem.

Příklad zadání a řešení:

(1 hvězda)

Ukázka postupu řešení:

(2 hvězdy)

V první řadě se zaměříme na menší podoblasti. Musí v nich být, tak jako v každé podoblasti, po dvou hvězdách, které se navíc vzájemně nedotýkají. Umístění hvězdy do kteréhokoliv ze šedě podbarvených polí by zablokovalo některou z menších podoblastí; nebyli bychom pak schopni v nich umístit dvě hvězdy. Proto tato pole zůstanou prázdná, což si právě budeme nadále značit šedým podbarvením.

Ve dvou menších podoblastech je naprosto zjevné, že jedna hvězda musí být „nahoře“ a jedna „dole“, když se nesmí dotýkat. Naznačujeme to černými puntíky. Navíc platí, že hvězda je vždy v jednom ze dvou sousedících polí. Proto všechna pole, která sousedí s oběma z dvojice, musí zůstat prázdná (hvězda v nich by se dotýkala). Tímto způsobem vzniklo dalších 7 šedých (jistě prázdných) polí.

V dalších dvou krocích rozvineme jeden nový způsob uvažování. V posledním sloupci mřížky mají být dvě hvězdy. Zároveň se v tomto sloupci vyskytuje jedna podoblast, která zasahuje pouze do tohoto sloupce. A ta má obsahovat také právě dvě hvězdy. Z toho plyne, že jinde v posledním sloupci již hvězdy nebudou. V našem případě se jedná o jedno políčko vpravo nahoře, které zůstané prázdné (značíme šedou).

Podobnou úvahu rozvineme v klíčový krok řešené úlohy. První čtyři sloupce mřížky mají obsahovat 8 hvězd. Do těchto čtyř sloupců zároveň zasahují 4 různé podoblasti, v každé z nich můžeme umístit nejvýše 2 hvězdy. Vychází nám, že všech 8 hvězd (ze sloupců) máme rozdělit do těchto podoblastí (8 = 4 krát 2). A důsledek je ten, že části oněch čtyř podoblastí, které nezasahují do prvních čtyř sloupců, zůstanou prázdné. (Už do nich „nezbývají“ žádné hvězdy.) Proto si je označíme šedou barvou. A jako přímý důsledek se rozhodlo o umístění hvězd z naznačených dvojic v malé obdélníkové podoblasti.

Pokaždé, když doplníme hvězdu, musíme pozorně označit pole, která zůstanou prázdná. Jsou to pole přímo s hvězdou sousedící, a také zbývající pole v řádku, kde již máme obě dvě hvězdy.

Nyní si povšimneme sedmého řádku. Zbývá v něm již poslední volné pole, kam umístit druhou hvězdu. Následně pochopitelně označíme šedou pole sousedící.

Tentokrát v osmém řádku zůstává poslední volné pole pro druhou hvězdu.

Následně zůstalo poslední volné pole pro druhou hvězdu v menší podoblasti při spodním okraji.

V podoblasti tvaru L je zjevné, že jedna hvězda bude ve vodorovné a druhé ve svislé části. Opět naznačujeme černými putníky a šedou barvou značíme prázdná pole, která sousedí vždy s oběma poli z dvojice.

V pátém řádku pak zůstává poslední volné pole pro druhou hvězdu. Bez dotyku je pak také jasná druhá hvězda v šestém řádku.

Ve čtvrtém řádku mají být dvě hvězdy, pro nejvýše jednu je místo v levé části, druhá bude v šestém sloupci. (Ten již pak obsahuje hvězdy dvě, proto sekvence šedých polí.)

Zbývá poslední volné pole pro druhou hvězdy v podoblasti, do níž jsme umístili poslední předchozí.

Každý čtverec 2 krát 2 pole může z principu nedotýkání obsahovat nejvýše jednu hvězdu. Proto musí být ve dvou podoblastech při horním okraji jedna z hvězd umístěna do „ spodního nosu“.