Modern AI Cannot Solve Sudoku: An Analysis of the Limits of Statistical Induction and the Neuro-Symbolic Future

1 Introduction

Today, artificial intelligences (AI), and more specifically large language models (LLMs), have taken a substantial place in our activities. They become a real asset when we ask questions, from literature to mathematics, philosophy, computer science, and many other academic, artistic or industrial fields (Colelough and Regli 2025). As a reminder, these AIs serve as decision-support tools; they must not make us lose our critical thinking in the face of their suggestions.

The purpose of this article is to recall the limits of these tools through a simple and striking example: Sudoku. In what follows, we argue that this puzzle, among many other logic puzzles, requires a chain of rigorous and deep deductions to be solved. We will see that, faced with this problem, modern AIs still struggle to find a reliable solution (Giadikiaroglou et al. 2024; Defresne et al. 2025). Of course, some will object that these AIs are also capable of recovering the solving algorithm, and they are. The point is elsewhere: if we present the machine with a novel problem, without it having the formal methods to solve it, what will it hallucinate and confidently return to us?

To offer a few perspectives and avenues aligned with the state of the art, we will first sketch a reminder of how AI has evolved over time by describing the emergence of its different paradigms (Section 2.1). In a second step, we will see how to categorize them through the logical tools we use as humans (Section 2.2). We will end by explaining why current AIs – the LLMs – fail to solve Sudoku (Section 3), and toward which paradigms we might move to address these shortcomings (Section 4.1).

2 Background

2.1 Brief History of the Symbolic and Connectionist Paradigms

In the broad history of AI, we focus here on the introduction, in broad strokes, of the symbolic and connectionist paradigms. Many myths and formal theories predate this introduction: one can mention the Golem myth as an early form of AI prototyping (Vudka 2020), or the foundations of computing laid by Alan Turing, often presented as one of the fathers of the field and of the famous Turing test (Saygin and Çiçekli 2000). This test aims to determine whether a machine reaches a level of cognition comparable to that of a human by confronting a person with an entity (human or machine) under blind conditions. This method is now widely discussed and calls for a renewal of the definitions of intelligence and consciousness (Wang et al. 2024).

During the 1950s-1980s, research focused particularly on the symbolic paradigm. Symbolism postulates that symbols – representing objects in the world – are the fundamental units of human intelligence. The cognitive process can then be described as a manipulation of symbols, through a series of rules and logical operations. This paradigm has several virtues: it requires few examples, offers declarative languages to represent knowledge, and its internal processes are conceptually clear. But like any formal language, it runs into limits, notably its fragility in the face of noise and ambiguity. Added to this is its lack of autonomy (for example, the rules must be provided by an expert) (Wang et al. 2022).

Faced with this impasse, the late 1980s marked a shift toward the connectionist paradigm. Inspired by the physiology of the nervous system, connectionism represents cognition through the interconnection of networks of small, simple, and uniform units: neurons. Learning occurs through the modification of the weights associated with these neurons, based on examples drawn from the real world. This paradigm is more tolerant of noise, extracts concepts, and generalizes from training sets. It is particularly effective in vision and, as we see today, in language. Its limits nonetheless appear in the massive amount of data required to learn, as well as in a generalization that is sometimes not very abstract. Finally, this paradigm suffers from its black box effect: it is difficult to observe and explain its reasoning process (Wang et al. 2022). In Section 3, we will see how these limits manifest themselves.

Given the respective limits of symbolism (rigidity, learning difficulty) and connectionism (lack of explainability, weakness in logical reasoning), a new field emerged in the 1990s: neuro-symbolic AI. This paradigm aims to combine statistical learning and logical reasoning to take advantage of the best of both worlds. (Wang et al. 2022) In Section 4.1, we observe that the current trend in research could once again converge toward this vision.

2.2 Link With the Field of Logic

Before studying the Sudoku problem, we want to clarify the previous definitions of the symbolic and connectionist paradigms by linking them to precise logical mechanisms.

Induction and deduction (Bergman et al. 2011) are three fundamental mechanisms used in logic, philosophy of science, artificial intelligence, and scientific research. Each has a distinct logical structure and plays a specific role in knowledge construction.

2.2.1 Deduction

Definition – Deduction is a form of reasoning that goes from the general to the particular: if the premises are true, the conclusion is necessarily true. Deduction is also said to follow a syllogistic structure.

