Sudoku

Many of us would have solved Sudoku ranging across different levels. I got to see Sudoku problems for the very first time in a newspaper back in 2005 when I was in high school. I used to solve them regularly back then but became an infrequent Sudoku solver later and I haven't solved a Sudoku problem in past few years now. During my conversation with an old friend recently, he gave me the problem of solving a Sudoku solver program itself. Here is the set of steps that I worked on in order to come up with a solution:

Initial Setup

Initially we get a 2D matrix input where some values are pre-filled already (rest are set to 0). These values can range between 1 and the size of the matrix (number of rows or columns, since it is a square matrix). A Python program reads an input text file of testcases and constructs the string argument and sends it to the compiled Java code.

Row and Column checkers

This is for the validity of existence of a value in a particular grid which translates into (i, j) index of a 2D matrix. The row checker checks whether the value under consideration is already present in any of the columns of a particular row index i whereas the column checker checks all the rows of a column indexed at j. This is the code snippet to support these checks (click on the image for enlarged view):

Finding a grid to check for a value

This step is for finding a grid (i, j) where we put a value and proceed further. Here we first search for the value 0 and if found we take a value in range 1 through size of the matrix, verify its validity in that particular row and column as in the above section then put that value in the grid and move to another grid. For this to happen we need to iterate over all the grids hence a nested loop is needed. Since these operations like searching a grid having the value 0, validating a probable value to be put in that grid, looking for another subsequent grid(s), etc. keep happening repeatedly, hence we need to have them in one block and in a recursive method. Please check the method isSolutionPossible() in the GitHub reference link provided below for the relevant codes. We are taking the current state of the matrix as input to this method for further recursive calls as the next set of values need to be applied on the current and further set of corresponding matrix states.

Construction of the input matrix

The main() method takes the string args array as input, parses it and constructs the initial state of the matrix. It then initiates the recursive method call to check whether a solution is possible with the initial state of the matrix as input along with its size. If yes, then it prints the final state matrix which is a solution to the given Sudoku problem. Before returning the final state of the matrix, a final uniqueness check is done to counter the testcases of all-filled matrix already provided.

Resources:

1. Code repository:    https://github.com/pyav/Sudoku