Malované křížovky

Vaším úkolem je napsat algoritmus, který vyřeší malovanou křížovku. Malované křížovky jsou logické hlavolamy, při kterých je kolem mřížky umístněná legenda s čísly pomocí nichž lze vytvořit obrázek. Každé číslo v legendě určuje počet za sebou následujících vyplněných čtverečků barvy, která přísluší danému číslu. Platí následující pravidla: (1) mezi jednotlivými bloky čtverečků vyplněných stejnou barvou je vždy minimálně jeden prázdný, (2) mezi čtverečky, které jsou vyplněny různou barvou nemusí být prázdný čtvereček, (3) pořadí čísel v legendě určuje pořadí bloků.

Program by měl načíst soubor ze standardního vstupu, a který má následující formát:

NUMBER_OF_ROWS,NUMBER_OF_COLUMNS
CONSTRAINTS_FOR_ROW_1
CONSTRAINTS_FOR_ROW_2
...
CONSTRAINTS_FOR_ROW_M
CONSTRAINTS_FOR_COLUMN_1
CONSTRAINTS_FOR_COLUMN_2
...
CONSTRAINTS_FOR_COLUMN_N

přičemž každá podmínka má tvar

COLOR_1,NUMBER_1,COLOR_2,NUMBER_2,...,NUMBER_K

kde položka “color” se vztahuje k následujícímu číslu a má formát znaku, který reprezentuje barvu, kterou při vykřeslování použijete (např. #). Položky “number” označují velikost daného bloku.

Příklady vstupu: csp_example.txt, input.txt, krtkek.txt, dino.txt

Příklady výstupu: csp_example.txt.out input.txt.out krtek.txt.out, dino.out.txt

• Obrázek vypište na standardní výstup.
• Obrázek vykreslujte po řádcích - pro plné políčko vypište znak příslušné barvy, pro prázdné políčko vypište _.
• Pokud je výsledných obrázků více, oddělte je prázdnou řádkou.
• Pokud řešení neexistuje, vypište “null”.

Promyslete si zejména způsob formalizace – co zvolit jako proměnnou, jak budou vypadat podmínky a zda půjde jednoduše implementovat algoritmy hranové konzistence. Začněte s jednoduchým prohledáváním do hloubky a ten vylepšujte pomocí CSP technik.

Do hlavní třídy/souboru do komentáru napište jakou formalizaci jste zvolili, jakým způsobem reprezentujete podmínky a které z CSP algoritmů/technik jste implementovali.

Za úkol můžete získat maximálně 14 bodů - plné bodové ohodnocení získáte, pokud problém vyřešíte (tj. najdete všechna řešení problému) pomocí technik CSP v kombinaci prohledávání a použití algoritmů hranové konzistence (AC-3). V případě nesplnění některých částí bude bodové hodnocení sníženo.

Je důležitější mít správnou formulaci/implementaci CSP a AC-3, než vyřešit co možná nejrychlej dané křížovky.

• Vaše třídy vytvořte v package “student”
• Ve Vašem package vytvořte hlavní třídu CSPMain, která bude implementovat metodu main
• Váš algoritmus musí vypsat všechna řešení
• Odevzdejte zabalenou balíčkovou strukturu se všemi Vašimi třídami

10.4.2015 3:59