Taška (puzzle) - Bag (puzzle)

Taška (také zvaný Corral nebo Jeskyně) je binární determinace logická hádanka publikováno Nikoli.

Pravidla

Bag se hraje na obdélníkové mřížce, obvykle přerušovaných čar, ve kterých se v některých buňkách objevují čísla.

Cílem je nakreslit jednu souvislou smyčku podél čar mřížky, která obsahuje všechna čísla v mřížce. Každé číslo navíc označuje součet všech buněk viditelných v jakémkoli ortogonálním směru před dosažením čáry smyčky. Například buňka 2 bude mít jednu buňku sousedící s ní, následovanou stěnou smyčky. Jinými slovy, pokud se smyčkou zacházíme jako se zdí, každé číslo označuje počet buněk, které lze vidět z buňky s číslem při pohledu kolmo, včetně samotné buňky.

Metody řešení

Nejjednodušší výchozí místo je najít „maximální buňku“; tj. číslovanou buňku, která, pokud stěny nejsou v maximální možné vzdálenosti, není počet uspokojen. Například v mřížce 10x10, která se nezačala řešit, je 19 buněk maximální buňka, protože pokud čtyři stěny nejsou na okrajích mřížky, počet viditelných buněk by nestačil. Po určitém pokroku se objeví „minimální buňky“, kde pokud stěny nejsou v minimální možné vzdálenosti, počet není uspokojen.

Mnoho metod řešení pro Bag je velmi podobných metodám používaným pro Kuromasu, protože pravidla jsou také velmi podobná. Nejpozoruhodnějším rozdílem je použití smyčky jako součásti řešení, na rozdíl od stínovaných buněk.

Výpočetní složitost

Rozhodovací otázka (Friedman, 2002): Má daná instance hry Corral Puzzle řešení?[1]

Tato rozhodovací otázka je NP-úplná. To se dokazuje snížením rozhodovacího problému rozhodování o 3barevnosti rovinného grafu, o kterém je známo, že je NP-úplný, do Corral Puzzle.

Viz také

Reference

  1. ^ Friedman, Erich. „Corral Puzzles are NP-complete“. Citováno 10. července 2016.

externí odkazy