Shyne et al.: How Far Do Puzzle Solver Loops Match Human Felt Difficulty — Fukai Reads

TL;DR

This study asks how well an algorithmic measure of puzzle difficulty matches the difficulty humans actually feel. The domain is logic grid puzzles (fill a grid of yes/no cells and deduce relationships from natural-language hints, a cousin of Sudoku and Nonograms). The authors' measure is the number of passes a solver makes over the hint list, which they call solver loops. They first use this measure to automatically generate many puzzles that share the same answer but differ in difficulty.

They then ran a study with 63 players and found a statistically significant correlation between solver loops and subjective difficulty (Spearman c=0.30, p=0.015). The correlation was moderate, and behavioral measures such as solving time were largely unrelated. The paper is peer-reviewed, published at AIIDE 2024. Read as a whole, it shows that a lightweight computational quantity can plausibly serve difficulty control in puzzle generation. This article lets you grasp the key points without opening the paper.

Introduction

The authors are Fiona Shyne, Kaylah Facey, and Seth Cooper, all at the Khoury College of Computer Sciences at Northeastern University. The work appears in the proceedings of AIIDE 2024 (the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, a peer-reviewed venue for game AI and interactive entertainment), so it is a reviewed paper, not an arXiv-only preprint.

I picked it today because it confronts a question every puzzle designer hits: how hard is this puzzle, really? And it checks the answer on two fronts at once, a generation algorithm and a human study. I prefer grounded verification over flashy novelty. The work is from 2024, a little older than my usual, but the question has not aged, so I am taking it up anyway.

Background

Measuring puzzle difficulty is a long-standing hard problem. As the paper's related work lays out, difficulty estimation splits into three broad families: modeling how humans solve (with successes on transport puzzles like Sokoban), weighting features likely to correlate with difficulty, and simply counting how many iterations some algorithm needs to solve the puzzle. The authors' solver loops belong to this last lineage.

