You might be familiar with Sudoku. It is a logical puzzle appearing in the puzzles section of most newspapers. The newspaper is the first place where I encountered this puzzle while I was in school and it took me days to solve my first Sudoku puzzle. Later in college, I learned about Constraint Satisfaction Problems (CSP) while taking a course on A.I., I found out that CSP could be applied to the Sudoku puzzle. In this blog post, we’ll explore How Sudoku can be modelled as a CSP and I’ll walk you through my implementation of the Algorithm in Golang. You can play with the live demo here.
Rules of Sudoku puzzle:
The objective is to fill a 9×9 grid with digits, so that each column, each row, and each of the nine 3×3 subgrids that compose the grid (also called “boxes”, “blocks”, or “regions”) contain all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which for a well-posed puzzle has a single solution. -(Wikipedia)
A fun fact about Sudoku puzzles is that there need to be at least 17 clues present in the puzzle in order to get a unique solution. Here is a Numberphile video related to this fact please do watch it.
Simple Sudoku puzzles can be solved by using a brute force approach of trying out every possible number in every empty cell using Backtracking. But this solution is not a scalable solution for Moderate and Hard puzzles. It has been established that approximately 5.96 x 11^26 final grids exist, but trying all of them out is going to take a long time, more than 13 billion years! So in order to solve very hard Sudoku puzzles within reasonable time constraints, we need intelligent algorithms.
For the A.I. course that I took the recommended textbook was Artificial Intelligence: A Modern Approach written by the great Peter Norvig – a very influential figure in the field of A.I., I regret that I had not referred to the entire textbook, I but a few parts here and there. While in college, I found this blog – Solving Every Sudoku Puzzle by Peter Norvig. I read the blog and I could understand only the key ideas, I could not follow along with the whole blog back then, but I had understood enough to implement my own Sudoku solver. In the blog, Peter Norvig shares his implementation and algorithm. The code that he has written is pure gold, very efficient, clear and concise!
What are Constraint Satisfaction Problems?
The mathematical definition of CSPs is boring, full of symbols and notations, and difficult to explain, So I’m not going to try to explain it in a mathematical way, you can refer Wikipedia or the book I mentioned above. CSP techniques can be applied to problems whose search space causes a combinatorial explosion, meaning as you move one step further in solving the problem the number of possible solution states exponentially increase. By applying CSP techniques I mean, enforcing strong limitations or constraints on the problem, by doing so, the invalid solution in the solution space gets eliminated quite early in the exploration process. There are two main exploration / exhaustive search techniques or used to explore a search space i.e. Breadth-First-Search (BFS) and Depth First Search (DFS) there are many more techniques like A* search, but they are in some way derivatives of BFS or DFS.
In the real world, it is difficult to enforce strong limitations on the problem and still keep the problem sensible, meaning as you enforce strong constraints on the problem, you also need to maintain the original problem you are solving and if the constraints you apply the problem are not strong the solution may not converge during the search phase. This is it what makes AI difficult/hard.
To search for the solution I have used DFS, since BFS tries to be more exhaustive by exploring more solutions early on, but if the solution is deep in the search space it will take more time to converge and we would have explored many non-solution states. By using DFS I’m making some assumptions early on in the search process and thereby eliminating obvious non-solution states.
Enough with the theory, let’s play with some code!
func solve(grid [9][9]uint8, possibilitiesGrid *[9][9][]uint8) ([9][9]uint8, bool) {
emptyX, emptyY := SudokuUtils.FindBlankCell(&grid)
if emptyX >= 0 && emptyY >= 0 {
for _, possibility := range (*possibilitiesGrid)[emptyX][emptyY] {
grid[emptyX][emptyY] = possibility
newPossibilitiesGrid := eliminatePossiblities(emptyX, emptyY, &grid, copyPossibilitiesGrid(possibilitiesGrid))
newGrid, solved := solve(grid, newPossibilitiesGrid)
if solved {
return newGrid, true
}
}
} else {
return grid, true
}
return grid, false
}
func Solve(puzzle string) (string, bool) {
grid := SudokuIO.ParsePuzzel(puzzle)
possibilitiesGrid := generatePossibilitiesForBlankCells(&grid)
grid, possibilitiesGrid = eliminateObviousPossibilitesFromPosssibilitiesGrid(&grid, &possibilitiesGrid)
grid, _ = solve(grid, &possibilitiesGrid)
if verbose {
SudokuIO.PrintPuzzle(&grid)
}
return SudokuIO.StringifyPuzzle(&grid), true
}
The algorithm that I have used is actually very simple-
- First, we parse the string representation of the puzzle to a grid representation.
- Then we generate the valid possibilities for blank cells.
- We then eliminate the obvious possibilities by checking the row, column and 3×3 box.
At this stage, we would have narrowed down our solution space by applying the constraints. - Now we perform the search phase, as I have mentioned above, I’m using DFS.
I have run some benchmarks using the world’s hardest Sudoku puzzle. I have used two configurations of machines C1 and C2, I’m only considering the processor family and amount of RAM for the benchmarks.
C1: AMD A8 Processor, 4 GB RAM
C2: Intel i5 Processor, 16 GB RAM
There are 3 versions of the program I have written.
- A very naive implementation in python, I had written it 2 years ago (while still in college). Let’s call it I1
- A refactored Implementation in python was written some months back. Let’s call it I2
- A Golang implementation which runs very fast. Let’s call it I3
Benchmarks:1. Comparing I1 running on C1 and C2:
- C1: 45.27 seconds (Too slow)
- C2: 12.81 seconds
2. Comparing I2 running on C1 and C2:
- C1: 5.62 seconds
- C2: 1.66 seconds
3. Comparing I3 running on C1 and C2:
- C1: 382.01 milliseconds
- C2: 152.46 milliseconds (Too fast)
Just to digress for a little bit, the final version of code that I have written is typesafe, meaning the code is written in statically typed languages, The front-end is written in TypeScript + React and the back-end is written in Go. Types are awesome they save you from a lot of careless bugs that you could introduce when using dynamically typed languages.
You can find the details of the Go API here (APIDOCS). I have made a very minimalistic client, If you don’t like it make your own client using the APIs exposed. I have hosted the Go API on Heroku (Free) and for caching I’m using Redis hosted on Redislabs(Free), Thanks to services like Heroku and RedisLabs freeloaders like me can deploy our apps 😛
If you reached this far, thanks for reading. I hope this blog post was not too boring.
~~~~ Happy Sudoku Solving ~~~~
References and Resources:
