Paper deep dive
Evaluating SAT Solver Metrics as Predictors of Human-Perceived Nonogram Difficulty
Changdao He, Yibing Ju, Jonathan Calver, Alice Gao
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Algorithmic solver effort is often assumed to align with perceived puzzle difficulty, but this assumption is rarely tested against human solving data. We evaluate this assumption for Nonograms, a popular logic puzzle similar to Sudoku in which numeric clues along each row and column determine a unique solution grid. We formulate Nonograms as a constraint satisfaction problem and solve them using existing SAT solvers. We then conduct a user study in which we collect data on both participant interactions and reported difficulty. We find that neither participants' reported difficulty nor their behavioural signals correlate meaningfully with SAT solver metrics; however, we find evidence that expertise moderates the relationship between solver metrics and reported difficulty. In this process, we uncover distinct, recurring solving strategies that indicate human preference for complex propagation, diverging from solver-measured complexity.
Tags
Links
- Source: https://arxiv.org/abs/2608.23300v1
- Canonical: https://arxiv.org/abs/2608.23300v1
Trouble viewing inline? Open PDF directly â
Full Text
36,120 characters extracted from source content.
Expand or collapse full text
Evaluating SAT Solver Metrics as Predictors of Human-Perceived Nonogram Difficulty Changdao He⥠Affiliation: Department of Computing Science, University of Alberta Yibing Ju Affiliation: Department of Computer Science, University of Toronto Jonathan Calver Affiliation: Department of Computer Science, University of Toronto Alice Gao Affiliation: mhe14@ualberta.ca bing.ju@mail.utoronto.ca calver@cs.toronto.edu ax.gao@utoronto.ca Affiliation: Department of Computer Science, University of Toronto Abstract Algorithmic solver effort is often assumed to align with perceived puzzle difficulty, but this assumption is rarely tested against human solving data. We evaluate this assumption for Nonograms, a popular logic puzzle similar to Sudoku in which numeric clues along each row and column determine a unique solution grid. We formulate Nonograms as a constraint satisfaction problem and solve them using existing SAT solvers. We then conduct a user study in which we collect data on both participant interactions and reported difficulty. We find that neither participantsâ reported difficulty nor their behavioural signals correlate meaningfully with SAT solver metrics; however, we find evidence that expertise moderates the relationship between solver metrics and reported difficulty. In this process, we uncover distinct, recurring solving strategies that indicate human preference for complex propagation, diverging from solver-measured complexity. 22footnotetext: These authors contributed equally.33footnotetext: Work done while at the University of Toronto. 1 Introduction Logic puzzles have been studied extensively; in particular, the efficacy of solver metrics at predicting difficulty has often been investigated for grid-based games such as Sudoku (for an overview, see [17]). Here, we study Nonograms, which are logic puzzles in which the clues beside each row and column specify the lengths of consecutive runs of filled cells. For example, the clue â1 31\ 3â denotes a run of one filled cell followed by at least one empty cell which is in turn followed by a run of three filled cells. The player must determine which cells are filled so that all row and column clues are satisfied simultaneously. Figure 1 shows a small example and its unique solution. Figure 1: Example Nonogram. Numbers beside each row and column indicate the lengths of consecutive filled-cell runs, in order. Filled cells form the unique solution. Multiple prior studies have examined how algorithmic solvers can be used to measure puzzle difficulty [4, 18], but most lack validation on human data. Motivated by this, we ask two research questions. ⢠RQ1: To what extent do SAT solver statistics correlate with participant-reported puzzle difficulty? ⢠RQ2: To what extent do SAT solver statistics correlate with human solving behaviour? We formulate Nonogram solving as a Boolean satisfiability (SAT) problem and solve the resulting instances using conflict-driven clause learning (CDCL) solvers, from which we derive solver statistics including decisions, propagations, and conflicts. We then conduct a behavioural study that records participant interactions and self-reported difficulty. We expected greater solver effort to correlate with higher reported difficulty. Further, we expected specific solver metrics to align with certain behaviour; for example, the number of conflicts encountered by the solver may correlate with the number of errors made by a human participant, and the number of decisions encountered by the solver may correlate with the number of pauses made by a human participant. In this exploratory study, we find little evidence that SAT solver statistics positively associate with participant-reported difficulty or with behavioural signalsâan initially discouraging result for the specific solver metrics, encoding, and puzzle sample examined. Participant trajectories and survey responses further suggest that starting footholds and constraint-propagation chains may be relevant to human judgments but are not directly represented by the SAT statistics considered. 2 Related Work 2.1 Algorithms and Solvers Many algorithms have been proposed for solving grid-based puzzle games. For Nonograms in particular, the methods employed include genetic algorithms [20], depth-first search and permutations generation [24], and a heuristic algorithm combined with a neural network [6]. Constraint-based formulations of Nonograms include a 2-SAT-based reasoning framework [3], an integer linear programming formulation for colored Nonograms that generalizes an earlier black-and-white model [13], and a CSP-based solver that decomposes the puzzle into separate row and column CSPs before combining them into a global CSP [1]. Human-oriented solver approaches have also been proposed, including line-by-line reasoning and deterministic guessing [4, 18]. Unlike these decomposition-based CSP formulations, our formulation encodes the complete puzzle as a single CNF instance with explicit block-start variables, which we detail in Section 3.1. 2.2 Puzzle Difficulty Puzzle difficulty, and Nonogram difficulty in particular, has received considerable attention. In terms of mathematical difficulty, Nonograms are shown to be NP-hard [21], and the difficulty of the inference problem (co-NP-complete) is largely determined by the density of filled cells [10]. However, we are interested in the human-perceived difficulty of Nonogram puzzles, often studied in the context of the automatic generation of puzzles. [8] provide an overview of procedural generation of puzzles in a broader context, emphasizing that difficulty is not a single intrinsic property, but instead reflects the interaction between problem structure, solving processes, and evaluation criteria. For specific grid-based logic puzzles, it is common to identify features likely to correlate with difficulty and derive weighted difficulty measures, using user ratings [12] or a proxy such as solve time [22]. Computational measures such as informational entropy [7] have also been studied in relation to user feedback. On the other hand, difficulty measures have been composed from metrics from human-like solvers [4, 18] but have not been validated against actual human subjects. We note that solve time and perceived difficulty have been used interchangeably in much of the existing literature [22, 15, 23]. However, more recent work suggests that while the two measures track each other reasonably well in general, they decouple around insight moments [14]. Therefore, we aim to obtain a more holistic understanding of human perception of puzzle difficulty by collecting data on solving behaviour as well as reported difficulty. 3 Methodology 3.1 SAT Problem Formulation and Metrics Formally, a Nonogram is defined on an RĂCRĂ C grid. Each row r is associated with an ordered sequence of positive integers (r)=(a1,âŚ,ak),a^(r)=(a_1,âŚ,a_k), where aia_i denotes the length of the i-th contiguous block of filled cells. Blocks must appear in order and be separated by at least one empty cell. Column clues (c)b^(c) are defined analogously. A valid solution is a binary matrix Xâ0,1RĂCXâ\0,1\^RĂ C satisfying all row and column constraints. We encode this constraint satisfaction problem as a Boolean satisfiability (SAT) instance in conjunctive normal form (CNF). The encoding introduces two types of Boolean variables. For each cell (r,c)(r,c) we create a variable xr,cx_r,c indicating whether the cell is filled. For each block i in a row or column and each feasible starting position p, we introduce a block-start variable si,ps_i,p, where si,p=1s_i,p=1 iff block i begins at position p. Each block must select exactly one start position. Feasible start positions are computed using tight bounds derived from a packed configuration of all blocks. Let a line have length N and block lengths (L1,âŚ,Lk)(L_1,âŚ,L_k). The earliest start of block i is mini=âj<i(Lj+1). _i= _j<i(L_j+1). Let T=âj=1kLj+(kâ1)T= _j=1^kL_j+(k-1) be the minimum length required for all blocks. The remaining slack is S=NâTS=N-T, yielding the latest start maxi=mini+S _i= _i+S. Restricting p to [mini,maxi][ _i, _i] eliminates structurally impossible placements before CNF construction. The constraints enforce exactly-one placement of each block, ordering between consecutive blocks, coverage of cells by selected blocks, and justification of filled cells. Row and column constraints share the same cell variables, ensuring global consistency. A full description of the clause construction is given in Appendix A. Let N denote line length and k the number of blocks. Each line introduces OâĄ(kâN)O(kN) auxiliary variables and OâĄ(kâN2)O(kN^2) clauses in the worst case due to pairwise and ordering constraints. For the puzzle sizes considered in our experiments (up to 10Ă1010Ă 10 grids), the resulting CNF instances remain compact and are solved within milliseconds by modern CDCL solvers. We adopt a block-start encoding rather than a purely cell-based formulation because it exposes explicit block-placement decisions and yields stronger propagation during search. 3.1.1 Solver-Derived Difficulty Metrics We collect the following metrics from the SAT solver for each puzzle: the number of decisions, which occur when the solver chooses a variable value arbitrarily (based on a heuristic) because it cannot yet deduce the value logically; the number of propagations, which occur when the solver deduces a variable assignment that must be true to satisfy a clause; and the number of conflicts, which occur when a clause becomes false under the current partial assignment. We treat these statistics as measures of solver search effort and investigate whether higher values correspond to greater human-perceived difficulty. All solver-metric results reported in this paper use MiniSat 2.2 [9], as its minimal preprocessing preserves a clear correspondence between CDCL search behaviour and interpretable metrics such as conflicts, decisions, and propagations. Glucose 4.2 [2] is used only as a secondary solver, to verify that these trends are not specific to a single CDCL implementation. We do not use heavily preprocessing solvers such as CaDiCaL [5] for behavioural comparisons, as aggressive simplification may significantly alter solver statistics and obscure their relationship with human solving processes. 3.2 Experimental Design The experiment was designed to collect both fine-grained behavioural interaction data and subjective difficulty judgments while controlling for prior experience and learning effects. 3.2.1 Participants and Recruitment Participants were recruited between January 2026 and May 2026 through email outreach and flyers posted in university buildings. Eligible participants were students registered at a North American research university. The study protocol was reviewed and approved by the ethics board of a North American research university. Most participants completed the study in person, although a smaller number participated remotely using the same web-based experimental platform and study procedure. Gender and other demographic characteristics beyond age eligibility and academic program were not collected. 3.2.2 Procedure Participants were asked to complete the study individually using a web-based platform. Each session consisted of a tutorial, a warmup phase, a pre-survey, three experimental puzzles, and a post-survey. The session began with a short tutorial video (approximately two minutes) introducing the rules of Nonograms and demonstrating the user interface. Participants then completed a warmup puzzle (maximum five minutes) to familiarize themselves with the interface and available features. Data from this phase were not included in the analysis. Next, participants completed a pre-survey collecting background information about their experience with Nonograms and other logic puzzles, including prior exposure to puzzle sizes, frequency of puzzle play, and self-reported skill levels on a 1â10 scale. Participants then attempted three experimental puzzles sequentially. During each puzzle they could toggle cells, cross cells, undo actions, reset the grid, request hints, submit solutions for verification, or skip the puzzle if they were unable to complete it. Immediately after each puzzle (whether solved or skipped), participants reported the perceived difficulty on a 1â5 scale (with an N/A option for skipped puzzles) and indicated how frequently they relied on guessing rather than logical deduction. After completing all puzzles, participants filled out a post-survey. In this survey, they were allowed to revise their difficulty ratings and provided open-ended explanations for their judgments, additional self-reports of guessing frequency, descriptions of strategies used, and optional comments about perceived puzzle difficulty. 3.2.3 Puzzle Selection We generated 1,000 random uniquely solvable 10Ă1010Ă 10 Nonograms with 50% filled cells. Prior computational work suggests that Nonogram solving behaviour varies with both grid size and filled-cell density: substantial changes in the number of unresolved cells have been observed when either parameter is varied [3], and density has been identified as a major factor in inference difficulty [10]. We therefore fixed both grid size and density to reduce these structural sources of variation and make the candidate puzzles more comparable. We then ranked the puzzles by MiniSat 2.2 conflict count and selected six: two with the lowest number of conflicts, two with conflict counts near the median, and two with the highest number of conflicts, excluding the top 5% (see Figure 2). This produced a small set spanning low, medium, and high solver-measured difficulty without relying on extreme outliers. Figure 2: Distribution of number of conflicts over 1,000 randomly generated qualifying puzzles. 3.2.4 Measured Variables The experiment recorded both behavioural interaction data and subjective self-reports. Raw interactions recorded include total solving time, cell updates, undo and reset operations, hint requests, incorrect solution submissions, and whether the puzzle was solved or skipped. All interaction events were timestamped, allowing reconstruction of complete solving trajectories. Subjective measures consisted of perceived difficulty ratings (1â5 scale) and self-reported frequency of guessing. The post-survey additionally collected qualitative explanations of difficulty judgments and descriptions of solving strategies, enabling exploratory analysis of reasoning styles. Finally, the pre-survey collected measures of prior Nonogram experience, general logic puzzle experience, and self-rated skill levels. These variables allow us to control for individual differences when comparing human performance with solver-derived difficulty metrics. 3.2.5 Implementation Details The web-based experimental platform was implemented using Next.js and React, with participant logs stored as newline-delimited JSON files. Nonograms were encoded in Python and SAT solving was performed through PySAT 1.8.dev23 [11]. As outlined in Section 3.1.1, all metrics reported in this paper come from MiniSat 2.2, with Glucose 4.2 used only for the secondary verification; CaDiCaL 1.9.5 was run solely to independently confirm puzzle solvability and did not contribute to any reported metric. 4 Results A total of 68 participants completed the study; 1 requested withdrawal, leaving 67 participants and 201 puzzle attempts in the final analysis. Each participant attempted three of the six puzzles. We enumerated all 120 possible ordered selections of three distinct puzzles and assigned participants unique sequences without replacement; therefore, 67 of the 120 sequences were used. This varied both puzzle subset and presentation order, helping reduce systematic order effects. We use participantsâ revised, final difficulty ratings from the post-survey. Because each participant rates only 3 of the 6 puzzles, we fit a Bradley-Terry model to obtain comparable adjusted rankings across all six puzzles. SAT metric Ď p Decisions -0.257 0.623 Propagations -0.257 0.623 Conflicts +0.000 1.000 Table 1: Spearman correlation between Bradley-Terry-adjusted puzzle difficulty ranking and SAT solver metrics. RQ1: We conducted a Spearman rank correlation test between the BT-adjusted participant-reported difficulty rankings and SAT solver metric rankings, and found no significant correlation at the puzzle level (Table 1). 4.1 Expertise Participants reported expertise on six items: Nonogram skill (1â10), general puzzle skill (1â10), how often they play Nonograms, how often they play puzzles, the range of Nonogram sizes theyâve tried, and the range of logic-puzzle types they know. PCA on the six dimensions of participant self-reported expertise shows that PC1 alone explains 56% of the variance, and all six items load positively, suggesting that there is a single dominant dimension. Factor analysis scores agree closely with the naive z-mean composite, obtained from averaging the z-scores of each of the six dimensions per participant. For simplicity of interpretation, we choose to represent expertise with z-mean in the analysis that follows. Figure 3: The distribution of the z-mean expertise score across participants. Conducting a Spearman test between participant expertise composite and their mean final difficulty, we find no statistically significant relationship (Ď=â0.094Ď=-0.094, p=0.451p=0.451). However, fitting a crossed-random-effects linear mixed model (LMM), with random intercepts for both participant ID and puzzle ID simultaneously, we discover that expertise significantly moderates the relationship between SAT solver metrics and reported difficulty through a negative coefficient (see Table 2). That is, more expert participantsâ difficulty ratings become progressively less sensitive to how hard the puzzle is as measured by SAT-solver metrics. SAT metric Metric β Expertise β Interaction β Decisions -0.0007 +0.0875 -0.0096* Propagations +0.0001 +0.2053 -0.0004** Conflicts +0.0067 +0.0891 -0.0247** Table 2: Moderation of the SAT-metric â difficulty relationship by participant expertise: fixed effects from a crossed-random-effects LMM (difficulty âź metric Ă expertise, with crossed random intercepts for participant and puzzle). * p<.05p<.05, ** p<.01p<.01. 4.2 Behavioural Data We extract the following signals from data collected as the participants solve the puzzles: ⢠Time to solve: the elapsed time it takes for a participant to solve the puzzle (submit a solution that is correct). If a participant fails to solve the puzzle (skipped), the time to solve is the total amount of time that the participant spent before skipping. ⢠Pause count: the number of times a participant paused in the process of solving a puzzle. A pause is any gap in interaction that exceeds 2.362.36s, the equal-posterior threshold between components in the gap length distribution (see Appendix B). ⢠Error count: the number of times a participant filled a cell black where the correct solution is white. ⢠Hint count: the number of hints the participant used. Outcome Ď p Mean time to solve (s) -0.541 <<.001 Mean pause count -0.507 <<.001 Mean error count -0.407 <<.001 Mean hints used -0.583 <<.001 Table 3: Spearman correlation between participant expertise (composite score) and behavioural outcomes, aggregated to participant-level means. A second, participant-level Spearman correlation test shows a strong relationship between expertise and behaviour (see Table 3): higher expertise scores were associated with faster solving, fewer hints and pauses, and fewer errors; this further validates our approach for constructing the expertise composite. RQ2: Fitting a crossed-random-effects LMM for each behavioural signal and SAT metric pair, we find no significant correlation between any particular recorded participant behaviour and solver metric (see Figure 4). Figure 4: Behavioural signals regressed on SAT solver metrics: fixed effects from a crossed-random-effects LMM (behavioural signal âź metric, with crossed random intercepts for participant and puzzle). 4.3 Survey Responses For each puzzle, participants were asked to respond to two questions: âWhy did you rate this difficulty? What made it easy/hard?â and âWhat strategies did you use when solving the puzzles?â They also provided any additional general comments. Using the Claude Sonnet 4.6 language model (an approach partially supported by [25]), the responses were coded using two categories of labels: thirteen difficulty themes and eight strategy themes. The full codebook, along with an example occurrence for each code, is included in Appendix C. We conducted rank-biserial correlation on the various themes against participant-rated difficulty; Figure 5 shows that constraint propagation is negatively correlated with subjective difficulty, whereas ambiguity, guessing, and cognitive load are positively correlated with subjective difficulty. Figure 5: Relationship between each difficulty theme and participant-reported difficulty. 5 Discussion We acknowledge that the investigations into puzzle-level correlations are exploratory due to the small sample size of 6 puzzles, and the puzzle assignments are somewhat unbalanced (28â43). Notwithstanding these limitations, the lack of evidence for SAT solver metrics predicting human-perceived difficulty (as reported or proxied by behavioural signals) suggests that human and solver difficulty arise from different underlying mechanisms. Prior Sudoku research has proposed that clarity and intuitiveness are critical components of perceived difficulty [22]. Relatedly, humans have been shown to prefer constraint propagation and to be averse to backtracking [16]. Our results support this claim: participants who mentioned constraint propagation rated their puzzles as meaningfully easier, while guessing, ambiguity, and cognitive loadâassociated with backtrackingâwere more common among puzzles rated as harder. Further, [19] suggest that humans apply complex propagation schemes; these align with strategies that puzzle-hosting websites commonly share as tips for players to improve, several of which were reported by our own participants. The strategy theme mentioned most frequently at 46%, the âfootholdââthat is, a line whose configuration can be fully determined from its clues aloneâis visible in a heatmap of the first actions that players take (see Figure 6). Figure 6: Heatmap of the first cell acted upon for each puzzle, by frequency. We posit that this causes a meaningful divide between solving processes of the human and the SAT solver. A human solver focuses on a âstrategyâ and prioritizes using advanced propagation schemes that combine several constraints at once. In contrast, because we only encoded the basic rules of the Nonogram, reasoning strategies that involve multiple constraints are not available to SAT solvers, which are limited to unit propagation on individual clauses. However, CDCL-backed solvers like MiniSat 2.2 learn joint patterns of clauses after encountering conflicts while solving the problem, enriching their understanding; this may be analogous to the process by which beginner players discover and start to implement strategies during solving. Indeed, Table 2 shows evidence that expert difficulty ratings diverge further from solver ratings than beginnersâ ratings do. Thus, it is possible that solvers would be better at capturing the difficulties encountered by human players with more propagation-complete encodings, as higher expressiveness may better capture propagation schemes used by humans. 6 Conclusion This exploratory study found that SAT solver metrics largely do not align with how humans experience and solve Nonograms; trajectory and survey response analysis revealed recurring human solving strategies that solver metrics do not capture. We find some evidence that expertise moderates the relationship between reported difficulty and solver metrics, and hypothesize that this reflects participantsâ growing understanding of advanced propagation strategies. We call for further investigation into whether the expressiveness of CSP encodings of puzzles affects the efficacy of constraint solver metrics as difficulty-tracking methods. Additionally, future work could extend this study to a larger scale with more puzzle samples, as well as to other logic puzzles (e.g., Sudoku, Norinori). More broadly, our results invite a reassessment of the role of computational proxies in predicting difficulty for puzzles. Acknowledgements We thank Juliana Zhang for developing the frontend of the experimental platform. We thank Riyad Valiyev for assisting with running study sessions and exploratory analysis of participant text responses. We also thank the study participants for their time and feedback. Appendix A Detailed SAT Encoding This section provides the detailed clause construction for the SAT encoding used in this study. For each cell (r,c)(r,c), we introduce a Boolean variable xr,cx_r,c indicating whether the cell is filled. For each block i and feasible start position p, we introduce a variable si,ps_i,p. Exactly-one placement. Each block must be placed exactly once. Let si,pp\s_i,p\_p denote the set of feasible start variables for block i. We enforce âpsi,p _ps_i,p and, for all pâ qpâ q, ÂŹsi,pâ¨ÂŹsi,q. s_i,p s_i,q. Block ordering. To enforce separation between consecutive blocks, if block i starts at p, block i+1i+1 must start at position at least p+Li+1p+L_i+1. For any invalid pair (p,q)(p,q) with q<p+Li+1q<p+L_i+1, we add ÂŹsi,pâ¨ÂŹsi+1,q. s_i,p s_i+1,q. Coverage constraints. If block i starts at p, all cells in its span must be filled: si,pâxjfor âjâ[p,p+Liâ1],s_i,pâ x_j jâ[p,p+L_i-1], encoded as ÂŹsi,pâ¨xj. s_i,p x_j. Cell justification. Any filled cell must be covered by at least one block placement: xjââ(i,p)â covering âjsi,p,x_jâ _(i,p) covering js_i,p, which is encoded as ÂŹxjâ¨si1,p1â¨âŻâ¨sim,pm. x_j s_i_1,p_1 ⌠s_i_m,p_m. If no block placement can cover a cell j, the clause ÂŹxj x_j is added. Empty lines. If a line contains no blocks, all cells in that line are constrained to be empty. Appendix B Identifying Pauses We separate all gaps in interaction into three components using a Gaussian mixture model (ÎâBIC=7387.1 =7387.1 against one component). The first component, with mean 0.010.01s, results from the interface allowing participants to drag across cells to fill them consecutively. We separate the rest of the interactions into two components to distinguish smooth logic chaining from blocks in reasoning or deliberation. The pause threshold is therefore selected to be 2.362.36s, the equal-posterior threshold between components 2 and 3. Figure 7: Log-interval distribution of interaction gaps recorded from participant behaviour during puzzle solving, with a three-component GMM. Appendix C Codebook Table 4 gives the codes used in the qualitative analysis, with an example occurrence of each code from the dataset. Table 4: Difficulty themes and strategy taxonomy, with example responses. Category Code Theme / Strategy Example Difficulty FOOT Starting footholds / forced lines âNot a lot of freebiesâ CLUE Clue magnitude âClue number too smallâ PROP Constraint propagation / chaining âeasier to solve using eliminationâ AMBIG Combinatorial ambiguity / overlap reasoning âMultiple intermediate steps seemed possible, but only one worked in the endâ GUESS Guessing / certainty ânever need to guessâ HINT Hint usage âI use many hints.â ERR Mistakes / error recovery âI got a little stuck but maybe thatâs because I misread some of the numbersâ LEARN Learning / practice / fatigue âeasier than first oneâ LOAD Cognitive load / tracking âKeeping track of what has been filled out made things overall harder.â VIS Visual / spatial layout âIn a lot of other nonograms, they usually form a picture so you kind of get a free hint as to what the general shape should look like but these ones were more randomâ TIME Time pressure âGuessed because of time constraints.â UI Interface friction âundo button should not be the same color and right beside the reset buttonâ AFF Confidence / affect âI never got stuck and felt confident the entire time.â Strategy S_FORCED Forced-line solving âdetermine the fixed lines firstâ S_CONSTR Most-constrained-first ordering âLocate the largest number block first.â S_OVERLAP Overlap analysis âfinding overlapsâ S_EDGE Edge / anchor exploitation âfixed arrangements from start/end positions, see possible solutions with remaining white spaceâ S_CROSS Row/column cross-referencing âTrying to compare values across rows and columns to see where the hints matched.â S_NEG Negative marking (X-ing whites) âTo fulfill the known lines first, and then along the guessing, I can cross some connected cells.â S_TRIAL Trial-and-error / contradiction âlogical deduction, trial and errorâ S_HINT Hint-as-tool âI feel like itâs better to use hints especially at the very beginning, but I had a lot left when finished.â References [1] A. Aramian and V. Yeghiazaryan (2025) Solving Nonograms: A Constraint Satisfaction Approach. In Computers and Games, M. Hartisch, C. Hsueh, and J. Schaeffer (Eds.), Cham, p. 130â141 (en). External Links: ISBN 978-3-031-86585-5, Document Cited by: §2.1. [2] G. Audemard and L. Simon (2018) On the Glucose SAT Solver. International Journal on Artificial Intelligence Tools 27 (01), p. 1840001. External Links: ISSN 0218-2130, Link, Document Cited by: §3.1.1. [3] K. J. Batenburg and W. A. Kosters (2008) A Reasoning Framework for Solving Nonograms. In Combinatorial Image Analysis, V. E. Brimkov, R. P. Barneva, and H. A. Hauptman (Eds.), Berlin, Heidelberg, p. 372â383 (en). External Links: ISBN 978-3-540-78275-9, Document Cited by: §2.1, §3.2.3. [4] K. Batenburg, S. Henstra, W. Kosters, and W. Palenstijn (2009) Constructing Simple Nonograms of Varying Difficulty. PU.M.A. Pure Mathematics and Applications 20. Cited by: §1, §2.1, §2.2. [5] A. Biere, T. Faller, K. Fazekas, M. Fleury, N. Froleyks, and F. Pollitt (2024) CaDiCaL 2.0. In Computer Aided Verification, A. Gurfinkel and V. Ganesh (Eds.), Cham, p. 133â152 (en). External Links: ISBN 978-3-031-65627-9, Document Cited by: §3.1.1. [6] J. M. Buades Rubio, A. Jaume-i-CapĂł, D. LĂłpez GonzĂĄlez, and G. MoyĂ Alcover (2024) Solving nonograms using neural networks. Entertainment Computing 50, p. 100652. External Links: ISSN 1875-9521, Link, Document Cited by: §2.1. [7] E. Y. C. Chen, A. White, and N. R. Sturtevant (2023) Entropy as a Measure of Puzzle Difficulty. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment 19 (1), p. 34â42 (en). External Links: ISSN 2334-0924, Link, Document Cited by: §2.2. [8] B. De Kegel and M. Haahr (2020) Procedural Puzzle Generation: A Survey. IEEE Transactions on Games 12 (1), p. 21â40. External Links: ISSN 2475-1510, Link, Document Cited by: §2.2. [9] N. EĂŠn and N. SĂśrensson (2004) An Extensible SAT-solver. In Theory and Applications of Satisfiability Testing, E. Giunchiglia and A. Tacchella (Eds.), Berlin, Heidelberg, p. 502â518 (en). External Links: ISBN 978-3-540-24605-3, Document Cited by: §3.1.1. [10] A. Foote and D. Krizanc (2025) Nonogram: Complexity of Inference and Phase Transition Behavior. arXiv. Note: arXiv:2507.07283 [cs.C] External Links: Link, Document Cited by: §2.2, §3.2.3. [11] A. Ignatiev, A. Morgado, and J. Marques-Silva (2018) PySAT: A Python Toolkit for Prototyping with SAT Oracles. In Theory and Applications of Satisfiability Testing â SAT 2018, O. Beyersdorff and C. M. Wintersteiger (Eds.), Cham, p. 428â437 (en). External Links: ISBN 978-3-319-94144-8, Document Cited by: §3.2.5. [12] B. Kartal, N. Sohre, and S. Guy (2016) Data Driven Sokoban Puzzle Generation with Monte Carlo Tree Search. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment 12 (1), p. 58â64 (en). External Links: ISSN 2334-0924, Link, Document Cited by: §2.2. [13] L. Mingote and F. Azevedo (2009) Colored Nonograms: An Integer Linear Programming Approach. In Progress in Artificial Intelligence, L. S. Lopes, N. Lau, P. Mariano, and L. M. Rocha (Eds.), Berlin, Heidelberg, p. 213â224 (en). External Links: ISBN 978-3-642-04686-5, Document Cited by: §2.1. [14] N. V. Moroshkina, E. I. Pavliuchik, A. V. Ammalainen, V. A. Gershkovich, and O. V. Lvova (2024) The Aha! experience is associated with a drop in the perceived difficulty of the problem. Frontiers in Psychology 15 (English). External Links: ISSN 1664-1078, Link, Document Cited by: §2.2. [15] A. Naji and S. Salous (2024) Sudoku Puzzle Difficulty Rating based on Fuzzy Logic. Journal of Computer Science and Technology Studies 6 (2), p. 86â91 (en). External Links: ISSN 2709-104X, Link, Document Cited by: §2.2. [16] R. PelĂĄnek (2011) Difficulty Rating of Sudoku Puzzles by a Computational Model. In Proceedings of the Twenty-Fourth International Florida Artificial Intelligence Research Society Conference, Note: [TLDR] This work provides a simple computational model of human solving activity and evaluates it over collected data, showing that there are two sources of problem difficulty: complexity of individual steps (logic operations) and structure of dependency among steps. External Links: Link Cited by: §5. [17] R. PelĂĄnek (2014) Difficulty Rating of Sudoku Puzzles: An Overview and Evaluation. arXiv. Note: arXiv:1403.7373 [cs.AI]Comment: 24 pages External Links: Link, Document Cited by: §1. [18] M. Roucairol and T. Cazenave (2024) Generating Difficult and Fun Nonograms. In Computers and Games: 12th International Conference, CG 2024, Virtual Event, November 25-29, 2024, Revised Selected Papers, Berlin, Heidelberg, p. 119â129. External Links: ISBN 978-3-031-86584-8, Link, Document Cited by: §1, §2.1, §2.2. [19] H. Simonis (2005) Sudoku as a Constraint Problem. In Proceedings of the 4th International Workshop on Modelling and Reformulating Constraint Satisfaction Problems, Note: [TLDR] This paper tries to understand the puzzle from a constraint point of view, shows models to solve and generate puzzles and gives an objective measure of the difficulty of a puzzle instance. External Links: Link Cited by: §5. [20] J. Tsai and P. Chou (2011) Solving Japanese puzzles by genetic algorithms. In 2011 International Conference on Machine Learning and Cybernetics, Vol. 2, p. 785â788. External Links: ISSN 2160-1348, Link, Document Cited by: §2.1. [21] N. Ueda and T. Nagao (1996) NP-completeness Results for NONOGRAM via Parsimonious Reductions. Technical report Technical Report TR96-0008, Tokyo Institute of Technology. Cited by: §2.2. [22] H. Wang, Y. Wang, and C. Sun (2012) Rating Logic Puzzle Difficulty Automatically in a Human Perspective. In Proceedings of Nordic DiGRA 2012 Conference, (en). External Links: ISSN 2342-9666, Link, Document Cited by: §2.2, §2.2, §5. [23] S. Wang (2024) A Dataset of Sudoku Puzzles With Difficulty Metrics Experienced by Human Players. IEEE Access 12, p. 104254â104262. External Links: ISSN 2169-3536, Link, Document Cited by: §2.2. [24] J. WiÄckowski and A. Shekhovtsov (2021) Algorithms Effectiveness comparison in solving Nonogram boards. Procedia Computer Science 192, p. 1885â1893. External Links: ISSN 1877-0509, Link, Document Cited by: §2.1. [25] Z. Xiao, X. Yuan, Q. V. Liao, R. Abdelghani, and P. Oudeyer (2023) Supporting Qualitative Analysis with Large Language Models: Combining Codebook with GPT-3 for Deductive Coding. In Companion Proceedings of the 28th International Conference on Intelligent User Interfaces, IUI â23 Companion, New York, NY, USA, p. 75â78. External Links: ISBN 979-8-4007-0107-8, Link, Document Cited by: §4.3.