Teaching Transformers to Solve Combinatorial Problems through Efficient Trial & Error
Efficient trial-and-error GPT-2 combines rules, DFS backtracking, and verification, reaching 99% on Sudoku and 1-in-3 SAT.
Key Findings
Methodology
The framework trains a GPT-2-style causal Transformer to solve combinatorial instances through verified search. It imitates four basic Sudoku rules, then makes informed guesses when rule propagation stalls. A verifier checks partial assignments; conflicts trigger DPLL-like Depth-First Search backtracking. Action-level tokenization encodes (r,c,v) as one three-digit token, while multi-target supervision uses −∑_{i∈S}log p_i over all valid next actions.
Key Results
- The complete system achieves about 99% board accuracy on 100K randomly generated Sudoku puzzles and 99% accuracy on 1-in-3 SAT. GPT-4o, Gemini-1.5 Pro, o3 mini, Gemini-2.5 Flash, and DeepSeek-R1 all obtain 0% board accuracy on the paper’s 9×9 Sudoku evaluation.
- Evaluation covers Random, Kaggle unfiltered, Kaggle filtered, and RRN datasets. Figure 1 reports roughly 99% Sudoku accuracy, exceeding neural baselines including RRN, Recurrent Transformer, and MDM approaches; training on generated puzzles also generalizes well to Kaggle and RRN distributions.
- Under depth-1 guessing, approximately 99.8% of random Sudoku boards are solved after basic rules plus one correct guess. A loss derived from contextual MIN-SUM SET COVER directly targets solution length and outperforms standard cross-entropy empirically.
Significance
The work shows that a Transformer need not emit a complete answer in one pass. With a verifier, it can propose actions, detect contradictions, revise decisions, and expose an interpretable search trace. This addresses a persistent weakness of LLMs on arithmetic, SAT, and Sudoku: fluent generation without reliable constraint maintenance. Because the framework is verifier-driven, it offers a principled route toward SAT, Clique, TSP, and other NP problems.
Technical Contribution
The engineering contributions are action-level tokenization, multi-valid-label training, unified rule propagation plus DFS trajectories, and the efficient C-backed SudokuPy generator. The theoretical contribution is a formulation of one-level, non-adaptive guessing as contextual MIN-SUM SET COVER, yielding a solution-length-oriented loss. Importantly, the solver uses a 42M-parameter vanilla GPT-2 architecture rather than a Sudoku-specific network.
Novelty
Unlike direct board prediction and prior GPT-style imitation of seven handcrafted strategies, this work teaches a decoder-only Transformer a closed loop of rules, guessing, verification, and backtracking. Its further novelty is to treat guess minimization as contextual MIN-SUM SET COVER and train on successful trajectories only, emphasizing decisions that lead directly to solutions.
Limitations
- The main evidence concerns 9×9 Sudoku and 1-in-3 SAT. The 99.8% depth-1 result depends on the random Sudoku distribution and the prevalence of backdoors; it does not establish comparable efficiency for large arbitrary NP instances.
- DFS can still grow exponentially as the search tree expands. Errors, maximum sequence length, and verifier design can cause failure, and the paper provides no polynomial-time guarantee or large industrial benchmark.
Future Work
Future research should test larger Sudoku, SAT, Clique, and TSP instances; combine multi-level guessing with adaptive memory; and compare model scale, search policies, and losses. A unified streaming benchmark for verifier-backed NP reasoning would clarify transfer, cost, and robustness.
AI Executive Summary
Large language models excel at language but often fail on Sudoku, SAT, TSP, and even arithmetic. In the paper’s 9×9 Sudoku test, GPT-4o, Gemini-1.5 Pro, o3 mini, Gemini-2.5 Flash, and DeepSeek-R1 all achieved 0% board accuracy. Once these systems make an invalid inference, they generally cannot locate the mistake and restart reliably.
Giannoulis, Pantis, and Tzamos propose efficient trial and error. A 42M-parameter vanilla GPT-2 first learns four elementary Sudoku rules. When propagation stops, it makes an informed guess; a verifier checks the resulting state, and DPLL-like DFS backtracking replaces guesses that lead to dead ends. Compact action tokens and multi-target loss teach the model that several next actions may be valid. The system reaches about 99% on 100K random Sudoku puzzles and 99% on 1-in-3 SAT.
The authors also frame guess minimization as contextual MIN-SUM SET COVER. Under depth-1 guessing, about 99.8% of generated Sudoku boards can be completed after one correct guess. The broader contribution is not a claim that Transformers make NP problems easy, but a demonstration that neural generation can be coupled to verification and reversible search. Its efficiency remains dependent on instance distribution, verifier cost, and limited search depth.
Deep Analysis
Background
LLMs learn next-token prediction, but combinatorial tasks require exact constraint maintenance. Earlier Sudoku systems used Hopfield Networks, Recurrent Relational Networks, Recurrent Transformers, or Masked Diffusion Models. SDWP24 trained a GPT-style model to imitate seven human strategies, yet direct generation and error-free transcripts offered limited recovery. This paper instead treats reasoning as candidate generation followed by verification and backtracking.
Core Problem
The goal is to make an ordinary decoder-only Transformer solve NP-style tasks without external tools. The challenges are that several next actions may be valid, simple rules may stall, wrong guesses must be detected and undone, and search length—not merely final accuracy—should be minimized.
Innovation
The method uses four basic rules and lets DFS handle residual difficulty rather than encoding seven complex heuristics. A single three-digit token represents (r,c,v), reducing sequence length by about threefold. Multi-target supervision labels every valid continuation. Finally, one-level non-adaptive guessing is formulated as contextual MIN-SUM SET COVER, motivating a loss aligned with solution length.
Methodology
- �� Input givens are followed by a start token.
- �� The model emits rule-resolvable moves until it outputs rules-end.
- �� It selects a guess level and a candidate value.
- �� A verifier checks row, column, box, and partial-assignment constraints.
- �� A dead end causes backtracking to the latest guess level and selection of another value.
- �� Training uses −∑_{i∈S}log p_i for valid action set S; inference takes each cell’s last assignment.
Experiments
The GPT-2 variant has 8 layers, 8 attention heads, 576-dimensional embeddings, a 3456-dimensional feed-forward layer, and 42M parameters. Tests use 100K Random puzzles, Kaggle unfiltered, Kaggle filtered, and RRN datasets, with comparisons to RRN, Recurrent Transformer, Causal Transformer, and MDM methods. Ablations compare triplet versus action-level tokens and single- versus multi-target loss; 1-in-3 SAT and depth-1 guessing are also evaluated.
Results
The full system reaches about 99% on Sudoku and 99% on 1-in-3 SAT. Figure 1 places it near 99%, above several neural baselines. Random-generator training tracks Kaggle performance and transfers strongly to RRN. Ablations show that compact action encoding plus multi-target supervision accelerates rule learning. Approximately 99.8% of random Sudoku boards contain a one-guess backdoor.
Applications
The framework could support SAT solving, constraint scheduling, combinatorial design, routing, and game planning whenever candidate solutions can be efficiently verified. In deployment, the Transformer can rank or propose actions while a symbolic verifier acts as a safety gate, improving auditability over unconstrained generation.
Limitations & Outlook
Sudoku is small and its distribution is controlled by a principled generator; the 99.8% one-guess result should not be generalized to arbitrary NP instances. DFS can remain exponential, while model errors and sequence limits create failures. The 1-in-3 SAT experiment supports transfer, but large-scale SAT, TSP, and industrial cost advantages remain unestablished.
Plain Language Accessible to non-experts
Imagine a student solving a Sudoku with a teacher beside them. First, the student uses simple classroom rules: if a square has only one possible number, fill it; if a number has only one place in a row, column, or small block, place it. When these rules stop working, the student makes a careful trial.
The important part is that a trial is never treated as permanent truth. After every move, the teacher checks whether any row, column, or block has become impossible. If a contradiction appears, the student returns to the latest trial, erases it, and tries another option. This is organized trial and error rather than random guessing.
The model is trained to recognize all moves that are acceptable at a moment, not just one teacher-selected move. On 100,000 random Sudoku puzzles, this ordinary GPT-2-style system solves about 99% of boards. Around 99.8% need only one successful trial after simple rules. The lesson is that a language model becomes much more reliable when generation is connected to checking and reversible decisions.
ELI14 Explained like you're 14
Think of an AI playing a Sudoku game. A normal chatbot is like a fast player who keeps talking but never saves the game. If it puts one wrong number in the grid, everything afterward may look confident but become nonsense. This paper gives the player save points and a referee.
The AI first uses easy clues. If it gets stuck, it picks a possible number and tries it. After each move, the referee checks the rows, columns, and boxes. If the move creates a contradiction, the AI jumps back to the last save point and tries a different number. That is DFS backtracking: explore one route, then rewind when the route fails!
The researchers also teach the AI that more than one move can be correct at the same time. Their 42M-parameter GPT-2 variant solves about 99% of 100K random Sudoku boards, and it gets 99% on 1-in-3 SAT. About 99.8% of random Sudoku boards need only one good guess.
Does this mean AI has conquered every hard problem? Not at all! Bigger puzzles can create gigantic numbers of possible routes, like a game map with millions of branching paths. The exciting idea is that the AI is not merely guessing answers: it is learning to try, check, undo, and try again.
Glossary
Depth-First Search (DFS)
A search procedure that follows one candidate path as deeply as possible before returning to the latest branch point. It systematically explores alternatives through backtracking.
Used after rule propagation when guesses and dead ends must be explored.
Verifier
A procedure that quickly checks whether a partial or complete candidate satisfies the problem constraints. It validates solutions rather than discovering them.
Checks Sudoku rows, columns, boxes, and SAT assignments.
Backdoor
A strategically useful guess after which simple rules complete the instance. The term denotes a search shortcut, not a security vulnerability.
About 99.8% of generated Sudoku boards have a one-guess backdoor.
Multiple-target loss
A training objective that increases probability for every valid next action when several continuations are acceptable. Here it is −∑_{i∈S}log p_i.
Applied during rule propagation to exploit multiple legal moves.
MIN-SUM SET COVER
An optimization framework that minimizes expected cost while covering relevant targets. The paper interprets guesses as context-dependent sets covering possible solution paths.
Used to derive a loss directly related to solution length.
Open Questions Unanswered questions from this research
- 1 It remains unknown whether multi-level guessing and memory can preserve the advantage on large SAT, TSP, or scheduling instances. Progress needs theory, realistic distributions, and industrial-scale benchmarks.
- 2 Verifier construction may be expensive or problem-specific. Automatically learning reliable verifiers while preserving soundness is an open research problem.
Applications
Immediate Applications
Constraint-planning assistants
Organizations could use the model for scheduling, resource allocation, or configuration generation. The Transformer proposes actions, a verifier rejects violations, and DFS revises failed choices. The prerequisite is a programmable constraint checker; the expected benefit is auditable search rather than unconstrained text generation.
SAT and reasoning evaluation
Researchers can train candidate generators on 1-in-3 SAT transcripts and place a logical verifier in the loop. This provides a controlled test of whether a neural model respects constraints, rather than merely producing plausible-looking explanations.
Long-term Vision
Verified neural search platform
A common Transformer framework could handle SAT, Clique, TSP, and scheduling by swapping in task-specific verifiers. Major obstacles are branching complexity, verification cost, representation transfer, and reliable scaling; meaningful deployment is likely a multi-year research direction.
Abstract
Despite their proficiency in various language tasks, Large Language Models (LLMs) struggle with combinatorial problems like Satisfiability, Traveling Salesman Problem, or even basic arithmetic. We address this gap through a novel trial & error approach for solving problems in the class NP, where candidate solutions are iteratively generated and efficiently validated using verifiers. We focus on the paradigmatic task of Sudoku and achieve state-of-the-art accuracy (99%) compared to prior neuro-symbolic approaches. Unlike prior work that used custom architectures, our method employs a vanilla decoder-only Transformer (GPT-2) without external tools or function calling. Our method integrates imitation learning of simple Sudoku rules with an explicit Depth-First Search (DFS) exploration strategy involving informed guessing and backtracking. Moving beyond imitation learning, we seek to minimize the number of guesses until reaching a solution. This is achieved using depth-1 guessing, showing empirically that almost all Sudoku can be solved using the puzzle's rules with at most one guess. We provide a rigorous analysis of this setup formalizing its connection to a contextual variant of Min-Sum Set Cover, a well-studied problem in algorithms and stochastic optimization.