Explaining Puzzle Solutions in Natural Language: An Exploratory Study on × 𝟔 \bm{6\!\times\!6} Sudoku

Anirudh Maiya Razan Alghamdi · 2025

Read Explaining Puzzle Solutions in Natural Language: An Exploratory Study on × 𝟔 \bm{6\!\times\!6} Sudoku by Anirudh Maiya Razan Alghamdi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-15993.txt.

Introduction

Anirudh Maiya and co-authors test whether large language models can explain how to solve a Sudoku puzzle, not solve it. They use a six-by-six version of the puzzle. Clear explanations matter when people and AI systems make decisions together, since a bare answer gives the partner little to check.

The team evaluated five language models on solving and explaining these puzzles. One model managed limited success at finding solutions. None of the five could explain a solution in a way that showed strategy or human-like insight. Their explanations failed to mirror the step-by-step reasoning a teacher would give. The authors say this gap must close before models can act as trusted partners in joint decisions. Puzzle solving offers a clean test bed for that problem, because every step of an explanation can be checked against the rules of the game.

Catalog record

CREATORAnirudh Maiya Razan Alghamdi
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE25 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-15993

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Explaining Puzzle Solutions in Natural Language: An Exploratory Study on × 𝟔 \bm{6\!\times\!6} Sudoku Anirudh Maiya Razan Alghamdi Abstract The success of Large Language Models (LLMs) in human-AI collaborative decision-making hinges on their ability to provide trustworthy, gradual, and tailored explanations. Solving complex puzzles, such as Sudoku, offers a canonical example of this collaboration, where clear and customized explanations often hold greater importance than the final solution. In this study, we evaluate the performance of five LLMs in solving and explaining × 6 6\!\times\!6 Sudoku puzzles. While one LLM demonstrates limited success in solving puzzles, none can explain the solution process in a manner that reflects strategic reasoning or intuitive problem-solving. These findings underscore significant challenges that must be addressed before LLMs can become effective partners in human-AI collaborative decision-making. 1 Introduction The recent success of Large Language Models (LLMs) in automating reasoning tasks using natural language highlights their potential in human-AI collaborative decision-support systems. However, their effectiveness in critical domains—such as safety-critical systems, legally sensitive decision-making, medical support systems, and business-critical processes—depends on their ability to provide step-by-step, consistent, and trustworthy explanations tailored to the prior knowledge and current capabilities of the human partner. Solving complex, multi-step puzzles like Sudoku offers a meaningful example of such decision-making scenarios. These puzzles share several key challenges—including step-by-step reasoning, the need for tailored explanations, and the importance of maintaining consistency—but without the risks associated with making incorrect critical decisions. Sudoku thus provides a controlled environment to study the capabilities of LLMs in addressing these challenges while isolating them from high-stakes consequences. This paper explores whether LLMs can effectively navigate these decision-making challenges by focusing on their performance in solving and explaining Sudoku problems. The ability of LLMs to reason and solve problems has become a key area of interest in the field of artificial intelligence Huang and Chang 2023 ; Yin et al. 2024 . Although LLMs have shown remarkable performance in tasks involving language generation, translation, and comprehension Brown et al. 2020 ; Wei et al. 2024 , their ability to handle more structured reasoning tasks is less understood Mirzadeh et al. 2024 . In the last year, several studies have attempted to test the abilities of LLMs to solve complex puzzles Chia et al. 2024 ; Li et al. 2024 ; Giadikiaroglou et al. 2024a . While these models are increasingly capable of generating correct answers, the explanations they provide for their reasoning process often fall short Turpin et al. 2024 . We argue that good reasoners should be able to clearly expose their deductive processes. Therefore, reasoning explanations should be faithful, provide enough support for individual decisions, and provide insight into the process they took to arrive at any given solution. While we can obtain correct answers and faithful reasoning steps for many puzzles with symbolic reasoners de Moura and Bjørner 2011 , it can be hard for humans to make sense of the explanations provided by these tools. These explanations usually come in the form of fine-grained proofs that require a good grasp of proof terminology and are often overwhelmingly detailed. They often refer to encodings of the problem that are cumbersome to relate to the original presentation of the puzzle. To be useful in practical scenarios, explanations need to be easily understandable to humans Gilpin et al. 2018 . Given that LLMs excel at producing human-like output Ouyang et al. 2022 , we are interested in studying the challenges and opportunities of LLMs for explaining puzzles solutions. Research Questions and Findings We investigate the explanation capabilities of LLMs in the context of 6\!\times\!6 Sudoku puzzles. Sudoku is a widely recognized logic-based puzzle Rosenhouse and Taalman 2011 , which provides an ideal benchmark to explore these facets of LLMs. Solving Sudoku requires deductive reasoning and rule-based elimination, skills that go beyond simple pattern recognition. We choose 6\!\times\!6 Sudoku because, while not being overly difficult, it often requires a few nontrivial reasoning steps to be solved. With our study, we aim to answer the following two research questions: (1) LLMs solve 6\!\times\!6 Sudoku puzzles? (2) Can LLMs successfully explain the steps needed to arrive to a given solution? To answer these questions, we construct a dataset of 2,293 6\!\times\!6 Sudoku puzzles with their solutions, and show that open-source models can correctly solve less than 1% of the puzzles, while the latest Open AI model can solve 65% of them. Then, select a subset of 20 puzzles spanning different difficulty levels to evaluate explanation capabilities using a structured survey, and show that explanations fall short for the best performing models. Contributions This study contributes to a deeper understanding of the (in)ability of LLMs to articulate the reasoning steps needed to explain a particular solution to multi-step reasoning tasks. We show that while these tools show promise (as evidenced by the increase performance for newer models), they still have significant challenges in exposing reasoning steps in a way that is both faithful and insightful. Finally, we outline a research agenda for combining LLMs with logic-based reasoning to address some of these challenges 1 1 1 All data and code will be released. . 2 Related Work The challenges that LLMs face in solving puzzles that require complex reasoning have been well-documented Giadikiaroglou et al. 2024b , with most methods struggling to successfully produce consistent results. In response to these challenges, methods that combine symbolic reasoning and LLMs have recently received attention with varying success Mittal et al. 2024 ; Jiang et al. 2022 ; Xin et al. 2024 . PuzzleLM Mittal et al. 2024 first prompts an LLM to generate an instance-agnostic program capable of handling various problem classes, such as Sudoku, N-Queens, graph coloring, etc. The program then converts the problem instance into SMT constraints and passes them to an external solver like Z3. The solver processes these constraints and returns a solution, which the program then converts to the desired output format. Xin et al. 2024 introduces a method for generating large-scale formal proof data from informal math problems. It fine-tunes an LLM, translates informal problems into formal Lean 4 statements, filters low-quality formalizations using a chain-of-thought evaluation, and attempts to prove both the formal statement and its negation. This iterative process refines the model’s performance by incorporating newly generated data to enhance subsequent rounds of statement generation. However, significant less attention has been given to the problem of whether LLMs can produce useful explanations (in form of reasoning steps) for the solutions that they provide. In this work, we study this question in the context of 6x6 sudoku and show that, while LLMs have improved their capacity of producing correct solutions, generating explanations continues to be challenging. 3 Task Formulation This study assesses the problem-solving capabilities of LLMs using 6\!\times\!6 Sudoku puzzles. We evaluate two key aspects: first, the ability of LLMs to generate correct solutions for puzzles of varying difficulty, and second, their capability to provide meaningful explanations for how these solutions are derived. These complementary tasks allow us to assess both the computational accuracy and reasoning transparency of LLMs in structured problem-solving scenarios. Dataset We generated 2,293 6\!\times\!6 Sudoku puzzles using the Z3 solver. Z3 decides the satisfiability of sentences of many decidable fragments of first-order

Read the complete text