On the estimation of the number of solutions for nonograms

Abstract

How possible is it to estimate the number of solutions of a nonogram problem? Although this thesis does not fully answer this question, it shows there is a category of nonograms where polynomial time can be achieved. The proposed algorithm for estimation partial solves a nonogram and then finds switching components from the partial solution. Switching component types are identified and the number of solutions for a type is estimated. The thesis concludes with a discussion of the feasibility of extending the algorithm by adding more types. Most likely, extending the algorithm will lead to a non-polynomial time algorithm. This could be because there is no finite amount of switching component types or detectors for a combination of types. Regardless, more types could be added to the algorithm.

Kuinka mahdollista on NP-täydellinen nonogrammin vastausten määrän estimointi? Tähän ei tämä työ täysin vastaa, mutta työ osoittaa nonogrammien kategorian, jota voidaan polynomisessa ajassa estimoida. Ehdotettu algoritmi estimointiin osittaisratkaisee nonogrammin, ja sitten etsii osittaisratkaisusta vaihto komponentit. Vaihto komponentin tyyppi tunnistetaan ja vastausten määrän estimointi tehdään tyypille. Työn lopussa pohditaan algoritmin jatkoa tyyppejä lisäämällä. Todennäköisesti, tyyppien lisääminen päättyy epäpolynomiseen algoritmiin. On mahdollista, että vaihto komponentteja ei saada luokiteltua rajattomalla tavalla tai tyyppien yhdistelmiä ei pystytä havainnoida. Joka tapauksessa tyyppejä voidaan lisätä algoritmiin.