Original title:
Hra minolovka - výpočetní složitost a implementace hledání řešení
Translated title:
Minesweeper game - computational complexity and solver implemetation
Authors:
Hoder, Kryštof ; Fiala, Jiří (advisor) ; Pangrác, Ondřej (referee) Document type: Bachelor's theses
Year:
2007
Language:
cze Abstract:
[cze][eng] V předložené práci studujeme vytváření stromových rozkladů grafu se speciálním zřetelem na grafy užitečné při hraní hry Minolovka. Zároveň formalizujeme postup hry a zavádíme potřebnou terminologii. Na základě tohoto jsme našli širokou množinu konfigurací hry, o jejichž konzistentnosti lze rozhodovat v polynomiálním čase - že problém je v obecnosti NP-úplný bylo ukázáno již dříve v jiných pracech. Taktéž popisujeme algoritmy, které klasifikují konfigurace a případně v polynomiálním čase rozhodnou o jejich konzistentnosti.In the present work we study construction of tree decompositions with respect to graphs useful for playing the Minesweeper game. We also formalize rules of the game and present necessary terminology. We provide the set of game configurations whose consistency can be decided in polynomial time - problem of consistency-deciding of general game configuration has been proven NP-compete in other works. We also provide algorithms that classify game configurations and decide about consistency of those configurations, which we can decide about in polynomial time.
Institution: Charles University Faculties (theses)
(web)
Document availability information: Available in the Charles University Digital Repository. Original record: http://hdl.handle.net/20.500.11956/10921