💬 NLP

Explaining Puzzle Solutions in Natural Language: An Exploratory Study on 6x6 Sudoku

This exploratory study evaluates five Large Language Models on 6x6 Sudoku puzzles and finds that while one model shows limited solving capability, none can provide explanations reflecting strategic reasoning or intuitive problem-solving, highlighting significant barriers to effective human-AI collaborative decision-making.

Original authors: Anirudh Maiya, Razan Alghamdi, Maria Leonor Pacheco, Ashutosh Trivedi, Fabio Somenzi

Published 2026-04-28

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Anirudh Maiya, Razan Alghamdi, Maria Leonor Pacheco, Ashutosh Trivedi, Fabio Somenzi

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a team of very smart, well-read robots. You ask them to solve a logic puzzle called Sudoku (specifically a smaller 6×6 version) and, more importantly, to teach you how they solved it in plain English.

This paper is like a report card for five of these robots, checking two things:

Did they get the right answer?
Could they explain their thinking in a way that actually makes sense to a human?

Here is the breakdown of what the researchers found, using some everyday analogies.

The Setup: The "Sudoku Test"

The researchers created nearly 2,300 of these 6×6 puzzles. Think of these puzzles as a gym for the brain. They aren't the hardest puzzles in the world (like the 9×9 version), but they are tricky enough that you can't just guess; you have to use logic and rules to figure out where numbers go.

They wanted to see if Large Language Models (LLMs)—the AI brains behind chatbots—could act like a good tutor. A good tutor doesn't just give you the answer key; they walk you through the steps so you understand why a move was made.

The Results: The "Solvers" vs. The "Explainers"

1. The Open-Source Robots (The "Amateur Hour")

The researchers tested four different open-source models (like Llama, Gemma, and Mistral).

The Result: These robots basically failed the test. Out of 2,293 puzzles, they got the entire puzzle correct less than 1% of the time.
The Analogy: Imagine asking a group of people to fill out a crossword puzzle. These robots were like people who guessed random words. They might get a few letters right by chance, but they couldn't keep the whole picture consistent. They forgot the rules as soon as they started writing.

2. The Star Student: OpenAI's "o1-preview"

Then there was one specific model from OpenAI called o1-preview.

The Result: This model was a star at solving. It got the full puzzle right about 65% of the time. On the easier puzzles, it was perfect (100%).
The Catch: As the puzzles got harder (the "Diabolical" level), its performance dropped. It started making mistakes, like a student who is great at math homework but gets confused when the test gets really tough.

3. The Real Problem: The "Bad Explainer"

Here is where the study gets interesting. The researchers took the 20 puzzles that o1-preview solved correctly and asked it to explain its steps to human experts.

