Nonogram: Complexity of Inference and Phase Transition Behavior

Aaron Foote; Danny Krizanc

REVIEW 2 major objections 4 minor 16 references

Nonogram: Complexity of Inference and Phase Transition Behavior

T0 review · 2 major / 4 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper claims that detecting a forced cell in a consistent Nonogram is co-NP-complete and that random boards undergo a phase transition at roughly 0.39–0.42 filled-cell density.

desk verdict co-NP-completeness is a genuine new result, but the phase-transition experiments measure only forced-filled cells, not the INFERENCE problem the paper defines. read the letter →

arxiv 2507.07283 v2 pith:GD62J3XP submitted 2025-07-09 cs.CC

Aaron Foote , Danny Krizanc This is my paper · ORCID

classification cs.CC MSC 68Q1768Q1568Q25

keywords Nonograminferenceproblemco-NP-completenessphasetransitionSATencodingregularexpressionsfilled-celldensityconsistentboard

topics P versus NP

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper tries to reconcile the fact that Nonogram is NP-complete to solve yet humans enjoy it by studying inference: whether some cell is forced in every solution of a consistent board. It claims this inference problem is co-NP-complete, meaning it is as hard as proving a Boolean formula unsatisfiable. It also reports an empirical phase transition: for random consistent boards, the proportion of filled cells that are inferable jumps from near zero to near one as filled-cell density crosses roughly 0.39 to 0.42, with SAT solving effort peaking at the transition. If correct, worst-case hardness and practical playability are compatible because typical boards sit far from the difficult threshold.

What carries the argument

The machinery has two linked pieces. The first is a library of eleven-by-eleven Nonogram gadgets for NOT, AND, OR, wire, splitter, crossover, and terminals, which simulate Boolean circuits; the reduction depends on the property that no gadget's cells can be derived from its own descriptions alone. The second is a line encoding: a description $(l_1,\ldots,l_t)$ becomes the regular expression $0^*1^{l_1}0^+1^{l_2}0^+\cdots 1^{l_t}0^*$, which is converted through a DFA into a CNF formula, with the whole board encoded as the conjunction of row and column formulas. The inference test for cell $(i,j)$ checks satisfiability of the board formula together with the assumption that the cell is empty (or filled).

What would settle it

Run the reduction on a satisfiable formula such as $\psi = (x \vee y) \wedge x^*$ and enumerate all solutions of the resulting Nonogram board; if any cell in a gadget other than the output terminal is filled in every solution, gadget property 4 fails and the only-if half of Theorem 1 is unsupported. For the phase transition, measure the inferable-cell fraction on 40x40 boards at densities 0.38, 0.39, 0.40, 0.41, and 0.42: if the curve does not sharpen toward a single threshold as board size grows, the empirical phase transition is not established.

Watch

Extended reading notes

Core claim

The central claim is that INFERENCE for Nonogram is co-NP-complete. A negative instance is certified by giving, for every cell, two consistent fillings of the board with opposite values in that cell. Co-NP-hardness is shown by reducing Boolean unsatisfiability: a fresh variable is added to the input formula, a Boolean circuit is built, and the circuit is translated into Nonogram gadgets so that the board has an inferable cell exactly when the circuit is unsatisfiable. Empirically, the paper finds that the average fraction of filled cells whose value is logically forced rises from almost zero to almost one when filled-cell density passes roughly 0.39 to 0.42, and that average solver propagation counts peak in the same region.

Load-bearing premise

The only-if direction of the co-NP-hardness proof depends on the unproved assertion that no gadget's cells are forced by that gadget's own constraints alone, which the paper defers to the first author's thesis; if any gadget cell were internally forced, a satisfiable formula could still produce an inferable cell.

Editorial extensions

If this is right

