Malované křížovky

• Název práce v češtině: Malované křížovky
• Název v anglickém jazyce: Griddlers
• Akademický rok vypsání: 2005/2006
• Typ práce: bakalářská práce
• Ústav: Ústav formální a aplikované lingvistiky (32-UFAL)
• Vedoucí / školitel: doc. RNDr. Vladislav Kuboň, Ph.D.
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 08.11.2005
• Datum zadání: 08.11.2005

Zásady pro vypracování

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.

Seznam odborné literatury

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.

Předběžná náplň práce

Práce navazuje na ročníkový projekt.