Zakódovaný obrázek (Paint by numbers)
Zadání bylo jednoduché, dekódovat následující obrázek. Čísla udávají, kolik je v daném sloupci/řádku černých políček. Pokud je těchto skupin několik, je vypsáno více čísel pro daný sloupec/řádek.
| 3 | 4 | 1 | 1 | 5 | 2 | |
|---|---|---|---|---|---|---|
| 1 | ||||||
| 1,2 | ||||||
| 2,2 | ||||||
| 4 | ||||||
| 1,1 | ||||||
| 1,1 |
| 3 | 4 | 1 | 1 | 5 | 2 | |
|---|---|---|---|---|---|---|
| 1 | ||||||
| 1,2 | ||||||
| 2,2 | ||||||
| 4 | ||||||
| 1,1 | ||||||
| 1,1 |
Například ve druhém řádku je napsáno 1,2 což znamená, že se v tomto řádku vyskytuje jeden osamocený černý čtverec následovaný alespoň jedním bílím za kerým je dvojice černých čtverců.
Všechny možnosti druhého řádku vypadají následovně, ale pouze jedna z nich je možná v závislosti na číslech ve sloupcích.
| 1,2 | ||||||
|---|---|---|---|---|---|---|
| 1,2 | ||||||
| 1,2 | ||||||
| 1,2 | ||||||
| 1,2 | ||||||
| 1,2 |
Řešení problému
Moje semestrální práce na předmět Kybernetika a umělá inteligence. Chvíli mě trvalo, než jsem přišel na princip, jak tyto obrázky dekódovat. Nejprve jsem programem chtěl jít jako člověk, jenže to by vedlo k mnoha pravidlům, která by bylo jen stěží možné naprogramovat. Takže jsem nakonec šel jinou, poněkud strojovější silou.
- nejprve se pro každý řádek vygenerují všechny možnosti
- totéž se provede pro každý sloupec obrázku
- následně se na takto vygenerované možnosti program podívá způsobem, že každe políčko je bílé/černé, kde jsou pod sebou jen černá, nebo jen bílá políčka, je toto políčko jistojistě černé/bíle
- nejprve se tímto způsobem projdou řádky
- podle takto vytvořené černo-šedo-bílé masky se vyfiltrují možností, ze sloupců, které ji neodpovídají
- ze sloupců se vygeneruje nová maska
- maskou se filtrují řádky
- skok na bod 3 pokud je ještě nějaké políčko šedivé, respektive pokud se maska od předchozí masky změnila.
- pokud je v masce ještě nějaké šedé políčko nastane řešení hrubou silou, které je prudce neoptimalizované a nemělo by k němu vůbec dojít.
- když žádné šedé políčko není, je výsledná mska dekódovaný obrázek
- pokud se v nějakém řádku či sloupci vyfiltrovaly všechny možnosti – zadání nemá řešení
Zadání, které jsem měl vyřešit, ale program samozřejmě řeší i složitější úlohy.