Solving INFERENCE on all consistent boards is at least as hard as proving unsatisfiability, so unless P = NP no polynomial-time algorithm can always find a safe move.
The empirical curve gives puzzle designers a tuning knob: boards below roughly 0.39 filled-cell density will rarely offer a forced step, while boards above roughly 0.42 will often have nearly every filled cell forced.
The peak in solver effort at the transition, rather than at the largest formulas, indicates that practical difficulty is a property of the inference decision and not just of formula size.
The regular-expression-to-CNF encoding is polynomial in board size, with $O(n^2)$ variables and clauses per line, which is what makes the inference experiments feasible at the board sizes tested.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The authors do not say this, but the location of the threshold suggests a counting argument: below roughly 0.4 density the number of solutions may grow so quickly that no cell is pinned, while above it enough row and column constraints overlap to pin cells; deriving the critical density analytically from run-length statistics would turn the empirical curve into a theorem.
A testable extension is to generate boards from other random models, such as random run-length descriptions or random images, and check whether the same 0.39–0.42 threshold appears; if the threshold moves, the transition is a property of the generation model rather than of Nonogram constraints alone.
The inferability test itself could serve as a puzzle-difficulty metric, letting a designer certify that a generated board has at least one logical step and deliberately place puzzles near the transition when a harder challenge is intended.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Two things you should know about arXiv:2507.07283. First, the co-NP-completeness of Nonogram INFERENCE is a genuine new result, and the membership argument is clean. Second, the phase-transition section does not actually measure the problem the paper defines. The experiments only count cells forced to be filled; they never test for cells forced to be empty. Since INFERENCE includes both, the plotted curve says nothing about the probability that a random consistent board has an inferable cell. At density 0.03 on a 15x15 board, a row is empty with probability 0.63, and each empty row forces every cell in it empty, so almost every such board is an INFERENCE instance. The paper's claim that boards below the threshold "almost surely do not have an inferable cell" is false for the stated problem.

The hardness proof is plausible but has a gap. Case 2 shows the output terminal is not forced when the formula is satisfiable, but co-NP-hardness requires no cell anywhere to be forced. That step rests on gadget property 4 in Section 2, which is asserted and deferred to the first author's thesis [4]. If that property holds, the proof works; as written it is incomplete. The same thesis supplies the gadget correctness, the CNF encoding details, and the formula-size recurrences. That is a heavy self-citation burden, though not disqualifying.

The encoding from row descriptions to automata to CNF is described well enough that someone could reimplement it, and the formula-size analysis is honest about the trade-off between runs and clauses. No code ships, the SAT solver is unnamed, the threshold is estimated by eye, and there are no error bars. Those are minor compared to the metric mismatch.

If the experimental half is meant to study INFERENCE, it needs to test both x_ij and not x_ij, or explicitly redefine the problem as forced-filled inference and adjust the claims. The complexity result is worth a serious referee independent of that.

My recommendation: send it to peer review, but expect a major revision. The gap in Theorem 1 should be closed by importing the relevant thesis lemma, and the phase-transition section should either measure the defined problem or be relabeled. The paper is for anyone interested in puzzle complexity or average-case behavior, and the core complexity claim is likely correct.

Referee Report

2 major / 4 minor

Summary. The paper studies INFERENCE for Nonogram: given a consistent board, decide whether some cell has the same value in every solution. It claims this problem is co-NP-complete (Theorem 1). Membership is argued via polynomial-time checkable certificates that exhibit, for every cell, two solutions differing at that cell. Hardness is attempted by a reduction from Boolean unsatisfiability through circuit gadgets (AND, OR, NOT, wires, crossovers, splitters, input/output terminals), with detailed gadget correctness deferred to the first author's thesis [4]. The paper then reports an empirical phase transition: for random consistent boards generated at filled-cell density rho, the average proportion of filled cells inferred rises sharply around rho in [0.39, 0.42], and SAT-solver propagation effort peaks at the same location. A CNF encoding based on regular expressions is used for the experiments.

Significance. If the hardness proof is completed, the co-NP-completeness classification is a meaningful complement to the known NP-completeness of Nonogram consistency, since inference is a natural formalization of making progress in a puzzle without guessing. The reported threshold phenomenon, if measured against the formal problem, would also be practically relevant for puzzle generation. The paper's certificate for membership in co-NP is simple and correct, and the experimental methodology is transparent enough to be reproduced. However, the current manuscript relies heavily on an unpublished thesis for the gadget lemmas, and the experimental metric does not match the formal definition of INFERENCE, so the central claims are not yet fully established as written.

major comments (2)

[Section 2, proof of Theorem 1] The only-if direction of the co-NP-hardness proof is incomplete. In the case where C_psi is satisfiable, the proof shows only that the output terminal is not forced, by exhibiting two assignments that give different values at the output. It does not rule out the possibility that some other cell in the board, perhaps inside a gadget, is forced in every solution. The conclusion that the whole board has no inferable cell requires a formal lemma, but the only support given is the unproved gadget property 4, which is asserted without proof and deferred to the first author's thesis [4]. Since the INFERENCE question asks whether any cell is forced, this is load-bearing: a forced cell anywhere in a gadget would invalidate the reduction. Please provide a direct proof, or at least a precise statement of the gadget property and a proof that it implies no cell in the entire construction is forced.
[Section 3, algorithm Step 5 and Figure 5] The experimental metric does not measure the formal INFERENCE problem defined in Section 2. The algorithm tests only whether phi and not x_ij is unsatisfiable, which detects cells forced to be filled; it never tests phi and x_ij, so cells forced to be empty are never counted. Under the formal definition such cells are inferable. At low densities this is not a negligible effect: for N=15 and rho=0.03, a row is empty with probability (1-rho)^N ≈ 0.63, and an empty row description forces every cell in that row to be empty in every solution, making the board an INFERENCE instance. Therefore the claim that boards below the threshold 'almost surely do not have an inferable cell' is false for the stated problem. The transition shown in Figure 5 is a property of forced-filled cells only. The authors should either count forced-empty cells as well (testing phi and x_ij), or explicitly redefine the experiment and all related claims as concerning the proportion of filled cells that are forced to be filled.

minor comments (4)

[Section 2, problem definition] The INFERENCE instance as stated includes 'a mapping of cells to values f', but f is also used for solutions and never appears as an input; the value v in the question is undefined. This should be cleaned up, for example by defining INFERENCE as the existence of a cell c and a bit b such that every solution f satisfies f(c)=b.
[Section 3, text near Figure 5] The prose alternates between 'inferable cell', 'proportion of filled cells inferred', and 'probability of an inferable cell'; these are different quantities. The text should state once, precisely, what is plotted and what the claimed threshold applies to.
[Section 2, proof of co-NP membership] The certificate description says 'There are 2mn boards to check'; it would be clearer to say that the certificate contains 2mn filled boards (two per cell), and checking each board takes O(mn) time when row and column descriptions are verified. The current wording is not wrong but is easy to misread.
[Section 3, CNF encoding paragraph] There is a typo: 'automoton' should be 'automaton'. There is also a redundant phrase 'appears to peak peaks' in the paragraph about propagation counts.

Circularity Check

2 steps flagged · score 5.0 of 10

Theorem 1 leans on an unproved gadget property in the first author's thesis, and the phase-transition experiment counts only forced-filled cells while INFERENCE also includes forced-empty ones.

self citation load bearing [Section 2, gadget property list (before Fig. 3) and proof of Theorem 1]
"More details for the gadgets, including their solutions, can be found in [4]. All gadgets have the following properties: ... 4. It is impossible to derive the contents of any gadget without information from other gadgets (with the exception of input terminals)."

The co-NP-hardness proof's second case ('Suppose Cψ is satisfiable ... the Nonogram construction is not in INFERENCE') requires that no cell anywhere in the constructed board is forced, not merely that the output terminal is unfixed. The only stated support for this global non-forcing claim is gadget property 4, which is asserted without proof in this paper and deferred to the first author's own thesis [4]. The theorem's central only-if direction is therefore load-bearing on an unverified self-citation rather than on a proof contained in the paper. This is not definitional circularity, but it makes the main complexity claim uncheckable from the manuscript alone.
other [Section 3, algorithm steps 4-5 and Fig. 5 description]
"Set accumulator inferredFilled=0 ... 5. For the Boolean variable xij associated with each cell cij: (a) Test ψ= ¯xij ∧ ϕ for satisfiability (b) If ψ satisfiable do nothing (c) Otherwise increment inferredFilled by one ... For each density, the average proportion of filled cells inferred is plotted in black."

Formal INFERENCE, as defined in Section 2, asks whether some cell has the same value in every solution, which includes cells forced to be empty. The experimental loop only tests ¯xij ∧ ϕ; unsatisfiability of that formula means xij is forced true, so only forced-filled cells are counted. No test of ϕ ∧ xij is performed to detect forced-empty cells. The plotted quantity is therefore, by construction, the proportion of filled cells that are forced, not the probability that the board is an INFERENCE instance. Even at low density this matters: for ρ=0.03 and N=15, an all-empty row occurs with probability (1−ρ)^15 ≈ 0.63, and its empty description forces every cell in that row to be empty in every solution, making the board an INFERENCE instance while contributing zero to inferredFilled.

full rationale

The formal co-NP-completeness proof is a standard reduction, but its only-if direction relies on an asserted gadget property deferred to the first author's own thesis [4]; because that property is load-bearing and not independently verified in the paper, the theorem is not self-contained. Separately, the empirical phase-transition claim is not about the INFERENCE predicate defined in Section 2: the SAT loop counts only cells forced to true, so boards whose only forced cells are forced empty are invisible to the plot. At low densities such boards dominate because empty rows are very likely, so the claimed threshold concerns forced-filled cells rather than INFERENCE. No step literally fits a parameter to the target quantity and then predicts it, so this is not full definitional circularity, but the combination of a load-bearing self-citation and a definitionally restricted experimental metric warrants a score of 5.

Assumptions & free parameters 1 free parameters · 5 assumptions · 0 invented entities

The central claim rests on two external loads. First, the co-NP-hardness proof depends on the correctness of the printed gadgets, especially property 4 (no gadget cell is forced without external information); the paper asserts these properties and defers verification to the first author's thesis [4]. Second, the empirical claims depend on a random Bernoulli board model and on an unnamed SAT solver being sound and complete on the generated formulas. The threshold density is an empirical observation, not a fitted parameter of a derivation. No new entities are postulated.

free parameters (1)

phase transition threshold density = 0.39 to 0.42 (estimated by inspection of Figure 5)
The reported threshold is read off the empirical curve from 250 boards per density at sizes 15, 20, 25. It is an observation, not a fitted constant of a derivation, and it is not used to derive any other result; it carries no error bars.

assumptions (5)

domain assumption The Nonogram gadgets in Figure 3 satisfy the six listed properties, in particular property 4: no cell inside any gadget can be deduced without information from other gadgets.
Used in the co-NP-hardness proof of Theorem 1 (Section 2). The reduction's only-if direction requires that when the circuit is satisfiable, no cell in the entire board is forced; this is exactly property 4, stated without proof and deferred to [4].
domain assumption A consistent puzzle has a unique solution if and only if every cell is inferable.
Invoked in Section 1 to link inference and uniqueness; labeled 'not hard to show' and cited to [4]. It is background folklore in the puzzle community, but the paper does not prove it.
domain assumption Random consistent boards are modeled by filling each cell independently with probability rho and extracting the resulting row and column descriptions.
Section 3 defines the instance distribution this way, invoking [5] on the pitfalls of random instances. The phase-transition conclusion is only about this specific distribution.
domain assumption The SAT solver used for the per-cell tests is sound and complete on the generated CNF formulas.
Section 3 decides inferability from satisfiability of psi = not x_ij and phi. The solver is never named and its configuration is not given, so the empirical correctness rests on an unstated tool assumption.
standard math Standard complexity theory: definitions of NP and co-NP, polynomial-time reductions, and the circuit construction for a formula.
Background for Theorem 1 (Section 2); no novel mathematical axioms are introduced.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Nonogram: Complexity of Inference and Phase Transition Behavior." pith.science (2026). https://pith.science/paper/GD62J3XP

@misc{pith2026250707283,
  author       = {Pith},
  title        = {Pith review of: Nonogram: Complexity of Inference and Phase Transition Behavior},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GD62J3XP}},
  note         = {Machine review of arXiv:2507.07283}
}

read the original abstract

Nonogram is a popular combinatorial puzzle (similar in nature to Sudoku or Minesweeper) in which a puzzle solver must determine if there exists a setting of the puzzle parameters that satisfy a given set of constraints. It has long been known that the problem of deciding if a solution exists is a computationally difficult problem. Despite this fact, humans still seem to enjoy playing it. This work aims to reconcile these seemingly contradictory facts by (1) analyzing the complexity of the inference problem for Nonogram (the problem of determining if there exists a puzzle parameter that can be inferred from the constraints without guessing) and (2) experimentally establishing the existence of a phase transition behavior for this inference problem. Our results show that the difficulty of the inference problem is largely determined by the density of filled cells (positive parameters) in a given puzzle. Along the way we implement an efficient encoding of a Nonogram board as a Boolean formula in Conjunctive Normal Form (CNF) through the use of regular expressions in order to make our experiments feasible.

