Abstract
Sudoku, a popular numbers puzzle, is more than just a fun brain teaser. It is a prime example of the Constraint Satisfaction Problem, a fundamental concept in how artificial intelligence (AI) and machine learning (ML) models conduct decision-making and optimize efficient solutions to relevant issues. Through puzzles and problems like Sudoku, humans have naturally developed techniques based on their logic and intuition. Machines operate in a similar way by learning to solve issues algorithmically based on patterns. Artificial Intelligence does not invent the solutions it finds, but rather formalizes, refines, and scales the methods humans already intuitively use–like elimination, recognition, and logical deduction. These algorithms help to streamline processes that solve real-world issues such as scheduling, medical diagnoses, and robotics. Sudoku can serve as a simple but effective lens into AI’s foundational problem-solving techniques and how these are essential in advancing machine learning models and their applications to everyday life.
Introduction
On the surface, Sudoku appears to be a simple logic-based puzzle. It requires players to fill an n² × n² grid so that every row, column, and n×n box contains the numbers 1 through n² exactly once. While n can be of any value, it is most commonly 3, resulting in the familiar 9×9 grid [1]. The puzzle begins with some numbers already filled in as clues, and players must deduce the missing values based on the constraints. For a 9×9 Sudoku puzzle, the minimum number of clues necessary to be solved with a unique solution is 17 clues [2]. But beneath these straightforward and simple rules, there is a deep mathematical structure that challenges solvers to think systematically. Unlike other puzzles that may involve trial and error, Sudoku does not require guessing as each part of the solution can be derived logically from the puzzle’s built-in constraints.
While Sudoku is usually thought of as a fun mental exercise, its underlying mechanics are pertinent to the field of artificial intelligence and how machine learning models solve problems. It is a prime example of a Constraint Satisfaction Problem (CSP), a type of problem where a set of variables must be assigned values while satisfying certain constraints. Just as humans use logic-based strategies to solve Sudoku, computers and AI algorithms approach it using CSP-solving techniques.
Constraint Satisfaction Problems
A Constraint Satisfaction Problem (CSP) is a mathematical framework in which a set of variables must be assigned values while following constraints [3]. CSPs appear across many fields of engineering, such as optimization, scheduling, and artificial intelligence.
Every CSP consists of three main components. The following will be described with a Sudoku of a 9×9 grid:
1. Variables – These are the unknowns that need to be assigned values [3].In Sudoku, each empty cell in the grid is a variable that must be filled with a number.
2. Domain – This is the set of possible values that can be assigned to each variable [3].In Sudoku, the domain for each empty cell is {1,2,3,4,5,6,7,8,9}, meaning each number is a potential solution.
3. Constraints – These are the rules that limit how variables can be assigned [3].In Sudoku, the key constraints are as follows:
– No number may repeat within the same row.
– No number may repeat within the same column.
– No number may repeat within the same 3×3 box.
Brute Force: A Backtracking Method
The simplest way for a computer to solve Sudoku is through backtracking, a brute-force method that uses pure trial and error without any real strategy. It tests all possible answers recursively until a valid solution is found [5]. The process for a typical 9×9 puzzle involves the following steps:
1. Pick an empty cell.
2. Try filling it with numbers in the domain (1-9).
3. If the number violates Sudoku’s constraints, backtrack and try the next number.
4. Repeat this process until the grid is filled and returns a valid solution.
5. If a contradiction arises later in the process, the algorithm backtracks, erasing previous choices until it finds a valid path [3].
While backtracking guarantees a solution if one exists, it is computationally expensive and inefficient. An empty 9×9 Sudoku grid has 6.67×10²¹ possible solutions [4], and thus Sudoku puzzles require more sophisticated techniques that prove more efficient.
In Sudoku, the Naked Single strategy’s reasoning is similar to how backtracking checks for the correct answer. A Naked Single describes a cell that has only one possible number left after considering all constraints. Since no other numbers can logically fit, that value must be placed. While backtracking does not have this sort of logic behind it, it is similar in that it checks if it violates any constraints and moves forward.
Contraint Propagation: Making Smarter Choices Earlier
Constraint propagation is a more efficient CSP-solving algorithm than backtracking. Rather than brute-force guessing and checking, it systematically eliminates the incorrect values in each cell from consideration before attempting to solve [3]. Constraint propagation works as follows:
1. Constraints are applied to variables, reducing the possible values (domains) for empty cells.
2. As the constraints propagate, the puzzle becomes easier to solve since fewer choices remain.
3. If a variable’s domain is reduced to nothing during propagation, there has been an error or inconsistency, so backtracking is used to correct the mistake [3]
This approach is often combined with other CSP-solving algorithms, like backtracking, to further improve efficiency. By narrowing down possibilities upfront, constraint propagation makes it so that when backtracking is needed, it is applied to a smaller and more manageable problem space.
Concepts of constraint propagation are similar to the basis of logic in real Sudoku techniques. In Sudoku, these methods translate into algorithms like forward checking as well as techniques like the Hidden Single or Naked Pairs. Forward checking is an algorithm used more generally in AI where the computer reduces conflicts. After a variable is assigned a value, dependent variables are automatically updated to prevent inconsistencies. In Sudoku, forward checking eliminates a number out of possibility in all connected cells as soon as it is placed [3].
Hidden Singles is a Sudoku technique that is derived from constraint propagation. Narrowing possibilities before attempting a solution can help reveal a forced placement in the solution. AHidden Single occurs when a number appears only once within a row, column, or 3×3 box. Even if other numbers are technically possible, the fact that that specific number only appears once means it has to go there [6]. Constraint propagation in certain cells can actually lead to solutions in not only those cells, but also dependent ones. Similarly, a Naked Pair, as seen in Figure 2, occurs when two cells in a unit (row, column, or box) are reduced to only containing the same two numbers. This means that no other cell in that unit can have those two numbers.
Algorithms like constraint propagation or forward checking, along with Sudoku techniques
derived from those algorithms’ logic, can all help solve Sudoku with a CSP-solving approach.
They refine the grid by eliminating numbers early, preventing unnecessary backtracking and
clearing a more efficient path to the solution.
Heuristic-based Solving: Where Should We Solve First?
In CSP solving, a heuristic is a method that prioritizes efficiency over searching, which is a method that AI and machine learning systems often rely on to make decisions faster. They work by targeting or prioritizing the parts of the problem to solve first. [1]. For example, a variable ordering heuristic would target solving the cells with the smallest domains first or the cells with the most dependencies in relation to other cells; it would choose the cells that leave the most options open for other cells [1]. To clarify, a heuristic makes better choices on how to attack the problem by guiding the search process, whereas constraint propagation reduces the complexity of the problem by clearing out possibilities. Computers can use a combination of heuristics and constraint propagation to solve extremely efficiently [7].
The X-Wing strategy is an example of a more advanced heuristic-based Sudoku technique that also involves constraint propagation. It is best explained with an example, as seen in Figure 3:
1. Based on the constraints, rows three and five each only have two cells that could be a four. These four cells form an X pattern, with two diagonal lines– also known as the X- wing.
2. Based on the constraints, columns two and five technically have many cells that could be a four.
3. There are only two possible scenarios to fill out the fours while satisfying the constraint to have no repeats in each row– when the fours are placed along the diagonals (the blue fours or the purple fours in figure 3).
4. In either scenario, there will be a four in column two and five.
5. Thus, regardless of the actual correct scenario, we know that there cannot be a four in the other cells of column two and five [8].
This strategy is formed on the same logic of heuristics, where the X-Wing is targeted because many other cells are dependent on the X-Wing and can be constraint propagated after (with reducing the value). Heuristic-driven decision-making is used in AI pathfinding algorithms, where a system doesn’t explore every route but instead prioritizes the most efficient ones.
Beyond Sudoku: CSPs in the Real World
The problem-solving techniques used in Sudoku are interesting. In fact, there is a good amount of research on the best and worst algorithms made to solve Sudokus [7]. But its relevance lies in how these algorithms extend beyond puzzles by playing a crucial role in artificial intelligence and optimization. AI planning and robotics rely on Constraint Satisfaction Problems to help computer systems navigate environments and issues efficiently by eliminating impossible paths or systematically selecting the best possible route—much like how Sudoku solvers narrow down solutions [9].
Medical diagnosis applies similar principles, using CSP-based reasoning to rule out diseases based on symptoms. In daily life, CSP algorithms are used for scheduling based on various constraints such as deadlines, resources, or safety rules for construction or teachers, students, space, and requirements for class registration [10]. Sudoku’s logic connects to the way AI applies algorithms to solve real-world problems. In robotics, healthcare, or even scheduling, CSP techniques provide a structured, logical approach to solving complex problems.
Conclusion
Sudoku is not just a popular logic puzzle; it is a window into the computational field of constraint satisfaction. From brute-force backtracking to constraint propagation to heuristics, the strategies humans use to solve Sudoku naturally align with techniques in AI problem-solving. While humans have already formed ways of reasoning and logically deduced techniques, machines and computers are learning to solve problems in similar ways. The ability to efficiently solve constrained problems is extremely prevalent in our day-to-day lives, and improving the way computers employ algorithms can greatly enhance the way technology can make significant and positive solutions.
References
[1] M. C. Machado and L. Chaimowicz, “Combining Metaheuristics and CSP Algorithms to Solve Sudoku,” in Proc. 2011 Brazilian Symposium on Games and Digital Entertainment, Salvador, Brazil, 2011, pp. 124-131. doi: 10.1109/SBGAMES.2011.18. [Online]. Available: https://ieeexplore.ieee.org/abstract/document/6363225.
[2] G. McGuire, B. Tugemann, and G. Civario, “There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem via Hitting Set Enumeration,” arXiv, Aug. 31, 2013. [Online]. Available: https://arxiv.org/pdf/1201.0749
[3] “Constraint Satisfaction Problems (CSP) in Artificial Intelligence,” GeeksforGeeks, Oct. 3, 2024. [Online]. Available: https://www.geeksforgeeks.org/constraint-satisfaction-problems-csp-in-artificial-intelligence/.
[4] H. Simonis, “Sudoku as a Constraint Problem,” 2013. [Online]. Available: https://ai.dmi.unibas.ch/_files/teaching/fs13/ki/material/ki10-sudoku-inference.pdf.
[5] V. Kumar, “Algorithms for Constraint-Satisfaction Problems: A Survey,” AI Magazine, vol. 13, no. 1, Spring 1992. [Online]. Available: https://ojs.aaai.org/aimagazine/index.php/aimagazine/article/view/976.
[6] S. Brandwein, “8 Sudoku Solving Strategies to Try Next Time You’re Stuck,” The Puzzle Society, Apr. 4, 2024. [Online]. Available: https://www.puzzlesociety.com/the-solutionist/sudoku-solving-strategies.
[7] N. Pillay, “Finding Solutions to Sudoku Puzzles Using Human Intuitive Heuristics,” South African Computer Journal, vol. 49, pp. 25-34, 2012. doi: 10.18489/sacj.v49i0.111. [Online]. Available: https://www.researchgate.net/publication/256087959_Finding_Solutions_to_Sudoku_Puzzles_Using_Human_Intuitive_Heuristics.
[8] “X-wing technique,” sudoku.com. [Online]. Available: https://sudoku.com/sudoku-rules/h-wing/.
[9] S. C. Brailsford, C. N. Potts, and B. M. Smith, “Constraint satisfaction problems: Algorithms and applications,” European Journal of Operational Research, vol. 119, no. 3, pp. 557-581, Dec. 1999. [Online]. Available: https://www.sciencedirect.com/science/article/abs/pii/S0377221798003646.
[10] P. Lorterapong and M. Ussavadilokrit, “Construction Scheduling Using the Constraint Satisfaction Problem Method,” Journal of Construction Engineering and Management, vol. 139, no. 4, 2013. [Online]. Available: https://ascelibrary.org/doi/abs/10.1061/(ASCE)CO.1943-7862.0000582.