Let us revisit a classic example from logic, with this syllogism inviting Socrates into the world of mortals. From the premises all men are mortal and Socrates is a man, deductive logic leads to the conclusion Socrates is mortal.

flowchart LR
  A["All men are mortal"] --> P{"Deduction"}
  B["Socrates is a man"] --> P
  P --> C["Socrates is mortal"]

Figure 1: Deduction graph (from the general to the particular)

2.2.2 Induction

Definition – Induction consists in inferring a general rule from repeated particular observations. Induction goes from the particular to the general, but it does not provide absolute certainty; its strength increases with the number of agreeing observations.

Taking the previous example, we may start from the observations: “Socrates is mortal”, “Plato is mortal”, …, “Andreas is mortal”; induction would therefore propose that “all men are mortal”.

flowchart LR
  A["Socrates is mortal"] --> P{"Induction"}
  B["Plato is mortal"] --> P
  C["..."] --> P
  D["Andreas is mortal"] --> P
  P --> E["All men are mortal"]

Figure 2: Induction graph (from the particular to the general)

In the context of Sudoku, a solution mainly requires a rigorous deductive chain – something symbolic solvers master perfectly, but which still largely eludes current LLMs, which are much closer to an inductive logic (Giadikiaroglou et al. 2024; Defresne et al. 2025). In the rest of this article, we test this observation (see Section 3) and revisit the terms defined in this section.

3 Experimenting With the Sudoku Problem

The experiments proposed here remain modest, but they provide an additional truth value to the more exhaustive work we cite later. These examples also invite the reader to copy the prompts in question and test for themselves whether their preferred LLM is capable, or not, of solving this problem. Before diving into the experiments we conducted, let us recall what the Sudoku problem is and the difference we make between a problem and an instance of the problem.

Sudoku is a logic-based numerical combinatorial puzzle. In the classic Sudoku, the goal is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 subgrids that make up the grid (also called “boxes”, “blocks”, or “regions”) contains all digits from 1 to 9. The puzzle author provides a partially filled grid which, for a well-posed puzzle, has a unique solution.¹

Thus, the problem of Sudoku corresponds to this generic definition, whereas a Sudoku instance corresponds to a pre-filled grid that always leads to one and only one solution. The Sudoku problem encompasses all possible instances. Not all Sudoku instances have the same level of complexity²: some require advanced techniques to be solved (for example, the difficult instance presented in Section 3.2 requires the application of techniques such as X-Wing or Y-Wing; see the study (Qi et al. 2019)).

It is important to make clear to the reader that solving a Sudoku instance is different from knowing how to solve the Sudoku problem generically.

The experiments carried out at the scale of this study remain limited: we focus on two instances of the Sudoku problem, the first simple and the second difficult. We then rely on a study (Seely et al. 2025) that proposes broader experiments on this problem.

3.1 Solving a Simple Sudoku Instance

For this first instance, described as simple, the techniques used to solve it do not require great operational complexity: for each empty cell, it is enough to cross the three constraints that govern its value (different values in the row, column, and 3×3 submatrix) to find, for one of them, a single possible value. And so on, until the puzzle is complete. Although the method may seem simple, it still requires many back-and-forths in reading the Sudoku grid.

Let us now look at the results obtained with two LLMs commonly used by the general public: ChatGPT (the free version) and Gemini (split into Gemini 3 Fast and Gemini 3 Pro). Figure 3 shows the results obtained.

. 1 8 | . . . | . 7 .
. 7 . | . . 1 | 9 . .
. 6 . | 8 5 . | 1 2 .
------+-------+------
6 . . | 7 . . | 3 . .
7 . . | 5 1 . | . 8 .
8 . 4 | . . 9 | 7 . 5
------+-------+------
. 4 7 | . 9 8 | . 5 .
. . 2 | 6 . 5 | . 3 .
. . 6 | . . . | 2 4 .

(a) Prompt proposed to the LLMs

 

2 1 8 | 9 6 3 | 5 7 4
5 7 3 | 2 4 1 | 9 6 8
4 6 9 | 8 5 7 | 1 2 3
------+-------+------
6 5 1 | 7 8 4 | 3 9 2
7 9 3 | 5 1 2 | 4 8 6
8 2 4 | 3 6 9 | 7 1 5
------+-------+------
3 4 7 | 1 9 8 | 6 5 2
1 8 2 | 6 7 5 | 4 3 9
9 3 6 | 4 2* 1 | 2* 4 7

