A couple of years ago, I implemented with the help of Julien Grenier a little program for creating random sudokus and for solving them in an intelligent way. We demonstrated that there was a simple way to solve a Sudoku faster by avoiding the bruteforce solution. Since it worked well, I took a day of the weekend to use this program in my android smartphone.
The android app is quite simple. I use a GridView with an adapter to have a clickable grid. When a cell of the grid is clicked on, an AlertDialog ask the user what number is to be put on that particular cell. When The Sudoku puzzle is copied on the screen, you just click on solve and the algorithm solves the Sudoku. I then just had to add a background image to the GridView and that’s it! See the image I uploaded.
Feel free to ask me if you want the app. As long as it stays OpenSource, I’ll give the code to you!
Now let’s talk about the algorithm for solving the sudoku. Say we start with a two dimensional array representing the Sudoku. Each cell contains a list of the possible values that can take the cell. Then we have a constraints reduction problem. We first tried the bruteforce way by reducing the possible values of each cell by looking at the numbers in the same row, in the same column and in the same region and then by guessing the value of the cell with the least possible values. Sure it works well, but the number of "choices" to make grows exponentially with the complexity of the Sudoku. The more choices that we can make, the longer it can take. So we wanted to go further than that.
Think of what a human do to solve a Sudoku puzzle: It will try to find evidences in the Sudoku that allows him to deduce the value of a particular cell and repeat this action until the puzzle is completed. I make a Chain of Responsibility pattern using multiple strategies found on the web. The algorithm is simple. The first chainlink tries to remove possible values in one or many cell. If it fails, it passes the puzzle to the chainlink below. If it succeeds, we return to the beginning of the chain. If every chainlink fail, then and only then we make an intelligent bruteforce choice by selecting the cell with the minimum possible values.
The strategies I have used are the following ones:
- Simple Constraints Propagation
- Hidden singles
- Naked Pairs
- Naked Triples
- Hidden Pairs
- Hidden Triples
- Pointing Pairs
- Box or Line Reduction
The strategies I wrote have been found on this website. They are explained it great details. I skipped some strategies that were costing more CPU time while not giving the wanted results very often. I have not implemented the "Diabolical Strategies" nor the "Extreme Strategies", since they don’t get used very often and that I wanted to Keep It Simple and Stupid. To bruteforce a choice once in a while will not make the algorithm slower.
Now that I write these lines, I realize that the person that wrote this website also have a sudoku solver for android. But its app costs 4 bucks while mine is free!
Again, if you want the code or only the app, I can give it to you. Just ask and enjoy!