The Result: The explanation was a disaster.
- Justification: Only 5% of the time did the robot actually explain why it picked a number. Most of the time, it just said, "I put a 5 here," without saying why.
- Clarity: The explanations were confusing, jumping around, and using terms incorrectly.
- Educational Value: If you were trying to learn how to solve Sudoku from this robot, you would learn nothing. It didn't teach any strategies.
The Analogy: Imagine a master chef who can cook a perfect steak. You ask them, "How did you do that?"
- A good explanation: "I seared it at high heat for two minutes, then lowered the temperature..."
- What o1-preview did: It handed you the steak and said, "It's done. It's good. Here is the steak." It gave you the result but refused to (or couldn't) share the recipe. It was like a magician who performs a trick perfectly but, when asked how, just says, "I just did it," and then makes up a fake reason that doesn't match what actually happened.

The Big Takeaway

The paper concludes that while AI is getting better at doing the work (solving the puzzle), it is still terrible at telling the story of how it did the work.

The authors argue that for AI to be a true partner to humans—especially in important jobs like medicine or law—it needs to be able to show its work clearly. Right now, even the smartest AI is like a student who gets an 'A' on the test but can't explain the answer to the teacher.

What's Next?

The paper suggests that instead of trying to make the AI "think" like a human entirely on its own, we should combine AI with logic tools (like specialized math software).

The Idea: Let the logic software do the hard, strict math to ensure the answer is 100% correct. Then, let the AI act as the translator, taking that strict, boring math and turning it into a friendly, easy-to-understand story for a human.

In short: The AI can solve the puzzle, but it can't yet teach you how to solve it. It's a great worker, but a terrible teacher.

1. Problem Statement

The paper addresses a critical gap in the deployment of Large Language Models (LLMs) for human-AI collaborative decision-making. While LLMs have shown success in language generation, their ability to perform structured, multi-step reasoning and, more importantly, provide trustworthy, faithful, and tailored explanations for their reasoning processes remains unproven.

The authors argue that in high-stakes domains (e.g., medical, legal, safety-critical systems), the explanation of a decision is often more valuable than the decision itself. Current LLMs often generate correct answers but fail to articulate the deductive steps taken to reach them, or they provide explanations that are hallucinated, inconsistent, or lack strategic insight. The paper uses 6×6 Sudoku as a controlled, risk-free benchmark to isolate and evaluate these reasoning and explanation capabilities without the risks associated with real-world critical errors.

2. Methodology

Dataset Construction

Generation: The authors generated a dataset of 2,293 unique 6×6 Sudoku puzzles using the Z3 SMT solver.
Constraints: Each puzzle ensures that every row, column, and 2×3 box contains numbers 1–6 without repetition.
Minimality & Uniqueness: Puzzles were generated by removing clues from a solved grid until the solution became non-unique, ensuring every puzzle has exactly one solution and is minimal (removing any clue creates multiple solutions).
Difficulty Distribution: Puzzles were rated using the Explainer Rating (ER) system, covering five difficulty levels: Easy (1.0–1.2), Medium (1.5), Hard (1.7–2.5), Fiendish (2.6–6.0), and Diabolical (6.2+). Approximately 93.5% of the dataset consists of Easy or Medium puzzles.
Validation: The ER ratings were validated against human ratings by two authors, yielding a Spearman's Rank Correlation Coefficient ( $\rho$ ) of 0.87, confirming the metric's alignment with human perception of difficulty.

Experimental Setup

The study evaluated five LLMs:

Open-source models: Llama-3.1-70B-Instruct, Llama-3.1-8B-Instruct, Gemma-2-9B-Instruct, and Mistral-7B-Instruct-v0.3.
Proprietary model: OpenAI's o1-preview.

Evaluation Tasks:

Solving Capability: Models were tested on the full dataset (2,293 puzzles) for open-source models and a random subset of 100 puzzles for all models (including o1-preview). Accuracy was measured at multiple granularities: cell-wise, row-wise, column-wise, box-wise, and fully correct solutions.
Explanation Capability: A subset of 20 puzzles (spanning various difficulties) was selected for o1-preview. Three expert evaluators assessed the explanations using a structured survey based on a 3-point Likert scale (Yes, Maybe, No) across three dimensions:
- Justification: Does the explanation logically support the solution?
- Clarity: Is the explanation easy to follow and detailed?
- Educational Value: Does it convey generalizable solving strategies?

3. Key Results

Solving Performance

Open-Source Models: Performed poorly across the board. Even the largest model (Llama-3.1-70B) achieved 0.04% fully correct solutions on the full dataset. They struggled to integrate global constraints (rows/columns/boxes), often satisfying only 7% of row/column constraints despite placing ~40-50% of individual cells correctly.
OpenAI o1-preview: Significantly outperformed open-source models. On the 100-puzzle subset, it achieved 59% fully correct solutions.
- Difficulty Sensitivity: o1-preview achieved 100% accuracy on Easy/Medium puzzles but performance degraded significantly on Diabolical puzzles (ER 6.2+), dropping to 40% full accuracy and 57.2% cell-wise accuracy.

Explanation Performance (o1-preview)

Despite solving 65% of the 20-puzzle subset correctly, the explanation quality was critically low:

Justification: Only 5% of explanations received a "Yes" rating. The model rarely justified why a specific digit placement was chosen, often stating the result without the deductive chain.
Clarity: Only 7.5% "Yes" ratings. Evaluators noted issues with logical progression and inconsistent terminology.
Educational Value: The weakest dimension with only 2.5% "Yes" ratings. Explanations failed to teach generalizable strategies.
Qualitative Feedback: Evaluators consistently noted that explanations lacked systematic progression, misused basic Sudoku terminology, and failed to articulate the solution path, often appearing as "post-hoc rationalizations" rather than genuine reasoning traces.

4. Key Contributions

Empirical Evidence of the "Explanation Gap": The study provides concrete data showing that while LLMs (specifically o1-preview) are making strides in solving logical puzzles, they are currently incapable of providing faithful, strategic, and educational explanations for their solutions.
Benchmarking Framework: The creation of a 2,293-puzzle 6×6 Sudoku dataset with verified uniqueness and difficulty ratings (ER) provides a standardized benchmark for future reasoning research.
Human-AI Collaboration Insight: The findings highlight that for LLMs to be effective partners in decision-making, they must move beyond "black box" correctness to transparent reasoning. The current inability to explain how a solution was derived undermines trust.
Research Agenda: The authors propose a hybrid approach combining LLMs with logic-based reasoning tools (e.g., SMT solvers like Z3, proof assistants like Lean/Isabelle). The vision is for symbolic solvers to handle the rigorous deduction and for LLMs to translate these formal proofs into natural language explanations accessible to non-experts.

5. Significance and Limitations

Significance: The paper challenges the assumption that improved reasoning capabilities in LLMs automatically translate to better explainability. It suggests that "reasoning" in LLMs may currently be a form of pattern matching or probabilistic guessing rather than true deductive logic, especially when required to articulate the process.
Limitations:
- Dataset Scope: The explanation evaluation was limited to 20 puzzles, though the consistency of failure suggests a systemic issue.
- Puzzle Complexity: 6×6 Sudoku is simpler than standard 9×9 puzzles; the models might struggle even more with higher complexity, or conversely, the 6×6 grid might not fully stress-test the limits of complex reasoning.
- Fine-Tuning: The study evaluated models "out-of-the-box." It is possible that fine-tuning on reasoning tasks could improve performance, though the disconnect between solving and explaining remains the core focus.

Conclusion: The paper concludes that while LLMs are becoming competent solvers for constrained logic problems, they are not yet reliable explainers. Bridging this gap requires integrating LLMs with formal reasoning systems to ensure explanations are both logically sound and human-interpretable.