(b) Response from Gemini 3 Fast. Problem\(^{*}\): two ‘2’ in the last line.

4 1 8 | 9 2 6 | 5 7 3
2 7 5 | 4 3 1 | 9 6 8
9 6 3 | 8 5 7 | 1 2 4
------+-------+------
6 5 1 | 7 8 4 | 3 9 2
7 3 9 | 5 1 2 | 4 8 6
8 2 4 | 3 6 9 | 7 1 5
------+-------+------
3 4 7 | 2 9 8 | 6 5 1
1 9 2 | 6 4 5 | 8 3 7
5 8 6 | 1 7 3 | 2 4 9

(c) Response from Gemini 3 Pro (reasoning). Correct.

 

5 1 8 | 9 2 4 | 6 7 3
2 7 3 | 4 6 1 | 9 0* 8
. . . | . . . | . . .
------+-------+------
. . . | . . . | . . .
. . . | . . . | . . .
. . . | . . . | . . .
------+-------+------
. . . | . . . | . . .
. . . | . . . | . . .
. . . | . . . | . . .

(d) Response from ChatGPT. Problem\(^{*}\): put ‘0’ and then gives up.

Figure 3: Solving a Simple Sudoku With Different LLMs

The first grid (Figure 3 (a)) represents a Sudoku instance to be completed, as it was presented to the three LLMs queried in the following form:

Solve this Sudoku instance:
<grid>

We first focus on the simplest models in our tests. Figure 3 (b) shows the result of the experiment with Gemini 3 Fast. This first response ends in failure: the tested LLM confidently returns an incorrect grid whose last row contains two duplicated values. Figure 3 (d) shows the result of the test with ChatGPT. This also leads to an incorrect grid, but the prompt responses show a certain humility regarding the produced results: ChatGPT itself states that this is not the kind of problem it can solve. In its response, it even stops writing the grid when a 0 is encountered.

One of the most advanced models in Google’s public (and paid) offering, under the name Gemini 3 Pro, changes the outcome of the tests. Indeed, this model is capable of reasoning. This reasoning must be put back into context: it is an iterative process of inductive reasoning, as the nature of LLMs requires. It is thanks to this iterative behavior that it can propose answers with a higher probability of being true. In Figure 3 (c), Gemini 3 Pro shows its ability to correctly fill in the simple Sudoku instance we proposed. We can observe, in its reasoning trace, that it uses this iterative process of trial and error until it reaches the correct solution to this grid.

This first test is interesting and, although it shows the inefficiency of simple models on this Sudoku instance, more advanced models manage to solve it. In the next part, we will see what happens to this advanced model when we submit a difficult instance of the Sudoku problem.

3.2 Solving a Difficult Sudoku Instance

As noted earlier, this difficult Sudoku instance requires advanced techniques to be solved (Y-Wing (Qi et al. 2019)) and therefore involves more complex reasoning. For this final step in our experiments, we assess how Gemini 3 Pro solves this Sudoku grid (Figure 4 (a)).

. . . | . 3 . | . . 6
. 1 . | . 5 . | . . .
. . . | . . 9 | 4 . 3
------+-------+------
8 . . | . . . | 5 . .
. . 4 | . . 2 | 1 . 7
6 . 5 | . . . | . . 4
------+-------+------
1 . 9 | 3 . . | . . .
. . . | . 4 . | . 3 .
4 . 2 | . 8 1 | . . .

(a) Prompt proposed

7 4 8 | 2 3 1 | 9 5 6
2 1 3 | 8 5 6 | 7 4 9
5 9 6 | 7 2 9 | 4 1 3
------+-------+------
8 2 1 | 4 6 7 | 5 9 3
3 9 4 | 5 1 2 | 6* 8 7
6 7 5 | 9 8 3 | 1 2 4
------+-------+------
1 5 9 | 3 7 8 | 2 6 4
9 8 7 | 6 4 5 | 3 1 2
4 3 2 | 1 9 4 | 8 7 5

(b) Response. Problem\(^{*}\): initial value modified.

Figure 4: Solving a Difficult Sudoku With Gemini 3 Pro (reasoning)

Before arriving at the result in Figure 4 (b), it should be noted that the reasoning time of Gemini 3 Pro doubled to produce the result (~3 minutes). After several rounds of trial and error, the LLM finally believes it has reached the solution to this grid and presents the result as we see it in this figure: on line 5, Gemini 3 Pro allowed itself to modify an initial value in the grid in order to make its solution fit. This is how a difficult instance managed to defeat one of Google’s most advanced reasoning models.

We repeat that this study is limited and requires a much larger test set. Nevertheless, it supports a broader study that we describe in the next section.

3.3 The Study by Seely et al. (2025)

To complement the previous results, the study by Seely et al. (2025) is presented in this section. It proposes a broader set of tests with \(100\) Sudoku instances of different kinds: \(15\) \(4×4\) grids, \(15\) \(6×6\) grids, and \(70\) \(9×9\) grids. Several LLMs are tested, including two OpenAI models (the standard GPT‑4.1 model and the reasoning model o3‑mini‑high), one Google model (Gemini 2.5 Pro), and a few open source models (Qwen-*).

Table 1: Success rate for solving different families of Sudoku (\(4×4\), \(6×6\), and \(9×9\)) with different LLMs

LLM model	\(4×4\)	\(6×6\)	\(9×9\)
o3‑mini‑high	73.3 %	6.7 %	2.9 %
Gemini 2.5 Pro	60.0 %	13.3 %	0.0 %
GPT‑4.1	13.3 %	0.0 %	0.0 %
Qwen-*	~40–53 %	0.0 %	0.0 %

In Table 1, we summarize the main results of Seely et al. (2025) as they relate to our topic. This table shows that even simplified Sudoku instances, at dimensions \(4×4\), do not achieve a perfect success rate. We note that models based on iterative-process reasoning (trial and error) reach up to \(60\%\), or even \(73.3\%\) success for the best OpenAI model (o3‑mini‑high). This model is also the only one to solve a few Sudoku instances at \(9×9\) dimensions. Finally, we note that Google’s previous model, Gemini 2.5 Pro, was not capable – at the time of that study – of solving these \(9×9\) puzzles.

These studies therefore experimentally highlight the inductive nature (as seen in Section 2.2.2) of the LLMs we use every day, as well as the difficulty they encounter when faced with puzzles like Sudoku – or more broadly with any novel question requiring a deductive reasoning chain – as soon as they rely on a connectionist paradigm. In a broader view of the kinds of problems we may encounter, this study (Giadikiaroglou et al. 2024) proposes a classification of puzzles according to their nature and the ability of different AI paradigms to answer them correctly, or not.

LLMs are trained by statistical induction on massive text corpora; they thus learn to predict the likely continuation of a given sequence. But when faced with Sudoku – an NP-complete problem requiring a systematic exploration of logical constraints – they struggle to maintain global consistency across the entire grid (Giadikiaroglou et al. 2024; Defresne et al. 2025). Even with advanced techniques such as chain-of-thought or tree-of-thought, their success rate remains well below that of classical symbolic solvers, which always guarantee a correct solution (Giadikiaroglou et al. 2024).

This observation illustrates that statistical induction alone is not enough to achieve deep algorithmic reasoning; current LLMs lack a robust mechanism for explicit logical inference. In the next section (Section 4.1), we describe some solutions proposed by the state of the art on paradigm hybridization: neuro-symbolic AI.

4 Discussion

4.1 Neuro-Symbolic AI and Its Promises

Contemporary research is moving toward deep integration between neural networks (inductive learning) and logical modules (deductive/abductive reasoning) (Colelough and Regli 2025; Wan et al. 2024; Wang et al. 2022). Neuro-symbolic architectures therefore aim to:

• inject logical constraints into neural learning;
• allow neural networks to dynamically call symbolical solvers;
• make AI decisions explainable;
• improve robustness in unfamiliar or ambiguous situations.

Notable progress has been made in various domains (automatic solving of complex visual puzzles such as Raven’s Progressive Matrices (Hersche et al. 2022), advanced question answering, and so on), but several challenges remain: scaling up, smooth multimodal integration, and preserving interpretability without sacrificing performance (Colelough and Regli 2025; Wan et al. 2024; Wang et al. 2022).

4.2 Deduction and Induction Definitions

The definitions proposed in this article regarding the principles of deduction and induction may be influenced by the field from which they originate. Nevertheless, for readers wishing to familiarize themselves with the definitions proposed by the field of philosophy, the following sources may offer alternative ways of defining them (Sider 2010; Novaes} and NIAS_library 2020).

