====== Japonský rébus - nonogram ======
  * Externí zdroj: http://www.puzzle-nonograms.com/
  * Data: {{:courses:a0m33eoa:semestralni_ulohy:nonogramy:nonogramy_data_3.zip|}}

Kdybychom měli k úloze přistupovat jako k černé skříňce, neměli byste zadání rébusu využívat nikde jinde než v ohodnocovací funkci. V této úloze ale **je povoleno využívat či analyzovat konkrétní zadání** i jinde, např. v rekombinačních operátorech. 

===== Popis problému =====
Nonogram se skládá se ze tří částí:
  * Mřížka obdélníkového tvaru MxN, do které se má vyplnit obrázek z plných a prázdných políček.
  * Dvě legendy (levá a horní). Každému řádku obrázku odpovídá řádek levé legendy, sloupci obrázku odpovídá sloupec horní legendy.

{{:courses:a0m33eoa:semestralni_ulohy:nonogramy:nono-small.png?350}}

V řádcích/sloupcích legend jsou uvedeny seznamy celých čísel. Každé číslo odpovídá souvislému bloku plných políček dané délky. Pořadí čísel v legendě určuje pořadí bloků v obrázku.

Mezi dvěma sousedními bloky v obrázku musí být alespoň jedno prázdné políčko. Na začátku a na konci každého řádku a sloupce se může, ale nemusí, vyskytovat libovolný počet prázdných políček.

Cílem je vyplnit mřížku plnými políčky tak, aby výsledný obrázek přesně odpovídal všem řádkům a sloupcům legendy.

===== Možné reprezentace =====
  * Binární vektor nebo binární matice <latex>\{0,1\}^{M\cdot N}</latex>.
  * Sloupcové nebo řádkové bloky.
  * ...

===== Jednotná ohodnocovací funkce =====
Považujme řádkové a sloupcové komponenty legendy za řetězce celých čísel. Stejně tak reprezentace aktuálního stavu řádku a sloupce považujme za řetězce celých čísel. Potom míru shody mezi legendou a daným stavem na řádku/sloupci spočítáme jako podobnost dvou řetězců podle Needleman-Wunchova algoritmu (viz níže). 

Hodnota shody legendy a konkrétního řádku/sloupce matice je součtem rozdílů hodnot přes všechny dvojice čísel na souhlasných pozicích a penalizací za vložené mezery.

Celková kvalita řešení se počítá jako součet příspěvků spočítaných přes všechny řádky a sloupce matice.

==== Needleman-Wunschův algoritmus ====
  * Wikipedia EN: [[http://en.wikipedia.org/wiki/Needleman%E2%80%93Wunsch_algorithm|Needleman-Wunsch Algorithm]]
  * Wikipedia CZ: [[http://cs.wikipedia.org/wiki/Algoritmus_Needleman-Wunsch|Algoritmus Needleman-Wunsch]]

**Příklad výpočtu** 

(Ne)shoda legendy (řetězec X)
  1 7 3 4 2
a řádku matice (řetězec Y)	
  8 2 2

Výpočet spočívá ve vyplnění tabulky shody H, viz obrázek, kde sloupce reprezentují znaky řetězce X a řádky odpovídají znakům řetězce Y. Začíná se z levého horního políčka, které má hodnotu 0, a pokračuje se po sloupcích zleva doprava a ve sloupci shora dolů. Hodnota v pravém dolním políčku udává výslednou hodnotu neshody řetězců X a Y.

{{:courses:a0m33eoa:semestralni_ulohy:nonogramy:nw.png|}}

**Parametry** Needleman-Wunchova algoritmu jsou:
  * penalizace za mezeru: -K, kde K je hodnota znaku, který je na stejné pozici s mezerou. Konkrétně, pokud uvažujeme přechod H(i-1, j) -> H(i, j), tedy přechod dolů, tak za tuto vloženou mezeru je penalta rovna záporné hodnotě znaku na řádku 'i'. Pokud uvažujeme přechod H(i, j-1) -> H(i, j), tedy přechod doprava, tak za takto vloženou mezeru je penalizace rovna záporné hodnotě znaku ve sloupci 'j'. 
  * Ohodnocení (ne)shody stejnolehlých znaků: -|Xj - Yi|, kde Xj a Yi jsou čísla na stejnolehlých pozicích.

**Postup:** 

Vyplň tabulku tak, že hodnota každého políčka se získá podle následujícího pravidla:

  H(i, j) = max(H(i-1, j)-Ki, H(i, j-1)-Kj, H(i-1, j-1)+Neshoda(i, j)),

kde Ki resp. Kj je hodnota i-tého znaku řetězce Y resp. Hodnota j-tého znaku řetězce X. Neshoda(i,j) = -(|Xj - Yi|). Výsledná hodnota je -7. Tomu odpovídá několik řešení, například

  legenda (řetězec X):        1 7 3 4 2
  řádku matice (řetězec Y):   - 8 - 2 2

nebo

  legenda (řetězec X):        1 7 3 4 2
  řádku matice (řetězec Y):   - 8 2 2 -