It is always interesting how we can get a machine to perform activities which require human thinking. No I am not talking about Artificial Intelligence! Not in the current post at least. What I have tried to do is get a piece of computer code to solve a Sudoku puzzle using a logic that we humans commonly use to solve a Sudoku.
Now before we get there, let’s go over some facts about the game itself. Did you know, Sudoku has been around for more quite sometime? French newspapers featured variations of the Sudoku puzzles dating back in the 19th century! Since then the puzzle had re-appeared again in 1979 in puzzle books under the name Number Place. However, modern sudoku was popularized when a Japanese puzzle company Nikoli published it the under the name Sudoku, which meant single number.
With gaining popularity over the last few years, a world Sudoku Championship is being held every year. Of the 13 championships held so far, Kota Morinishi of Japan has been the most successful winner with four individual titles and Thomas Snyder of United States has won three. Thomas Snyder also has the Guinness World Record for solving a “Very Easy” difficulty Sudoku puzzle in 1 minute 23.93 seconds.
Now we will see if our logic and computation efficiency of a commonly used coding language on a home laptop can beat that!
There are quite a few commonly used computer algorithms to solve Sudoku from Backtracking to Dancing links. Here we will explore the Backtracking approach since that is very similar to how we would solve.
Backtracking like the name suggests relies on trying a possible value on a given cell of the Sudoku and then trying to fill the rest of the puzzle. If we encounter an issue, it means the value we guessed was not right. We then try and pick another value and then try to fill the puzzle. This is exactly how I have always tried to solve a Sudoku puzzle.
Let’s go over that in few steps-
- Determine possible options
we decide what possible values a cell could take. This would depend on the values various other cells carry in the same row, column or block.
There are many ways to do this. One such commonly used method is called naked single, where (for example) if value 3 is already filled in a row, then 3 would not a possible option in any of the other cells in that row - Perform temporary assignment
temporarily assign one of the possible values for a cell - Evaluate
understand if the assigned value is right. One way to do that is by filling the rest of the puzzle, updating the possible options for rest of the cells. Sometimes you’ll find that the temporary assignment is not right because due to this some other cell lost all its possible options. If you don’t find any issue, then do step #2 and #3 again for another cell - Repeat
repeat 1 to 3 till all cells are filled
Obviously there are some nuances which I am purposely not delving here. But the basic premise is as mentioned.
Let’s first create a sudoku representation. Here I have used an array with 81 elements. Each element representing a certain cell of the sudoku. Each cell will be initialized with 9 values representing the 9 possible values it could take.
Given that some of the cell values (or most depending on the difficulty level) are filled before we start and during the course. We need a way to keep a tab of what values a cell could take.
The way I have approached this problem is by finding out what cells are already filled in that particular cell’s row, column and box. I have defined three arrays (one for row, column and box) which can track the list of values that have already been filled (I refer to them as exclusions).
Once we know that, the remaining numbers between 1 to 9 would be the possible values each cell can take. So let’s update the rest of the cells based on the exclusions mentioned. For this we use two functions
- one to find out how many cells in the array is filled
- second to update the array based on exclusions
We let the second function run on a recurring loop so that we keep updating the rules as more cells get filled.
Now that the base is set, it is time for us to try out few options on each cell. But since a particular assignment can go wrong, we need to keep the previous iterations in-tact so that we can revert as required.
Now we evaluate if an assignment is right. The only way to find out is assume that is right and continue to fill the entire array. If we face an issue, then we know that the assignment is incorrect. If we notice it is indeed incorrect, we go back and drop that value from the options within the cell value. Else, if we don’t encounter an issue, we go ahead and perform more assignments. Sometimes we encounter an issue only after two or three assignments later.
Now all that is left is running these steps in a recursive fashion
The entire code can be found in git here https://github.com/thilakghub/sudokusolver/blob/master/solver.py
Below is a difficulty level Expert puzzle and following that is the solution being iterated.
A Sudoku puzzle with as little as 17 clues can probably be the hardest. There are proofs that a 16 clue puzzle is not possible. So when I tried our algorithm for few 17 clue puzzles, it could solve most puzzles in under one second!
Now is this the best option for solving a Sudoku- probably not. But it performs fairly well. There are better solutions shared on Stack Exchange which seems to be solving not one but around 49,000 puzzles in less than 10 seconds! https://codegolf.stackexchange.com/questions/190727/the-fastest-sudoku-solver
The choice of technique, optimal use of memory, programming language and ability to parallelize could further improve the run time. But that is for another day.
