Japonský rébus - nonogram

• Externí zdroj: http://www.puzzle-nonograms.com/
• Data: 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.

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.

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.

• Binární vektor nebo binární matice <latex>\{0,1\}^{M\cdot N}</latex>.
• Sloupcové nebo řádkové bloky.
• …

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.

• Wikipedia EN: Needleman-Wunsch Algorithm
• Wikipedia CZ: 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.

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 -