Sudoku Assistant – An AI Assistant Combining Machine Learning and Reasoning
This story was originally published via Leuven.AI Stories.
Sudoku is a popular pen-and-paper puzzle game that involves completing a partially filled-in 9x9 grid such that each row, column, and 3x3 box contains all of the digits from 1 to 9. It is commonly included in the puzzle section of newspapers and magazines, and is even sold in the form of dedicated Sudoku puzzle books. It comes in many variants and even has its own annual world championship.
It is also often included in introductory artificial intelligence (AI) courses as a nice way to introduce students to the area of constraint programming (CP), a research field that focuses on solving problems that are expressed as constraints over decision variables. With some basic constraint programming knowledge, it is surprisingly easy to write the Sudoku rules as constraints, and have a generic solver compute the solution in milliseconds.
However, using these highly effective constraint reasoning techniques requires that the Sudoku is provided in a symbolic way, meaning that the 9x9 grid and the given digits are provided to the system as a matrix of numbers. If the Sudoku were given in the form of an image (taken with a smartphone, for example), then this image could not be given as input to a constraint solver. One first has to recognize the given digits and the empty cells, a task best tackled using computer vision techniques involving (convolutional) neural networks, which are machine learning models that can learn to recognize objects, translate text, generate images and so much more.
Machine learning (e.g., neural networks) and reasoning (e.g., constraint programming) are subfields of AI that have historically been developed mostly independently from one another. However, nowadays there is a growing research interest in combining these subfields. We have developed the Sudoku Assistant app, available on the Google Play store, as a demonstration of such a combination.
Sudoku Assistant – a demonstrator of three AI trends
The Sudoku Assistant is an AI assistant that can interpret, solve and explain pen-and-paper Sudokus scanned with a smartphone. It uses techniques from both machine learning and constraint programming, but goes one step further: it employs a new way of integrating the digit recognition and the reasoning more deeply, allowing it to solve significantly more scanned Sudokus correctly than previous approaches were able to.
Furthermore, it isn’t limited to merely solving Sudokus: through the use of our state-of-the-art research on step-wise explanations to constraint satisfaction problems, it is able to guide the user through the solving process by giving small hints. This ensures that the AI system doesn’t ruin the fun by doing the solving for you, but is able to assist you when you are stuck.
The Sudoku Assistant hence demonstrates three concepts that are becoming increasingly important in AI research: the integration of learning and reasoning, explainable AI and human-centered AI. And although the assistant is focused on Sudoku, the underlying techniques are equally applicable to other constraint solving problems like timetabling, scheduling and vehicle routing.
Solving Scanned Sudokus with integrated prediction and reasoning
One of the Sudoku Assistant’s main features is the ability to solve pen-and-paper Sudokus scanned with a smartphone. To do this, the user starts by taking a picture of a Sudoku puzzle. After a picture is taken, the image is segmented into 81 cells. A pre-trained neural network – more specifically a convolutional neural network (CNN), which is commonly used for image recognition tasks – is then applied to each cell in order to make a digit prediction.
For each cell, the output of the CNN is a probability distribution over the 10 possible values: digits 1-9 and the empty cell value. Once a probability distribution has been predicted for each cell, the distributions should be used somehow in order to obtain a solution, i.e., a fully filled-in Sudoku. There are two ways of doing this: a naive way in which the digit prediction and the constraint reasoning are clearly separated, and a more effective way in which they are integrated.
Figure 1: Cropped and aligned picture of a Sudoku grid taken with a smartphone camera.
Figure 2: In each cell, the predicted probability distribution is visualized using a bar chart. The blue bar represents the probability of the cell being empty, while the other 9 bars represent the probabilities of the digits 1 to 9. Bars associated with very small probabilities are omitted
A naive, separated, approach
A naive way of using the probability distributions to solve the Sudoku involves assigning to each cell the value that is given the largest probability by the CNN classifier (i.e., the argmax, the most likely prediction). The resulting partial Sudoku can then be modeled as a constraint satisfaction problem (CSP), which is a problem that consists solely of constraints, and thus does not contain a criterion to be optimized. The CSP can be given to a generic constraint solver in order to obtain the full solution. This approach is schematically shown in Figure 3.
One large disadvantage of this approach results from the fact that even a single misclassification almost always leads to a wrong solution, or no solution at all. For this reason, even if the digit classifier would have an accuracy of 99%, the naive approach would lead to a correct solution only approximately 0.9981 = 44% of the time (since 81 cells must be classified). To improve on this weakness, a deeper integration of the digit recognition and the reasoning is needed.
Figure 3: The naive approach. First, a CNN classifier predicts a probability distribution over all 10 possible values for each cell. Then, for each cell, the value with the largest assigned probability is taken and given to a CSP solver, which then computes and outputs the solution.
An integrated approach
To avoid finding no solution or a wrong solution, we proposed an alternative approach, which features a deeper integration of the digit classification and the reasoning required to solve the Sudoku puzzle. This approach is schematically shown in Figure 4.
Figure 4: An integrated approach. The difference with Figure 3 can be seen in the input to the CP solver: here, the full probability distributions produced by the CNN classifier – rather than just the most likely predictions – are used by the CP solver to compute the assignment with the maximum likelihood that respects the Sudoku constraints. This integrated approach can successfully solve considerably more Sudoku puzzles than the naive approach.
The main idea is to not provide the constraint solver with merely the most likely digit – as predicted by the neural network – for each of the Sudoku’s cells, but rather with the full distributions outputted by the network. In other words, for each of the 81 cells, the solver is given the class probabilities of all 10 possible classes. The solver is then tasked to solve a constrained optimization problem (COP), rather than a CSP. This means that it does not merely look for a solution that satisfies certain constraints anymore. It now prefers certain constraint-satisfying solutions over others.
Concretely, the solver now searches for a solution in which the product of the probabilities associated with all the chosen digits is maximal (i.e., the maximum likelihood solution, given the class probabilities), whilst satisfying the rules of Sudoku. Effectively, this integrated approach allows the reasoning to correct some of the mistakes made by the CNN classifier, by subjecting the classifications to the Sudoku constraints.
Figure 5: Wrongly predicted digits corrected by the joint prediction-and-reasoning approach shown in Figure 4.
Consider, for example, the Sudoku puzzle shown in Figure 5. The naive approach would assign value 2 to the cell highlighted in red, as well as to the cell above it, highlighted in blue, based on the predicted probability distributions (which were shown in Figure 2). However, since two cells in the same column would contain a 2, the CSP solver would not be able to find a valid solution to the problem.
Instead, our integrated approach recognizes that if the value 2 would occur twice in the same column, a Sudoku constraint would be violated. To correct this conflict, it considers the other probabilities in the predicted distributions. In this case the correction is quite easy: the second largest probability of the cell in red (associated with the value 3) is larger than the second largest probability of the cell in blue, and assigning the value 3 to the cell in red does not conflict with any of the other value assignments. Thus, the value 3 is assigned to the cell in red.
If, instead, the value 3 did conflict with another assignment, then either that other assignment would also be corrected, or a value with an even lower probability would be assigned to the cell in red, depending on which option leads to the largest joint probability (the product of the probabilities associated with the assigned values). In this way, the corrections can become quite complex, as is demonstrated in Figure 6, where the cells in red represent the corrections (i.e., value assignments that do not have the largest probability according to the digit recognition model).
Our approach might even make a correction when there is no direct conflict between any of the most probable values of the different cells. This happens when those values constitute a Sudoku that has no solution, or one that has multiple solutions. Even in these cases the integrated approach knows that the digit recognition model must have made a mistake, since a valid Sudoku must have a unique solution.
Figure 6: The corrections made by the novel integrated approach can become quite complex.
Guiding the user by generating hints
We want the Sudoku Assistant to do more than just show the solution and ruin all the fun for the user. We also want it to be able to guide the user to finding the solution, and to make them learn some solving strategies along the way. For this purpose, we integrated our state-of-the-art research on step-wise explaining constraint satisfaction problems into the assistant.
Figure 7: A generated hint.
As a result, the Sudoku Assistant has a hint mechanism that provides the easiest next move among all empty cells. The provided hint highlights only the existing digits and constraints necessary to derive that cell’s value.
In Figure 6, the green cell containing a white puzzle piece represents a derived digit, which is currently hidden to the user in order to give them the chance to derive it by themselves. The cells highlighted in yellow contain the values that are needed in the derivation, and the blue column and row represent the constraints involved. These values and constraints are sufficient to derive that the green cell should contain the digit… 7!
We stated above that the Sudoku Assistant always provides the easiest possible explanation step. We achieve this by using a cost function that expresses an explanation step’s difficulty, namely the number of constraints involved in it. This reflects the intuition that explanation steps involving many constraints are more difficult to understand than steps with less constraints.
Of course, the ‘real’ cost function that captures the actual difficulty of an explanation step from the perspective of a human is likely much more complex and nuanced, and probably domain dependent. The development of a cost function that better reflects this human perspective is definitely a promising direction for future work.
A broader perspective
The approaches detailed in this article are by no means limited to Sudoku. The integrated approach is applicable to any problem consisting of a classification step followed by a constraint programming step. This means that it can easily be used on the many variants of Sudoku, or other puzzle games like Numberlink, Kakuro and Hidato.
There are also a range of real-world problems that require the scanning and interpreting of documents, where the required structure of the document is known (e.g., tax forms) or where the information provided has to be verified or completed (e.g., subsidy request forms). Even archaeological reconstruction of pieces into statues or paintings requires perception and reasoning. Just like in the Sudoku setting, knowledge of the requirements and constraints can be used to (re)construct the desired input, even when the machine learning models used for scanning make mistakes.
Also our approach to step-wise explanations can easily be used on other constraint satisfaction problems, such as other logic puzzles and real-world problems like scheduling, timetabling and routing problems. For example, a company may need to find a schedule ensuring that each employee works a certain number of hours per week, that no two employees are scheduled to do the same job at the same time, and that all shifts are covered. The ability to generate a step-wise explanation of such a schedule can help employees understand why they have to work in certain shifts, and can help increase overall trust in the scheduling system.
The Sudoku Assistant was built using our Python-based CPMpy Constraint Programming and Modeling library. We started building this library 2 years ago to facilitate the integration of constraint solving and machine learning, and to ease the development of explanation algorithms and other algorithms that involve repeatedly calling constraint solvers. The library, and the Sudoku Assistant, are part of Professor Tias Guns’ prestigious 5-year ERC funded project on Conversational Human-Aware Technologies for Optimisation.
The assistant is based on the following publications:
- Hybrid classification and reasoning for image-based constraint solving. Maxime Mulamba, Jayanta Mandi, Rocsildes Canoy, and Tias Guns, In International Conference on Integration of Constraint Programming, Artificial Intelligence, and Operations Research, pages 364–380. Springer, 2020.
- Efficiently Explaining CSPs with Unsatisfiable Subset Optimization Emilio Gamba, Bart Bogaerts, and Tias Guns. In International Joint Conference on Artificial Intelligence, 1381-1388, 2021.
System Overview
Try it for yourself
