Waugh: Measuring AI's Reasoning with Sudoku and Slitherlink — Fukai Reads

TL;DR

I read a study that turns pencil puzzles — the family of logic puzzles you solve with paper and pencil, such as Sudoku and Slitherlink — into a yardstick for the reasoning ability of large language models (LLMs, AI trained on huge amounts of text that generate writing by predicting the next word). The author is Justin Waugh of Approximate Labs, and it is an arXiv preprint (a not-yet-peer-reviewed manuscript) released on March 2, 2026.

The core idea is that a machine can strictly check not only whether the final answer is correct, but whether every single intermediate move stays within the rules. From 62,231 puzzles across 94 types, 300 puzzles across 20 types were selected, and 51 models from 11 providers were evaluated. Even the strongest, GPT-5.2, reached only 56.0% in the tool-using 'agentic' mode, and by the author's account about half of the benchmark remained unsolved. This article aims to convey the gist without you having to open the paper.

Introduction

What I chose today is 'Pencil Puzzle Bench: A Benchmark for Multi-Step Verifiable Reasoning.' The author is Justin Waugh (Approximate Labs). The arXiv number is 2603.02119, released March 2, 2026. Let me state up front that this is not a peer-reviewed conference paper but a preprint (a not-yet-reviewed manuscript) published as a company research log. It is new, and the discussion around it has not yet accumulated.

Why would I, writing for a puzzle site, pick this? Simply because the subject matter is our own garden. Sudoku, Nurikabe, Slitherlink, Masyu, Yajilin, Light Up — any puzzle lover's hands twitch at the mere names. The very idea of using them as a tool to evaluate AI is suggestive for makers too. I read this study as a story about a machine taking over the 'fairness' of a puzzle.

Background

Recent LLMs, as 'reasoning models' (LLMs trained to write out their chain of thought before answering), show that the more time (computation) you spend, the smarter they get. But how do you measure that smartness fairly? This is hard. Grading essays or code often has to rely on the subjective judgment of a human or another AI.

Pencil puzzles neatly sidestep this grading problem, the author argues. The rules are fully determined and the answer is unique (a single solution is guaranteed), so no subjective grading (judgments that wobble with human or AI preference) is needed. In addition, solving requires long deductive chains; there are dozens of varieties with diverse structures; and because the culture shares 'problems' rather than 'answer keys,' contamination (answers leaking into training data — the seed of cheating) is unlikely. The author lists these four points as why pencil puzzles suit evaluation.

Approach

The author first gathered 62,231 puzzles across 94 types, with verified unique solutions, sourced from the puzzle-sharing site puzz.link. From these, 300 puzzles across 20 types (including several difficulty tiers) were selected as a shared yardstick. The puzzles are constraint-satisfaction problems (finding an arrangement that simultaneously satisfies every rule), and many are described as close to NP-complete (a class where checking an answer is fast, but finding one balloons rapidly with size).

Evaluation comes in two forms. One is 'direct ask,' where the model receives the puzzle and must write a complete solution in a single response. The other is 'agentic' (a way of proceeding where the AI uses tools, makes a move, checks the result, and repeats corrections), where the model solves while using tools to make one or multiple moves, check the board's completeness, render the board as a picture, query the rules, reset, or give up.

The backbone of this study is 'step-level verification.' Each time a move changes the board, a dedicated verifier (a program that mechanically judges the correctness of a move) checks the state and returns which rule was violated, and exactly where on the board. It does not rely on the subjectivity of a person or another AI (no LLM-as-judge). The author positions this as a foundation for 'process supervision' (giving a correctness signal at every intermediate move, not just the final answer) and for reinforcement learning (learning behaviors that maximize reward through trial and error). A Gym-compatible environment operable by external programs was also released for RL work.

Findings

The results are, frankly, sobering. Even running the strongest GPT-5.2 at maximum reasoning effort, agentic solving reached 56.0% (evaluated on 84 puzzles); direct solving stayed at 27.0%. In the abstract the author reports that GPT-5.2 improves 81-fold when reasoning effort is raised from none to maximum (figures as in the original). Put the other way, without pouring in effort (computation), it can barely solve anything.

The other axis is 'agentic iteration.' According to the author, Claude Opus 4.6 without extended thinking solves almost nothing in direct mode (0.3%), but rises to 30.0% when it checks and iterates with tools. On matched puzzles, the reported gains are +30.0 points for Opus 4.6 and +35.7 points for GPT-5.2@xhigh. From this, the author frames 'depth of deliberation' and 'trial-and-correction iteration' as two distinct axes of capability.

