Automatic Sudoku (Number Place) Solver with Digit Recognition and Integer Linear Programming
Sudoku is a logic-based number placement puzzle that consists of 81 cells which are divided into 9 columns, rows and blocks. The goal of this game is to fill out each cells with numbers 1–9 so that there are no repeating numbers in each row, column and blocks.
In this post, I aim to introduce a digit recognition and integer linear programming based automatic sudoku solver that uses the following: Keras (based on the MNIST database [1]) and OpenCV for digit recognition and PuLP for integer linear programming. Also, I plan on detailing out the integer linear programming part and only lightly touch upon the digit recognition and extraction part (image processing)
[1] The MNIST database is a large database of handwritten digits that is commonly used for training various image processing systems. The database is also widely used for training and testing in the field of machine learning.
The rest of this post is organized as follows:
- Digit Extraction with OpenCV & Digit Recognition with Keras
- Formulas and Python3 code with PuLP used for a Sudoku Puzzle Solver
- Digit placement on the image of a Sudoku puzzle
- Testing of the developed solver with a sample Sudoku puzzle
1. Digit Extraction with OpenCV & Digit Recognition with Keras
In this section, I explain the overview of image processing for digit recognition. Below, I have laid out a simple description of the sample code.
- Image processing: Gaussian blur, Thresholding, Resizing for prediction with MNIST based digit recognition model
- Digit Extraction: Based on Contours, crop and warp image
- Digit Recognition: MNIST based digit recognition model (As I used an existing trained model, I won’t provide a sample code for digit recognition modeling.)
2. Formulas and Python3 code with PuLP used for a Sudoku Puzzle Solver
Unlike typical integer linear programming problems, there is no objective function in sudoku puzzles. In this case, we just find a feasible answer which satisfies some given constraints.
The constraints to solving a Sudoku puzzle is that each row, column, and blocks is filled with an integer between 1–9 and that no duplicates exists within each row, column and block. Fig2 shows constraints of sudoku puzzles and we use parameter x with i for columns, j for rows and k for values. In other words, x _(i, j, k) assumes the value of 1, if element (i, j) of the sudoku matrix contains k, and 0 otherwise.
- (1) the constraint on columns
- (2) the constraint on rows
- (3) the constraint on 3 x 3 block
- (4) assures that all the cells of the Sudoku puzzle is filled
- (5) means that where the corresponding sudoku matrix are assumed to equal one.
Based on the above formulas , I wrote a sudoku solving function with PuLP.
4. Digit placement on the image of a Sudoku puzzle
As in section 1, description for details of writing calculated results is omitted.
5. Testing of the developed solver with a sample Sudoku puzzle
In this section, I will test the solver, which was built using functions outlined in Section1~4, on a sample sudoku puzzle. Fig3 shows the sample Sudoku puzzle that I used for testing. Fig4, Fig5, Fig6 shows the code on Jupyter Notebook that I used for recognizing digits from the image of a sudoku puzzle, solving the sudoku puzzle and writing in the calculated results on the original image of the puzzle respectively.
Closing Remarks
In this post, I introduced an automatic Sudoku solver using digit recognition and integer linear programming, However, this is one of many methods for building a sudoku solver and I only chose it from the purpose of mathematical optimization. Hence, I recommend you also implementing other methods for building a sudoku solver!
