Nonogram: Complexity of Inference and Phase Transition Behavior

Aaron Foote, Danny Krizanc

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 t…