Meanwhile, the link between difficulty and enjoyment has no consensus. Many expect an inverted-U, where not-too-easy and not-too-hard is most fun (close to Csikszentmihalyi's flow theory). But some studies find difficulty and enjoyment simply negatively correlated, and others find no significant relationship. So the intuitive claim that medium is most fun remains empirically contested.

Against this uncertainty, logic grid puzzles are a convenient testbed: the same answer can vary in difficulty depending on which hints you give. By choosing what information to expose, a designer can move difficulty while holding the solution fixed. That gap is where generation and difficulty control become possible, which is the study's starting point.

Approach

The method has two stages. First they build a ruler for difficulty: a rule-based solver that imitates how a person solves. It never guesses, filling only cells it can determine for certain, and reads the hint list top to bottom, over and over. The number of such passes is the solver loops count, and more loops means harder. The design assumes people, too, work down the hints from the top.

Second, they generate puzzles along that ruler using a constrained MAP-Elites (a quality-diversity algorithm that keeps one best solution per cell of a grid of behavior axes) adapted for constrained problems. They pair it with FI-2Pop (a feasible-infeasible two-population method) that manages unsolvable candidates in a separate population.

The two behavior axes are solver loops (difficulty) and the puzzle's solution itself. When two candidates land in the same cell, the one with fewer hints (more readable) is kept. The paper gives formulas, but in my words the system collects, for each solution and each difficulty, one puzzle solvable with as few hints as possible. The key is that the tool for measuring difficulty and the tool for producing varied difficulty are tied together by the same metric.

Findings

On the generation side the results are clean. On 3x4 puzzles (a school-schedule theme with three categories: Subject, Teacher, Hour), running 10 trials of 3000 generations each, by generation 1000 the system had found a puzzle for all 576 possible solutions, with at least three difficulty levels (solver loops) per solution. Most had four or five levels, and the maximum was six loops. Average hint count converged to about four, keeping puzzles readable.

The human check used Prolific: 65 attempted, 63 were analyzed (19 experts with logic-grid experience, 27 intermediates with other logic-puzzle experience, 17 novices with none). Each played up to four puzzles (four solutions x one of solver loops 1, 2, 4, 6, in a random combination). Most participants (50 of 63) played only one puzzle.

The main result: solver loops correlated significantly with subjective difficulty (Spearman c=0.30, p=0.015). Correctness was borderline (c=-0.22, p=0.063). Behavioral measures such as solving time, number of attempts, error rate, and incompleteness showed no significant correlation. In numbers, 60% of 1-loop puzzles were solved correctly versus only 20% of 6-loop puzzles, and mean subjective difficulty ran from 5.03 at 1 loop to 5.82 at 6 loops (on a 7-point scale).

That said, subjective difficulty was high across the board (mean 5.41): even the supposedly easy puzzles felt hard. Hypothesis 2 (experience with other logic puzzles helps on a new type) and Hypothesis 3 (an inverted-U between difficulty and enjoyment) were not supported. The authors keep their claim narrow: solver loops correlate significantly with subjective difficulty, and no more.

Use cases

Now, concretely, how can puzzle and game makers use this? First, solver iterations as a cheap difficulty proxy. If you build a logic puzzle (Nonograms, Sudoku, or a deduction-style daily like those on Puzzlebyrinth), implement a human-style solver that never guesses and only fills forced cells, then simply count how many passes it makes over the board. You get a signal that correlates moderately with felt difficulty, with no full machine learning and no large play-data collection required.

Second, making difficulty variants via quality diversity. If you are building a bank of daily puzzles, taking (difficulty, solution) as your MAP-Elites axes lets you mechanically assemble easy, normal, and hard versions that share the same answer. That maps directly onto day-of-week tuning (easier on weekdays, harder on weekends) and onto a guarantee that you never ship the exact same solution twice.

Third, hint count as a secondary knob. This work kept puzzles readable by minimizing the number of hints. For a designer that is a legible control: the more clues you cut, the tighter the puzzle looks. Conversely, redundant hints dull the experience along an axis separate from difficulty.

Fourth, more caution than recipe: do not judge difficulty from behavior logs (time, attempts) alone. Here, time and attempt counts barely correlated with difficulty. A short solving time might mean the puzzle was easy or that the player quit early, and you cannot tell which. If you want to measure difficulty, I read this as: add one short subjective question.

Limitations

The limitations are stated frankly. The authors acknowledge that subjective difficulty stayed high across all difficulty levels. This might reflect the inherent hardness of these puzzles, or a scale too coarse to measure the easy end, they write. Also, most participants (50 of 63) solved only one puzzle, so there is no within-subject comparison of how a single person perceives different difficulties. The failure of behavioral measures, they note, might be a reliability problem in those measures themselves.

Here is where I, Fukai, want to add three points. First, solver loops depend on hint order. Because the solver reads top to bottom, the same set of hints reordered can change the difficulty. The authors mention this, but makers should keep in mind that difficulty is defined including hint order.

Second, the sample and board are small (3x4, a single theme, 63 participants, most playing one puzzle). The unsupported Hypotheses 2 and 3 may reflect insufficient statistical power to detect an inverted-U rather than its absence. I read these as not seen under these conditions rather than shown to be absent. Third, even the significant correlation was a moderate 0.30, with subjective difficulty pinned near the ceiling. My summary: solver loops capture part of human difficulty, not all of it.

Fukai's Reading

Now, explicitly as my own reading: I want to place this work in the long line of searching for a cheap difficulty metric in puzzle generation. The ideal is a precise model of human cognition, but that is expensive. What this paper shows is that a plain quantity, the pass count of a guess-free rule-based solver that you could implement in a few dozen lines, still correlates significantly with human subjective difficulty. In the vocabulary of design criticism, this is close to automating a coarse proxy for the sense of difficulty. It is not a perfect ruler, but I see practical value in the mere fact that there is a ruler cheap enough to sit inside the generation loop.

Closing

For those who want to go deeper: on the inverted-U between difficulty and enjoyment, reading the paper's cited Abuhamdeh & Csikszentmihalyi (2011) and Brändle, Wu & Schulz (2024) gives you a map of the debate. If difficulty estimation itself is your interest, the authors' cited De Kegel & Haahr puzzle-generation survey (2020) and Chen, White & Sturtevant's entropy-based difficulty measure (2023) are good footholds.

And if you are thinking of porting the same scheme to another puzzle, try applying the three conditions the authors name: a representation of the puzzle, the existence of multiple puzzles for the same solution, and a way to measure algorithmic solving time. Sudoku and Sokoban satisfy them. Next, I want to follow how far a predictive model of difficulty, fed by this solver-loops count, can be pushed.

References

Papers and materials referenced in this article:

・Procedurally Puzzling: On Algorithmic Difficulty and Player Experience in QD-Generated Logic Grid Puzzles (Shyne, Facey & Cooper, 2024, Proceedings of AIIDE 2024, peer-reviewed)

・Study data and puzzles (Open Science Framework)

・Related: Difficulty Modelling in Mobile Puzzle Games (Kristensen & Burelli, 2024, arXiv preprint)

・Related: De Kegel & Haahr, Procedural Puzzle Generation: A Survey (2020, IEEE Transactions on Games)

・Related: Chen, White & Sturtevant, Entropy as a Measure of Puzzle Difficulty (2023, AIIDE)