Sudoku Introduction
As many of us know Sudoku is a puzzle. The puzzle consists of board with small boxes in rows, columns and sub-boards. Some of the boxes are filled with numbers and others are left empty. The goal of the puzzle is to fill in the empty boxes with numbers with three constraints. The three constraints are:
A number must not repeat in any row.
A number must not repeat in any column.
A number must not repeat in any sub-boards.
Let’s now define row, column and sub-board with an example. Let us consider a board of 9x9 board. The below image shows an example of row, column and sub-board.
These boxes from the above image are partially filled and the goal is to fill the empty boxes.
Solver Introduction
So, Now enough of introduction to sudoku, lets get into the topic. How did I solve sudoku without solving it? Well, to solve a puzzle we definitely need a “solver” that solves the puzzle. So, I decided instead of me being the “solver” why don’t I create a solver. Still puzzled? Don’t be confused, I wrote a “solver” Java program to solve Sudoku puzzle. This is classic programmer move (“Why don’t I write program in 3 weeks to automate a manual task of 3 seconds?”). After all, why did I choose to write solver for Sudoku puzzle? The main reason is I hated solving it and the other reason is I found the problem on leetcode. Having the problem on leetcode makes it easy for me as I shall use leetcode as tool to validate my approach at the end of the article.
I divide that article into 3 parts to solve the problem:
Validation of the board.
Possible values for a box.
Backtracking algorithm.
Validation of the board
When we solve a problem we must be able to validate the final answer. The same goes for the solver program. The program has to validate itself. So, first we shall write the part that validates the Sudoku solution. We shall write the validation part so that it can validate partially filled Sudoku (In the later of the article we can understand the usefulness of it). We validate the rows, columns and sub-boards by checking if there exists a duplicate element. If there exists a duplicate element then we return false (meaning it is not a valid Sudoku). If non of the rows, columns and sub-boards have duplicate element then we return true (meaning it is a valid Sudoku). In case of partially filled board, we skip the validation for empty box.
In order to fill a box we have to find set of numbers that are suitable for the box fulfilling the constraints. Considering the constraints of Sudoku, the possible values for a box is set of numbers that doesn’t exists in its row, column or sub-board. Now, we shall write the Java method that return set of values given the board and Position of the box.
The Position is nothing but a pointer to the box in the board. Since the board is 2 dimensional, the pointer has two values to locate the box. Additional to these two values we shall also encapsulate the set of possible values for the box in the Position as shown below.
The above block of code removes values from set of all values between 1 to 9 if it already exists in either in row, column or sub-board. Since in the above code “getPossibleValues” is encapsulated in Position class, the reference “this” refers to the box at i, j which means position is also a parameter to the method. After removing the existing values we can get a set of possible values for the box at the position of the board.
Backtracking Algorithm
The core part of the Sudoku solver is the Backtracking Algorithm. In a Backtracking algorithm, we take a possible move at a time and continue to solve a problem, but when we find out that the solution cannot be found taking the move, we revert back and try other possible moves iteratively. In our case, initially we find all the positions that are empty and try to fill them with a possible value and continue solving the for next empty positions. Once we find out this possible value was not a good move, we revert back and try other values until we find the solution. If we reach to the solution then we don’t revert the move. We shall now see the code for this below.
In the above code, the algorithm checks if the partially filled board is valid because the possible values are found with the initial state of board. But, as we do modification to the board the possible value may not be a valid move. This adds more optimization to algorithm as we don’t traverse through all the possible values eventhough they are invalid in the current state. Once we completely fill the Sudoku and the solution is valid then we don’t revert the move, else if the Sudoku is not valid, we revert the move.
Evaluation
We shall evaluate the approach with leetcode now.
For the input below.
The following output is generated.
The solution might not be optimized since it was designed to be presentable. Please feel free to share if any optimization can be applied to this approach.
