Detekcija i rešavanje nonogram puzle

[djordjeognjenovic97]

Tim Srbislav Vučenović, SW-77/2017 Đorđe Ognjenović, SW-2/2016

Asistenti Milica Škipina Dragan Vidaković

Definicija problema Rešavanje nonogram puzle na osnovu učitane slike, uz korišćenje različitih algoritama. Algoritmi koje ćemo koristiti su DFS, backtracking i genetski. Takođe, uporedićemo njihove rezultate i brzinu rešavanja. Nonogram je logička puzla sa mrežom, u kojoj je cilj da se u mreži ćelije oboje, ili ne oboje, na osnovu brojeva sa strana mreže, da bi se dobila skrivena slika. Brojevi predstavljaju koliko ima obojenih ćelija u vrsti ili koloni. Uobičajeno, nonogram puzle su crno bele boje. Za više informacija o igri, posetiti: https://en.wikipedia.org/wiki/Nonogram

Metodologija

1. Priprema slike: binarizacija, threshold, dilacija-erozija
2. Detekcija puzle i grid-a
3. Detekcija brojeva sa leve i gornje strane puzle
4. Rešavanje nonograma pomoću DFS-a, backtracking-a i genetskog algoritma.
5. Generisanje i prikaz krajnje nonogram slike
6. Poređenje rezultata korišćenih algoritama

Skup podataka Za sada koristićemo nonograme sa stranice: https://www.nonograms.org/nonograms tako što ćemo ih uslikati ili screenshot-ovati. Takođe bismo ručno napravili i neke nevalidne slučajeve.

Evaluacija Potrebno je proveriti da li je nonogram validan. Brojevi u nonogramu moraju da se uklapaju u vrstu ili kolonu u kojoj se nalaze. Nakon toga treba proveriti da li je nonogram rešiv i da li ima jedinstveno rešenje. Nonogram sa više mogućih rešenja bi bio besmislen, jer se ne bi uvek generisala željena slika.

[milica-skipina]

Tema odobrena. Ostavite link ka GitHub repozitorijumu projekta. Srećan rad.

[djordjeognjenovic97]

Repozitorijum: https://github.com/djordjeognjenovic97/Nonogram-Solver