5 Conclusion

Although modern AIs are impressive in their apparent versatility, it is crucial for any informed user – researcher or citizen alike – to remain critical of their true cognitive capabilities. LLMs excel where statistical induction is sufficient, but they fail as soon as a deep deductive chain is required (as in Sudoku). The future probably lies in a neuro-symbolic hybridization that will finally allow machines not only to “learn”, but also to truly “reason”. Until that major technological convergence arrives, vigilance and discernment remain essential in the face of sometimes exaggerated promises surrounding artificial intelligence.

Acknowledgment

héhé

References

Bergman, Martin, S. Paavola, and A. Pietarinen. 2011. Nordic Studies in Pragmatism Helsinki | 2010 Gerhard Minnameier “ the Logicality of Abduction , Deduction and Induction ”.

Colelough, B., and William Regli. 2025. “Neuro-Symbolic AI in 2024: A Systematic Review.” ArXiv abs/2501.05435. https://doi.org/10.48550/arxiv.2501.05435.

Defresne, Marianne, Romain Gambardella, S. Barbe, and T. Schiex. 2025. Scaling Neuro-Symbolic Problem Solving: Solver-Free Learning of Constraints and Objectives. https://doi.org/10.1613/jair.1.21105.

Giadikiaroglou, Panagiotis, Maria Lymperaiou, Giorgos Filandrianos, and G. Stamou. 2024. “Puzzle Solving Using Reasoning of Large Language Models: A Survey.” ArXiv abs/2402.11291. https://doi.org/10.18653/v1/2024.emnlp-main.646.

Hersche, Michael, Mustafa Zeqiri, L. Benini, Abu Sebastian, and Abbas Rahimi. 2022. “A Neuro-Vector-Symbolic Architecture for Solving Raven’s Progressive Matrices.” Nature Machine Intelligence 5: 363–75. https://doi.org/10.1038/s42256-023-00630-8.

Novaes}, Catarina {Dutilh, and NIAS_library. 2020. The Dialogical Roots of Deduction: Historical, Cognitive, and Philosophical Perspectives on Reasoning. Cambridge University Press.

Qi, Xinshe, Guo Li, Na Wang, Xin Wang, and Liang Wen. 2019. “Method Study on Solving Sudoku Problem.” 2019 3rd International Conference on Data Science and Business Analytics (ICDSBA), 269–71. https://doi.org/10.1109/icdsba48748.2019.00063.

Saygin, A., and I. Çiçekli. 2000. “Turing Test: 50 Years Later.” Minds and Machines 10: 463–518. https://doi.org/10.1023/a:1011288000451.

Seely, Jeffrey, Yuki Imajuku, Tianyu Zhao, Edoardo Cetin, and Llion Jones. 2025. “Sudoku-Bench: Evaluating Creative Reasoning with Sudoku Variants.” ArXiv abs/2505.16135. https://doi.org/10.48550/arxiv.2505.16135.

Sider, T. 2010. Logic for Philosophy. Oxford University Press. https://books.google.fr/books?id=-KkPEAAAQBAJ.

Vudka, A. 2020. The Golem in the Age of Artificial Intelligence. 9: 101–23. https://doi.org/10.25969/mediarep/14326.

Wan, Zishen, Che-Kai Liu, Hanchen Yang, et al. 2024. “Towards Cognitive AI Systems: A Survey and Prospective on Neuro-Symbolic AI.” ArXiv abs/2401.01040. https://doi.org/10.48550/arxiv.2401.01040.

Wang, Ge, Xianhong Li, and Shenghua Xie. 2024. “Bilateral Turing Test: Assessing Machine Consciousness Simulations.” Cognitive Systems Research 88. https://doi.org/10.1016/j.cogsys.2024.101299.

Wang, Wenguan, Yi Yang, and Fei Wu. 2022. “Towards Data-and Knowledge-Driven AI: A Survey on Neuro-Symbolic Computing.” IEEE Transactions on Pattern Analysis and Machine Intelligence 47: 878–99. https://doi.org/10.1109/tpami.2024.3483273.

Footnotes

1. Definition proposed by Wikipedia: https://en.wikipedia.org/wiki/Sudoku

2. Not in terms of algorithmic complexity—where each instance has the same complexity—but depending on the technique used to solve it.