Figures

Figures reproduced from arXiv: 2507.07283 by the authors.

**Figure 1.** An example Nonogram of a smiley face. As noted by Kaye in the context of Minesweeper [7], obtaining an NPcomplete result for consistency does not guarantee that there is not a polynomialtime approach to playing the game. Later work proposes the problem of inference – deciding the existence of a cell that can have its value deduced by logical inference – as a more natural expression of solving a combinatorial puzz… view at source ↗

**Figure 2.** Two puzzles in which inference is possible (the 2x2 square). In the first puzzle the pair of 1 clues creates multiple solutions, while the second puzzle only has one solution. sions. The formulas can be solved iteratively under different assumptions to solve the inference problem. 2 Inference is co-NP-complete The INFERENCE problem for Nonogram is defined as follows: INSTANCE: A consistent Nonogram board N = (R, C, … view at source ↗

**Figure 3.** Nonogram gadgets 3 Phase Transition Assuming P ̸= NP, the previous complexity result would suggest that Nonogram is not a puzzle that can be played efficiently. Nonetheless, it is a popular combinatorial puzzle enjoyed by millions. We explain this by showing, empirically, phase transition behavior for the INFERENCE problem. Boards with filled cell density below the transition threshold almost surely do not have an … view at source ↗

Figures from the paper (3 more)

**Figure 4.** Figure 4: Board generation process [PITH_FULL_IMAGE:figures/full_fig_p007_4.png]

**Figure 5.** Figure 5: Phase transition behavior for Nonogram INFERENCE [PITH_FULL_IMAGE:figures/full_fig_p007_5.png]

**Figure 6.** Figure 6: Formula size across densities Average clause and variable counts and computational cost appear to follow different patterns. The number of clauses and variables is greatest above a filled cell density of 0.5, the puzzles for which solving is the easiest (fewest propag…

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

16 extracted references · 15 canonical work pages

[4]

Foote, A.: On the complexity and threshold behavior of playing nonogram puz- zles (April 2024), available at https://digitalcollections.wesleyan.edu/islandora/ complexity-and-threshold-behavior-playing-nonogram-puzzles

work page 2024
[1]

In: Proceedings of the 16th Belgium-Netherlands Conference on Artificial Intelligence (BNAIC)

Batenburg, K.J., Kosters, W.A.: A discrete tomography approach to japanese puz- zles. In: Proceedings of the 16th Belgium-Netherlands Conference on Artificial Intelligence (BNAIC). pp. 243–250 (2005)

work page 2005
[2]

Bosboom, J.W.: Exhaustive search and hardness proofs for games. Ph.D. thesis, Massachusetts Institute of Technology, USA (2020)

work page 2020
[3]

In: FUN with Algo- rithms 2020 (2020)

Dempsey, R., Guinn, C.: A phase transition in minesweeper. In: FUN with Algo- rithms 2020 (2020)

work page 2020
[5]

Discrete Applied Mathematics5(1), 77–87 (1983)

Franco, J., Paull, M.: Probabilistic analysis of the davis putnam procedure for solv- ing the satisfiability problem. Discrete Applied Mathematics5(1), 77–87 (1983). https://doi.org/https://doi.org/10.1016/0166-218X(83)90017-3

work page doi:10.1016/0166-218x(83)90017-3 1983
[6]

Hearn, R.A.: Games, puzzles, and computation. Ph.D. thesis, Massachusetts Insti- tute of Technology, USA (2006)

work page 2006
[7]

The Mathematical Intelligencer22(2), 9–15 (2000)

Kaye, R.: Minesweeper is np-complete. The Mathematical Intelligencer22(2), 9–15 (2000)

work page 2000
[8]

(eds.): Colored Nonograms: An Integer Linear Programming Approach

Lopes, L.S., Lau, N., Mariano, P., Rocha, L.M. (eds.): Colored Nonograms: An Integer Linear Programming Approach. Springer Berlin Heidelberg, Berlin, Hei- delberg (2009)

work page 2009

Show all 16 references

[9]

Proceedings Tenth National Conference on Artificial Intelligence (07 1992)

Mitchell,D.,Selman,B.,Levesque,H.:Hardandeasydistributionsofsatproblems. Proceedings Tenth National Conference on Artificial Intelligence (07 1992)

1992
[10]

Master’s thesis, University of Gronigen (2017)

Oosterman, R.: Complexity and Solvability of Nonogram Puzzles. Master’s thesis, University of Gronigen (2017)

2017
[11]

In: 2018 IEEE 30th International Conference on Tools with Artificial Intelligence (ICTAI)

Prates, M., Lamb, L.: Problem solving at the edge of chaos: Entropy, puzzles and the sudoku freezing transition. In: 2018 IEEE 30th International Conference on Tools with Artificial Intelligence (ICTAI). pp. 115–116 (2018)

2018
[12]

Master’s thesis, Leiden Institute for Advanced Computer Sci- ence (2012)

van Rijn, J.N.: Playing Games: The Complexity of Klondike, Mahjong, Nonograms, and Animal Chess. Master’s thesis, Leiden Institute for Advanced Computer Sci- ence (2012)

2012
[13]

The Mathematical Intelligencer33, 5–17 (2011)

Scott, A., Stege, U., van Rooij, I.: Minesweeper may not be np-complete but is hard nonetheless. The Mathematical Intelligencer33, 5–17 (2011)

2011
[14]

Bachelor’s thesis, University of Nebraska, Lincoln, Nebraska (October 2019), available at https://consystlab.unl.edu/Documents/Theses/ Hung-UG-thesis.pdf

Tran, T.H.: Modeling and Solving the Nonogram Puzzle Using Constraint Programming. Bachelor’s thesis, University of Nebraska, Lincoln, Nebraska (October 2019), available at https://consystlab.unl.edu/Documents/Theses/ Hung-UG-thesis.pdf

2019
[15]

Journal of Algo- rithms9(1), 63–82 (1988)

Turner, J.S.: Almost all k-colorable graphs are easy to color. Journal of Algo- rithms9(1), 63–82 (1988). https://doi.org/https://doi.org/10.1016/0196-6774(88) 90005-3, https://www.sciencedirect.com/science/article/pii/0196677488900053

1988
[16]

Ueda, N., Nagao, T.: Np-completeness results for nonogram via parsimonious re- ductions. Tech. rep., Tokyo Institute of Technology (05 1996)

1996

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.

[1] [4]

Foote, A.: On the complexity and threshold behavior of playing nonogram puz- zles (April 2024), available at https://digitalcollections.wesleyan.edu/islandora/ complexity-and-threshold-behavior-playing-nonogram-puzzles

work page 2024

[2] [1]

In: Proceedings of the 16th Belgium-Netherlands Conference on Artificial Intelligence (BNAIC)

Batenburg, K.J., Kosters, W.A.: A discrete tomography approach to japanese puz- zles. In: Proceedings of the 16th Belgium-Netherlands Conference on Artificial Intelligence (BNAIC). pp. 243–250 (2005)

work page 2005

[3] [2]

Bosboom, J.W.: Exhaustive search and hardness proofs for games. Ph.D. thesis, Massachusetts Institute of Technology, USA (2020)

work page 2020

[4] [3]

In: FUN with Algo- rithms 2020 (2020)

Dempsey, R., Guinn, C.: A phase transition in minesweeper. In: FUN with Algo- rithms 2020 (2020)

work page 2020

[5] [5]

Discrete Applied Mathematics5(1), 77–87 (1983)

Franco, J., Paull, M.: Probabilistic analysis of the davis putnam procedure for solv- ing the satisfiability problem. Discrete Applied Mathematics5(1), 77–87 (1983). https://doi.org/https://doi.org/10.1016/0166-218X(83)90017-3

work page doi:10.1016/0166-218x(83)90017-3 1983

[6] [6]

Hearn, R.A.: Games, puzzles, and computation. Ph.D. thesis, Massachusetts Insti- tute of Technology, USA (2006)

work page 2006

[7] [7]

The Mathematical Intelligencer22(2), 9–15 (2000)

Kaye, R.: Minesweeper is np-complete. The Mathematical Intelligencer22(2), 9–15 (2000)

work page 2000

[8] [8]

(eds.): Colored Nonograms: An Integer Linear Programming Approach

Lopes, L.S., Lau, N., Mariano, P., Rocha, L.M. (eds.): Colored Nonograms: An Integer Linear Programming Approach. Springer Berlin Heidelberg, Berlin, Hei- delberg (2009)

work page 2009