And it is an endurance run. Agentic attempts span a median of 29 turns over 17 minutes, reach 113 turns at the 90th percentile, and the longest exceeded 1,221 turns over 14.3 hours (figures as in the original). The author calls it 'a test of sustained long-context use, not one good chain of thought.' Cost varies widely too: about $1.66 per attempt on average (across 17,032 runs), yet cost-per-success spanned roughly 67,000x across models. Taking the best model per provider, the top three (OpenAI, Anthropic, Google) all exceed 33%, while the best Chinese open-weight model reached 6%, as reported.

Use cases

From here, let me name three or more concrete ways puzzle and game makers can use this study. First, a design that puts generation and verification in the same loop. If I were building an auto-generator for Nurikabe or Slitherlink, I would want a verifier inside that, at every move, reports 'which rule was broken, and where.' You get a unique-solution guarantee and localized error information at once.

Second, hint systems. This study's verifier returns not merely 'wrong' but the specific 'this row violates this rule.' That is directly a blueprint for good in-game hints. If I were building a pencil-puzzle app, instead of showing plain 'incorrect' I would progressively reveal the violated rule and its location — translating the verifier's output into the UI.

Third, difficulty estimation and automated playtesting. The number of moves an agentic solve needed (median 29, 113 at P90) can serve as a proxy for difficulty. If I were churning out many levels for a hypercasual title, I could rank levels by how many corrections a model needs and feed that into difficulty-curve tuning. Fourth, this study's two axes (deliberation vs. trial-and-correction) also map onto human players. There is room to design for both the look-ahead type and the trial-and-error type by weaving in undo and a 'check' button — a human counterpart to verifier feedback. On top of that, the released dataset of 62,231 puzzles across 94 types (on Hugging Face) and its source puzz.link are ready-made raw material for production.

Limitations

Let me split the limits into what the author admits and what I noticed. The author explicitly kept both solving methods as 'deliberately simple baselines' — no elaborate prompt engineering to inflate scores — so the results here are closer to a lower bound than an upper bound. He also notes that at maximum reasoning effort, real-world walls such as timeouts and context-length limits appear. That agentic evaluation runs on smaller subsets of 30 or 84 puzzles is a scale gap versus the 300 in direct mode (the author does report matched-puzzle comparisons, which mitigates this).

What I, Fukai, point out is this. First, this is a yardstick for the power to 'solve,' not to 'make or design'; so the implications for makers must be read across indirectly. Second, the leaderboard is a single snapshot of specific versions — GPT-5.2, Opus 4.6, Gemini 3.1 — and the 56% is tied to those versions; it will age quickly as models update. Third, the advantage that 'contamination is unlikely' is, at this point, a design expectation rather than something fully proven, as I read it. Finally, this is a pre-review preprint and a company research log with almost no citations yet — the reservation that replication and external verification are still to come cannot be dropped.

Fukai's Reading

Here, and only here, I flag this as my own interpretation. I want to place this study within the recent current of 'training AI in environments you can verify.' In the vocabulary of design criticism, this comes close to automating a contract that puzzles have long kept — 'there is a unique solution, and the board can always be checked against the rules.' What is interesting is that the verifier is repurposed not as a judge of the final answer but as a 'teacher' that grades every move. A tool meant to make solvers smarter is, in fact, also a quality-assurance tool for makers; I read that duality as the core of this paper.

Closing

Let me leave a map. If you want to go deeper, reading SokoBench, which measures reasoning with Sokoban, and Sudoku-Bench, which measures creative reasoning with Sudoku variants, alongside this one will reveal the terrain of the field. You will grasp how far the idea of 'verifying the process, not just the correctness of the answer' has spread.

For my part, I read the printed paper with a cup of strong drip coffee, drawing colored-pen lines across it. Though it is a story about AI that solves puzzles, by the end it pulls you back to the question of what makes a good puzzle — checkable fairness and a long chain you can see through. For makers too, I think that is not a bad question.

References

Papers and related materials referenced in this article:

・Pencil Puzzle Bench: A Benchmark for Multi-Step Verifiable Reasoning (Justin Waugh, 2026, arXiv preprint)

・Approximate Labs: Pencil Puzzle Benchmark (author's writeup)

・Dataset and run logs (Hugging Face)

・ppbench.com (official site to try puzzles and replay model attempts)

・Related: SokoBench: Evaluating Long-Horizon Planning and Reasoning in Large Language Models (Monti et al., 2026)

・Related: Sudoku-Bench: Evaluating creative reasoning with Sudoku variants (2025)