Malované křížovky
Thesis title in Czech: | Malované křížovky |
---|---|
Thesis title in English: | Griddlers |
Academic year of topic announcement: | 2005/2006 |
Thesis type: | Bachelor's thesis |
Thesis language: | |
Department: | Institute of Formal and Applied Linguistics (32-UFAL) |
Supervisor: | doc. RNDr. Vladislav Kuboň, Ph.D. |
Author: | hidden - assigned and confirmed by the Study Dept. |
Date of registration: | 08.11.2005 |
Date of assignment: | 08.11.2005 |
Guidelines |
Cílem práce bude vytvořit program, který efektivně zvládne řešit různé varianty malovaných křížovek. Pod pojmem Malované křížovky se rozumí hlavolam, jehož cílem je pomocí zadaných čísel nakreslit na čtvercové síti výsledný obrázek. Čísla udávají (pro každý sloupec i řádek zvlášť) počet za sebou následujících vybarvených políček. Součástí řešení bude vytvoření rozumné skupiny pravidel, která by omezila nutnost použití backtrackingu na minimum, čímž se zmenší doba hledání řešení.
Výsledný program se bude skládat ze dvou částí, a sice z řešitelského prostředí umožňující řešení uživatelem i počítačem, a z editoru na vytváření nových křížovek. Program by měl pracovat s černobílými i barevnými křížovkami a umožňovat práci s trojúhelníkovými políčky pro obě barevné varianty. Kromě klasické čtvercové sítě by měl zvládat i trojúhelníkovou. |
References |
Robert Bosch: Solving Paint-by-Numbers Puzzles with Integer Programming, viz
http://www.oberlin.edu/math/faculty/bosch/pbn-page.html Wouter Wiggers: A comparison of a genetic algorithm and a depth first search algorithm applied to Japanese nonograms, University of Twente, 2004. Hans Eendebak and Jan Lam. Japanse Puzzles. Mat Heffels, 2004. |
Preliminary scope of work |
Práce navazuje na ročníkový projekt. |