Search
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 číst ze standardního vstupu, vstup 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
_
Stáhněte si připravený balíček, kde je pro vás připravena struktura programu, kterou budete doplňovat. Jako první se volá CSPMain.main(), ve kterém se načte vstup pomocí InputLoader.loader(), kde zároveň definujete jak váš CSP problém vypadá, pomocí třídy Problem. Nakonec se instance problem předá do Solver.solve(), která inicializuje algoritmus, zavolá AC3 (pokud se rozhodnete ji implementovat) a nakonec spustí funkci backtrack(). Poté vrátíte výsledek a vypíšete ve funkci main(). Všechny třídy a metody budete muset nejdříve doplnit. Struktura není striktně rigidní, můžete měnit definice tříd, pokud máte dobrý důvod. Nutné je pouze zachovat CSPMain.main() jako hlavní metodu programu.
CSPMain.main()
InputLoader.loader()
Problem
problem
Solver.solve()
backtrack()
main()
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 algoritmem backtracking a do něj můžete implementovat AC3, nebo Most-Constrained-Variable heuristiku.
Ke komentáři třídy CSPMain prosím vložte krátký popis vaší formalizace – jaké jste zvolili proměnné, domény a jaké jsou zde omezení.
CSPMain
Vaše implementace bude automaticky vyhodnocena na 6 problémech, s celkovým časovým limitem 15 minut.
Za úkol můžete získat maximálně 12 bodů:
Nehodnotí se rychlost řešení.
student
main
31/03/2019 23:59