Developing a Sudoku solver
I've never been great at solving Sudoku because I find it boring to sit down for an hour staring at boxes some filled and others to be filled with numbers. But I think it's an interesting game. I've always thought of developing an algorithm to solve any given Sudoku puzzle. I've had this in my mind from the very first year of my under graduation but I never gave it a serious thought. If you have seen my previous post, it's about backtracking which is a general algorithm used to solve many problems such as the classical N-Queens problem(I've solved it in that post). Yesterday I tried solving a question on the Hackerrank site which required me to use the backtracking algorithm and I was successful in devising an algorithm to solve it. I felt the question was very similar to solving a Sudoku puzzle so I thought of creating a sudoku solver and I've done it! It was simpler than what I thought it would be. All you need to know is how to use backtracking. If you don't know what backtracking is, just have a look at my previous post and I hope it'd help you.
Here's a video of me solving a Sudoku puzzle at 'Evil' mode using the Sudoku solver I developed. Hope you enjoy it.
Now coming back to Sudoku solver, I've not taken the time to see any other algorithm so this is my own approach to the problem and I think it's pretty straight forward and easy to understand. To solve the Sudoku I'll be using these methods:
- canPlace(): This function is used to check whether we can place a particular value at a particular position in the Sudoku.
- solveSudoku(): This function uses backtracking and canPlace() method to solve the Sudoku. If the given Sudoku does not have a solution, it returns false.
- displayBoard(): A simple function to display the numbers of a Sudoku puzzle(a box) which is simply a 2-Dimensional array.
- insertNumbers(): A function to insert numbers into the Sudoku before it gets solved. You are required to mention row number, column number and value for each entry.
- insertFileNumbers(): This function is used to read the Sudoku entries from a mentioned file. To fill a sudoku having N*N boxes, the text must have N*N lines. The first line denotes the number at the first row and first column. The second line represents value at the first row and second column (and) so on. For not mentioning any value, you can leave the line empty or insert any non-number string.
The main logic only depends on the first two functions mentioned which are canPlace() and solveSudoku(). Both of these functions are Boolean returning functions. here are the algorithms for these functions:
- canPlace() function algorithm:
- solveSudoku() function algorithm:
I hope the above algorithms are clear enough to help you understand the logic behind Sudoku solver. Here's the code for java implementation of Sudoku solver with all of the five methods mentioned above along with the main() function.
I know this can be further developed into a good application but my intention of developing the program wasn't that. I just wanted to devise an algorithm to solve any given valid Sudoku puzzle.