Step 9 : Play and solve the Sudoku

It is really amazing how it is simple to write a program to find one solution or all the solutions of a Sudoku. Here is the pseudo-code to do it :

Function Find_all_solutions (The_Sudoku)

    look for the first empty square in The_sudoku
    if there is no empty square
          you found a solution
          you can now show, store or print The_Sudoku
    else
          for i = 1 to 9
                if you can place i in the empty square of The_Sudoku
                      place i in the empty square
                      call Find_all_solutions(The_Sudoku)
                      place 0 in the empty square

End of Find_all_solutions

You just have to translate this pseudo-code in Java and it works!

But, this code is not the most performant one. We can improve it a lot, particularly with Dancing Links, or DLX, which is a technique suggested by  the famous Donald Knuth. Here are some very interesting resources concerning this technique :

Dancing links
Knuth's Algorithm X
Exact Cover Matrix

Of course, we implemented this excellent technique in our application.

So, now, you just have to play with your Sudoku. But sometimes, the Sudoku is quite hard. Of course, our application can give one solution. And our application can even  say if they are many solutions. But, asking for the solution does not help to know how to solve a Sudoku. So, why not ask just for a hint? If you do, our application will give you the next number it would play. At this point, you can have one of these reactions :

1. Yes, or course; why did not I find this number myself?
2. Why is this number suggested by the application? You check the Sudoku a little bit more and you get it! Now, you learn rapidly to solve a Sudoku
3. I do not know why the application suggests this number but, at least, I can continue

Here is the screen shown when you press the Hint button. Just try it! You will understand it very fast :

What technique do we use to suggest a number when asked to give a hint, for the lines for example? Very simple . . . as usual! We use the function Find_all_solutions  not for all the Sudoku but rather for just the first line; after, for all the solutions found in the first line, we verify if a number is always in the same square; if yes, we suggest this number. If not, we verify the line 2 up to the line 9. If we do not find any number always in the same square, we  say we do not have any clue for the lines.

You want a hint for the columns? Just press the Columns button. And so on.

Enjoy and amusez-vous bien!

Note : You can store the current Sudoku. It is stored in the external storage in the directory named com.rogerlebo.sudokuvision. Of course, you can  also retrieve a Sudoku you stored previously.