Software

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.

  1. nejprve se pro každý řádek vygenerují všechny možnosti
  2. totéž se provede pro každý sloupec obrázku
  3. 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
  4. nejprve se tímto způsobem projdou řádky
  5. podle takto vytvořené černo-šedo-bílé masky se vyfiltrují možností, ze sloupců, které ji neodpovídají
  6. ze sloupců se vygeneruje nová maska
  7. maskou se filtrují řádky
  8. skok na bod 3 pokud je ještě nějaké políčko šedivé, respektive pokud se maska od předchozí masky změnila.
  9. 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.
  10. když žádné šedé políčko není, je výsledná mska dekódovaný obrázek
  11. 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.

Odkazy na zdroje obrázků

Download

Severovýchod Valid XHTML 1.0 Strict Valid CSS 2 Text to HTML converter and formatter Jay Bee simple CMS