Solving Sudoku with Simple Data Science Tricks
Recently, I became interested in a logic based puzzle Sudoku. It is kind of like the crossword puzzle where one needs to fill in the missing part with certain constraints. Unlike the crossword puzzle, only numbers from 1 to 9 are played. Sudoku is a 9 x 9 grid puzzle, with nine 3 x 3 blocks, completing the puzzle means all the missing digits need to be filled in so that each row would have 9 unique numbers, as well as each column and block. Playing Sudoku requires one to keep track of what is known, what is unknown, and make a move each time to fill in the unknowns. Depending on how obvious the unknown could be derived, the puzzle usually has three different difficulty levels: easy, medium, and hard.
As a data scientist, naturally I start thinking about if I can use simple programming to find the solution quickly.
I first tried writing a program that mimics how humans play Sudoku - we tend to fill in the obvious solutions first so that the search space of uncertainties could be limited. In Python, we can create a dictionary with each key as a (row, col) coordinate indicating the position needs to be filled, the associated value(s) to the key is the valid possible digits to choose from based on the current puzzle setup. Of course, this program would only tackle some of the easiest puzzles since it doesn’t know how to make a decision with uncertainties.
Next, I accumulated all left over valid potential solutions at the current configuration for each position, and made a combinatorial list so that the computer can evaluate them one by one. For example, if position1 can be either 1 or 2, and position2 can be either 8 or 9, it is going to try 4 solutions: (1,8), (1,9), (2,8), (2,9). The problem is that the search space is still too big (after 1 day on my M1 Macbook pro, it is still running).
Then I came across a famous computer science algorithm called backtracking, which is a perfect classic solution for puzzles like this. Instead of filling numbers with obvious solutions, the vanilla version of this algorithm sequentially fills in the missing pieces by sequentially trying all possible digits in a cell. In each attempt, it accepts the possible solution if it’s valid and moves on to the next cell, if there is no possible solution found in the next cell, the program will trace back to the previous cell and eliminate the digit that leads to the dead-end solution. The program continues in this fashion until it is able to fill in the entire board with digits, otherwise, it goes back to the first uncertainty position and eliminates the answer that has been tested and try the next valid new answer. It is guaranteed to find a solution, however, it could be slow based on how many numbers to be filled in.
I compared the two methods mentioned above with an easy Sudoku, an extremely difficult Sudoku, and an average difficult Sudoku and wrote a report here.
In my next blog post, I will write about my attempts in using machine learning to solve Sudoku.
Other reading: