Slaying the Sudoku Puzzle
Implement the AI techniques of constraint propagation and search in Python to solve a Sudoku board
There seem to be two main types of people in the world, crosswords and sudokus. — Rebecca McKinsey
In this article, you will constraint propagation and search by making a program that solves Sudoku board. All of the code is written in Python3 and is available on my GitHub profile along with instructions on how to use and execute the code.
https://github.com/zahash/ArtificialIntelligence/tree/master/sudoku
Before jumping straight into the code, lets first get familiar with some terminology and rules of Sudoku.
For all of you extraterrestrials that are reading this article, this is what a typical unsolved sudoku board looks like.
Getting familiar with Sudoku
Every 9x9 sudoku board is divided into nine 3x3 sections.
The rows will be labeled by the letters A, B, C, D, E, F, G, H, I. The columns will be labeled by the numbers 1, 2, 3, 4, 5, 6, 7, 8, 9. Note that the labeling convention is just for our understanding and doesn’t actually exists on the board.
The individual squares at the intersection of rows and columns will be called boxes. These boxes will have labels 'A1', 'A2', …, 'I9'. We will use these labels to address each box on the board uniquely while coding
Each row, column, and 3x3 square will be called a unit. Thus, each unit is a set of 9 boxes, and there are 27 units in total.
For a particular box (such as ‘E7’), its peers will be all other boxes that belong to a common unit (namely, those that belong to the same row, column, or 3x3 square).
The rules of the game are pretty straightforward. Fill all of the empty boxes on the board with a digit such that none of the boxes in the same row, same column, or same 3x3 square has that same digit.
Encoding the board
We have to figure out a way to represent the board and everything about it using a suitable data structure.
This is probably the most important part of the project because everything else depends on it. If you get this wrong then the code will either be inefficient or just not work properly.
The input
- The starting values of the unsolved board will be represented by a string of digits with a dot(.) to represent if the box is empty.
- The correct format of the input should consist of a concatenation of all the readings of the digits in the rows, taking the rows from top to bottom.
- The input string to the above-shown sudoku is
‘53..7….6..195….98….6.8…6…34..8.3..17…2…6.6….28….419..5….8..79’
The board
- The board itself will be represented in the form of a dictionary with the keys to be the labels of each the box(‘E7’) and the values to be the digit in the box
The units
- The 27 units will be stored as a list of lists with each inner list representing a single unit that contains all the labels of boxes present in the same row or column or 3x3 square
- We will use this unit list to create a unit dictionary to store the information about which box is a part of which unit. Its keys will be the labels of boxes and its values will be a list of all the units of which the box is a part of
The peers
- The peers will be stored as a dictionary with the keys representing the labels of boxes and the values representing the set of all of the box’s peers
Now that we have encoded the board lets just jump right into the coding part
The Coding part
Lets now write the code to encode the board
Write a helper function that takes in two iterables (like a string) and returns their Cartesian product
Another helper function to print the sudoku board in a visually appealing way
Now comes the actual encoding
The above code is the entire main function. For now, just look till the 24th line
The Elimination Method
Look at the highlighted box on the board and guess all the possible values that can go into that.
By looking at its row we can say that the box cannot contain 3, 6, 8. By looking at its column, the box cannot contain 1, 4, 8 and finally by looking at its 3x3 square, the box cannot contain 2, 3, 6, 8. So the options left for that box are 5,7,9.
This is the main idea behind the Elimination method. We eliminate the possible values according to the rules to get a simplified version of the puzzle.
To do this in code lets replace all the empty boxes represented by a dot(.) with the string ‘123456789’ because all values are possible initially before eliminating.
Look at the lines from 29 to 32 in the main function above for the code
Now, create a function that takes the unsolved sudoku board (as a dictionary) and returns the same board (as a dictionary) but after applying elimination ‘once’ to all of the boxes
Encode the board and run the elimination function once. Display the board before and after eliminating using the given display function.
The only choice method
After running the elimination function we will get a partially solved sudoku-like this
5 3 124 | 26 7 8246 | 1948 1924 82
6 47 247 | 1 9 5 | 8347 24 827
12 9 8 | 32 34 24 |13547 6 247
------------------+------------------+------------------
8 15 195 | 7 6 14 | 9547 9254 3
4 2 926 | 8 5 3 | 97 925 1
7 15 1935 | 9 2 14 | 854 54 6
------------------+------------------+------------------
193 6 19354 | 35 35 7 | 2 8 4
2 87 327 | 4 1 9 | 36 3 5
132 1254 13254 | 3256 8 26 | 1346 7 9here, if a box has a single digit then it means that its value is fixed and if a box has more than one digit then it means that those are the possible values that can be filled in that box.
Now, look closely at the 3x3 square at the top-middle
26 7 8246
1 9 5
32 34 24 According to the game rules, we should have all the digits from 1 to 9 inside a 3x3 square.
If we look closely at the box containing ‘8246’ we can see that it is the only box in that 3x3 square that can have the digit ‘8’ because no other box has that possibility.
so, we can happily fix the digit ‘8’ in that box (because we should have all the digits in a 3x3 square and no other box can have it)
it is not limited to only 3x3 squares. in fact, for a given box we look at all of its three units where one of them is a 3x3 square (the other two are the row and column of that box)
This is simply called the Only Choice method/strategy.
The code looks like this…
After applying the only choice function once to each and every box of the sudoku, this is what we get
5 3 124 | 6 7 8 | 9 1 2
6 7 247 | 1 9 5 | 3 24 8
12 9 8 | 3 4 24 | 5 6 7
------------------+------------------+------------------
8 15 9 | 7 6 14 | 4 2 3
4 2 6 | 8 5 3 | 7 9 1
7 15 3 | 9 2 14 | 8 5 6
------------------+------------------+------------------
9 6 19354 | 35 35 7 | 2 8 4
2 8 7 | 4 1 9 | 6 3 5
132 1254 13254 | 3256 8 26 | 1 7 9But these methods have a major drawback. That is, sometimes no matter how much you eliminate or make the only choice, you can’t reduce the board any further. This is called getting stuck.
Try this board ‘8……….36……7..9.2…5…7…….457…..1…3…1….68..85…1..9….4..’
In fact, that board was claimed to be the world’s hardest sudoku puzzle.
So now we have two challenges to tackle.
- Find out when we get stuck
- What to do after getting stuck
Tackling the first challenge is pretty easy. Just note the board values before and after eliminating and making the only choice. If the values didn’t change then it means we got stuck.
Let's write a simple function to do this
Here, we are initializing a boolean variable stuck to False. Then using a while loop we are checking at each iteration whether the number of fixed(single digit) values on the board are the same before and after applying elimination and only choice strategies. If they are the same then stuck will be True else False.
But there is a catch! Did you notice the if statement at the end of the function? This tells if the sudoku is solvable or not at its current configuration.
The sudoku is unsolvable if at any box there is no possible digit to fix.
Also, don’t be limited to just elimination and only choice. There are plenty of strategies to solve a Sudoku board. Write your favorite strategy as a function and execute it along with the other two.
Finally…
Everything we did until now is also known as constraint propagation.
Constraint Propagation is all about using local constraints in a space (in the case of Sudoku, the constraints of each square) to dramatically reduce the search space. As we enforce each constraint, we see how it introduces new constraints for other parts of the board that can help us further reduce the number of possibilities.
Moving onto the second challenge…
The world’s hardest sudoku puzzle is ‘The World’s Hardest Sudoku Puzzle’ for a reason. That is, you cannot just solve the puzzle using constraint propagation because you will get stuck!
So, I’m going to introduce you to Search. If you studied Data Structures and Algorithms, you might already know what search is! If you don’t, let me explain
Suppose you have a list of groceries that you want to buy from the store. You go to the store and buy the items from the list without following any particular order. After you add them to your cart, you strike off that item from the list. Now, say, you want to know if you added milk to your cart. To find out, you will open your list and look at each item from top to bottom till you find milk and see if it is struck off or not.
That’s linear search in plain English! (because you are searching item by item in a linear fashion)
There are many types of search algorithms, like, linear search, binary search, and so on. Here, we will use Depth First Search.
I won’t go into detail about Depth First Search in this article because it will get very long. But do remember that DFS uses ‘backtracking’ to search
We will use DFS to search the game tree.
But what is a game tree? It's simply a tree of all the possible moves of the game. look at the image below to get an understanding.
Now, coming to the Sudoku puzzle, the main idea behind this is that when we get stuck, we will fix the value of a cell with the least number of possible values (usually two) and expand the game tree in that direction.
We will repeat the above step till we either solve the board or find out that the current configuration is unsolvable. In which case, we backtrack and expand another node.
I know that this is a bit too much to understand. It is also hard for me to explain everything in the text. Maybe a video will be more practical to explain the process.
I will make a video and embed it in this article if I have time.
The code looks like this
Conclusion
And just like that, now you know how to make your own program to solve Sudoku. But most importantly you now know two of the most powerful concepts in Artificial Intelligence — ‘Constraint Propagation’ and ‘Search’.
You can use those two techniques to solve many kinds of problems, like for instance, CryptArithmetic puzzles (I freaking hate them).
Also, follow me if you want to see more articles about data science, machine learning, artificial intelligence and programming in general.
