Hra minolovka - výpočetní složitost a implementace hledání řešení

• Thesis title in Czech: Hra minolovka - výpočetní složitost a implementace; hledání řešení
• Thesis title in English: Minesweeper game - computational complexity and solver implemetation
• Academic year of topic announcement: 2006/2007
• Thesis type: Bachelor's thesis
• Thesis language: čeština
• Department: Department of Applied Mathematics (32-KAM)
• Supervisor: doc. RNDr. Jiří Fiala, Ph.D.
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 05.10.2006
• Date of assignment: 05.10.2006
• Date and time of defence: 25.06.2007 00:00
• Date of electronic submission: 25.06.2007
• Date of proceeded defence: 25.06.2007
• Opponents: RNDr. Ondřej Pangrác, Ph.D.

Guidelines

Cílem práce je klasifikovat konfigurace hry minolovka a to podle výpočetní složitosti problému určení rozmístění min. Je známo, že tento problém je v obecnosti NP-úplný, a proto by primárním cílem bylo navrhnout některé podmínky za nichž by se stal řešitelný v polynomiálním čase.
Očekává se i implementace navržených algoritmů.

References

Kaye R, Minesweeper is NP-complete, Math. Intell. 22 (2) 9--15 (2000)

M. R. Garey and D. S. Johnson. Computers and Intractability. Freeman,
1979.

L. Kučera, Kombinatorické algoritmy, SNTL 1983, 1991.

časopisecká literatura dle doporučení vedoucího

Preliminary scope of work

Práce se zabývá konfiguracemi hry minolovka a to podle výpočetní složitosti problému určení rozmístění min.

Preliminary scope of work in English

The thesis explores positions of the minesweeper game according to computational complexity of the mine location problem.