Editing Nonogram (section)

==Nonograms in computing==
Solving nonogram puzzles is an [[NP-complete]] problem.<ref>{{Citation|first1=Nobuhisa|last1=Ueda|first2=Tadaaki|last2=Nagao|title=NP-completeness results for NONOGRAM via Parsimonious Reductions|year=1996|place=Technical Report, Department of Computer Science, Tokyo Institute of Technology|volume=TR96-0008|citeseerx = 10.1.1.57.5277}}</ref><ref>{{citation|title=Playing Games: The complexity of Klondike, Mahjong, Nonograms and Animal Chess|series=master's thesis|publisher=Leiden Institute of Advanced Computer Science, Leiden University|first=Jan N.|last=van Rijn|year=2012|url=http://www.liacs.nl/assets/2012-01JanvanRijn.pdf|access-date=2012-06-29}}.</ref><ref>{{cite journal |first1=Hendrik Jan|last1=Hoogeboom|first2=Walter|last2=Kosters|first3=Jan N.|last3=van Rijn|first4=Jonathan K.|last4=Vis|title=Acyclic Constraint Logic and Games|year=2014|journal=[[ICGA Journal]]|volume=37|issue=1|pages=3–16|doi=10.3233/ICG-2014-37102|arxiv=1604.05487|s2cid=3120304|access-date=2019-02-24|url=https://content.iospress.com/articles/icga-journal/icg37102}}</ref>  This means that there is no [[polynomial time]] [[algorithm]] that solves all nonogram puzzles unless [[P = NP]].

However, certain classes of puzzles, such as those in which each row or column has only one block of cells and all cells are connected, may be solved in polynomial time by transforming the problem into an instance of [[2-satisfiability]].<ref>{{citation|first1=Sara|last1=Brunetti|first2=Alain|last2=Daurat|title=An algorithm reconstructing convex lattice sets|journal=Theoretical Computer Science|volume=304|issue=1–3|pages=35–57|year=2003|doi=10.1016/S0304-3975(03)00050-1|s2cid=2803842 |url=https://hal.archives-ouvertes.fr/hal-00023033/file/tomoqconv_els.pdf}}; {{citation|first1=Marek|last1=Chrobak|first2=Christoph|last2=Dürr|title=Reconstructing hv-convex polyominoes from orthogonal projections|journal=Information Processing Letters|volume=69|issue=6|year=1999|pages=283–289|doi=10.1016/S0020-0190(99)00025-3|arxiv=cs/9906021|bibcode=1999cs........6021D|s2cid=6799509}}; {{citation|first1=Attila|last1=Kuba|first2=Emese|last2=Balogh|title=Reconstruction of convex 2D discrete sets in polynomial time|journal=Theoretical Computer Science|volume=283|issue=1|year=2002|pages=223–242|doi=10.1016/S0304-3975(01)00080-9|doi-access=free}}.</ref>