====== Task 2 - CS - Malované křížovky  ======

===== Zadání =====

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ů.

===== Pokyny k vypracování =====

==== Vstup ====

Program by měl číst ze standardního vstupu, vstup má následující formát:
<file>
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
</file>

přičemž každá podmínka má tvar 
<file>
COLOR_1,NUMBER_1,COLOR_2,NUMBER_2,...,NUMBER_K
</file>

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: {{courses:b4b36zui:csp_example.txt|}}, {{courses:b4b36zui:input.txt|}}, {{courses:b4b36zui:krtkek.txt|}}, {{:courses:b4b36zui:dino.txt|}}

Příklady výstupu: {{courses:b4b36zui:csp_example.txt.out.txt|csp_example.txt.out}} {{courses:b4b36zui:input.txt.out.txt|input.txt.out}} {{courses:b4b36zui:krtek.txt.out.txt|krtek.txt.out}}, {{:courses:b4b36zui:dino.out.txt|}}


==== Výstup ====

  * 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".
==== Postup ====

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.

Vaše implementace bude automaticky vyhodnocena na 6 problémech, s celkovým časovým limitem 15 minut.
==== Ohodnocení ====

Za úkol můžete získat maximálně 14 bodů:

   * 4 body za správnou implementaci (vyhodnoceno automaticky)
   * 4 body za správnou CSP implementaci
   * 3 body za správnou AC3 implementaci
   * 2 body za implementované pokročilé heuristiky (Forward checking, MCV, LCV)
   * 1 bod za dokumentaci popisující jak jste formalizovali CSP (proměnné, domény, omezující podmínky) a stručně shrnující vaši implementaci. Stačí napsat do komentářů u hlavní třídy.

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

  * Vaše třídy vytvořte v package "student"
  * Ve této 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

===== Termín odevzdání =====
Týden 5 - 08/04/2018 23:59