Artificial Intelligence, Computer Science
Solving Sudoku With AI or Quantum?
After a centenary of existence as a fun board game, how the Sudoku became one of the focus points of the Computational Research? Explore how you can create an intelligent Sudoku Solver from Scratch using AI or Quantum Computers.
A little bit of history before diving deeper:
“History is called the mother of all subjects”, said Marc Bloch. So, let’s talk about how the famous Sudoku even came into existence. The story dates back to the late 19th Century and it originated from France. Le Siecle, a French daily published a 9x9 puzzle that required arithmetic calculations to solve rather than logic and had double-digit numbers instead of 1-to-9 with similar game properties like Sudoku where the digits across rows, columns, and diagonals if added, will result in the same number. In 1979 a retired architect and puzzler named Howard Garns is believed to be the creator behind the modern Sudoku which was first published by Dell Magazines in the name of Number Place. The puzzle was first published in the name Sudoku in 1986 by a Japanese puzzle company named Nikoli.
Framing the Problems in solving a Sudoku:
Sudoku is a real-world example of a Constraint Satisfaction Problem (CSP) as the variable set, domain set and the set of constraints are all finite. We must enter numbers ranging from 1–9 in a 9x9 table in such a manner that the numbers in every row, column, and in every 3x3 sub-table contains each number exactly once. There exists another variation of Sudoku too, which is Diagonal Sudoku with an extra set of constraints stating in each of the table diagonals each number must exactly be featured once. As we know about the constraint satisfaction domain the optimal solution must satisfy all the constraints or more specifically it should abide by the rules of the game. The optimal solution will satisfy all the constraints in the set thus will solve the puzzle.
Computationally the constraints of solving a n x n sudoku can be solved in nondeterministic polynomial time (NP) as the constraints can be solved with some very specific brute-force algorithms and the validity of the set of solutions can be tested in polynomial time too where the inputs to the problem are associated with a set of solutions of polynomial length. A completely solved Sudoku is an example of a Latin Square (n x n array filled with n different symbols, as described by Euler). The Sudoku problem can be thought of as a graph coloring problem where we need to color the graph using only 9 colors and the exposed letters can be thought of as a partial color.
Satisfying Constraints with Artificially Intelligent set of Algorithms:
The founding principles of Computational Sciences stand on the ability to satisfy certain constraints with the help of logic. In the scenario of solving sudoku, we must train the solver to look for some specific match-winning patterns besides the basic rules. So, the thing is the system is not just following the rules blindly it is also taking some decisions keeping in mind its near and long-term effects. These patterns are called Heuristics. Similar to expert players who happen to know about some tips and tricks of the game, knowing only the basic rules doesn’t make them an expert in the game. So, while we develop the algorithms and solve our problems we must keep in mind the useful heuristics which we should also include in our program to make it smarter and more useful when it comes to winning.
For our Sudoku Solver, we will take input the sequence of 81 numbers as a string and will represent unsolved numbers with ‘.’(period). To solve the problem we are going to do is replace the ‘.’ with all the probable numbers which can be placed into that cell.
According to the constraints of the Sudoku, we cannot use a single digit more than once in a row, column, or in a 3x3 sub-square in the vicinity of any cell. In the case of Diagonal Sudoku, we must also take into consideration the same constraint. We start by replacing the period with all possible numbers from 1 to 9. We do this programmatically by using the following grid_values function.
As we have now replaced the unsolved cells with all possible numbers from 1 to 9, we know from the basic rules of the Sudoku that we cannot use a number twice if it has already been used across that row, column and within the 3x3 sub-square of that cell. So, let us eliminate them if we encounter them at the unsolved grids which we have filled with all possible numbers initially. So let us take a look at how we can eliminate those irrelevant numbers from the unsolved cells using the eliminate python method.
So, while satisfying these constraints we sometimes come across some cells where only a single digit can be placed, no other digit becomes viable for that specific cell except that digit. We fill in these at the very first of all. With their proper solution. We call this Only Choice, the easiest heuristic to solve a cell of a sudoku grid.
In our journey so far around Constraint Satisfaction, there might come a situation where there will be two unsolved cells in a unit (considering row, column, and 3x3 sub-square) where only two specific remaining numbers can be assigned. So, these two numbers can be effectively removed from the possible numbers on other cells in the same unit. This heuristic is called the Naked Twins. The algorithm implementation specifically makes a deep copy of the grid values and checks for the naked twins' feasibility that is whether there are exactly two unsolved cells which can accept only two specific values and if it does it goes ahead and removes those two values from other cells in the same unit. We implement it programmatically by using the naked_twins function as written below:
We now try to reduce the puzzle as much as possible by repeatedly applying these three constraint satisfaction algorithms and checking if it is stuck and cannot reduce any further. We do this programmatically by using the reduce_puzzle function. What we do is we call the previous three function inside a for loop and terminate it when the number of solved cells in both the input and the output sequence of the grid values are the same, which means that it cannot be reduced any further by only the constraint satisfaction algorithms alone.
If the sudoku grid is still not solved with the constraint satisfaction problem, a partial solution will get to the output where a few of the cells will still be assigned to certain possible values. In these circumstances what we do is we use a search tree to search for the optimal set of digits in those places. We use Depth First Search (DFS) algorithm to traverse through the search tree. So basically with DFS we create up a few instances with the same grid and try out different possible assignments for each of the yet-unsolved cells. We recursively call for the CSP algorithms to reduce the grid based on the search results. We implement it programmatically as below:
We use the display sudoku function to display the input string sequence as a two-dimensional 9x9 Sudoku grid:
To solve a Sudoku Sequence we call the above functions like the following:
The output looks like the following, where the set of algorithms have been successful in calculating the answer.
The Quantum Approach to Solving Sudoku as a Constraint Satisfaction Problem:
We will now try to solve a simple Sudoku Grid with Quantum Simulated Annealing. First things first, what is the simulated annealing? The idea is for optimization problems like this we use some sub-optimal heuristics and obtain the optimal set of heuristics to obtain the optimal solution. We have used here the DWave AQC Model (Adiabetic Quantum Computing) to sample out the optimal solution which satisfies the constraints discussed earlier.
Using the DWave Kerberos Hybrid Sampler:
We are in this example working with the hybrid solver provided with DWave. It finds out the optimal set of heuristics by running a parallel tabu search. It’s a hybrid solver as it uses both quantum and the classical properties of computation underneath. It is also a decomposition sampler that uses an asynchronous workflow while processing. It’s included in the Ocean SDK package of the DWave Systems. To get started with the development locally make sure you have Python 3.5+ installed on your system and issue the following command.
python -m pip install --upgrade pippip install dwave-ocean-sdk
Using Binary Quadratic Models (BQM) for the calculations:
We cannot frame the constraints directly ready to be fed to the Quantum Computers, we need an intermediate representation for it to be getting fed. That’s why we will use BQM, fortunately, DWave Ocean SDK already provides a tool called combinations which can be used to frame Constraint Satisfaction Problems into BQMs. Firstly Binary Quadratic Models as the name itself suggests is a system of the equation which is quadratic and is expressed in Binary. Due to higher complexities in calculations, Quantum computers use these to significantly speed up the development process. So, back in the game we were we have decided to use the combinations tool from dimod which is going to return a Binary Quadratic Model which is minimized for each of the k-combinations of its input and internal variables.
We start by importing necessary packages from the dwave-ocean-sdk and do some sanity check before actually reading into the Sudoku Grid.
We now go ahead and create up the Binary Quadratic Models using combinations tools from all the available variable combinations of the Sudoku Grid’s rows, columns, and sub-square indices.
So, that is it. We have successfully implemented two intelligent solutions one of which uses classical Computation and uses Artificially Intelligent Heuristic, really powerful, and can solve even diagonal sudoku grids. The second one uses an Asynchronous hybrid heuristic sampler which also happens to use state of the art Simulated Annealing of the Adiabatic Quantum Computing model to perform a conversion of the Constraint satisfaction problem to a Binary Quadratic Model to perform sampling over it and thereby obtaining the optimal solution.
I am earnestly grateful to you for your time.
“Even the greatest fool can accomplish a task if it were after his or her heart. But the intelligent ones are those who can convert every work into one that suits their taste.” — Swami Vivekananda.
