By Michael Smith
How to create a Sudoku Solver?
Well one way to do it is to use an algorithm known as backtracking. I’ve made a Sudoku Solver using the backtracking algorithm and recorded my steps. The solver is written in Visual Basic, but that’s just illustrative – whatever language you use, it will be quite straight-forward to adapt the code.
Backtracking is categorized as a “Brute Force” method to solving a problem, which kind of makes it sound rather crude and cumbersome. It’s not, it’s quite the opposite in my opinion. The key component in backtracking is the use of the recursive function – a programming technique that is far from crude or cumbersome, the recursive function is a rather elegant concept.
To illustrate the beauty of the recursive function, let’s write a function to return a number to the power of n. Imagine, for example, we want the find 3^3. We need the program to calculate:
and return the value of 27.
Of course, a simple c function like this would work:
And such a function works perfectly well and would probably be best – not because the function itself is better than a recursive function, but because it’s very simple to follow the logic, even when revisiting the code a long time after it’s been written. Of course you may be very organised and be in the habit of writing detailed explanatory comments with all your code, but if like me you’re the sort that constantly promises to return to to each function to make detailed comments “after I’ve done this bit” but quite often doesn’t get round to it, then code that flows logically to the naked eye without explanation is best.
Let us now write a recursive function to achieve the same result:
Each instance of the function creates a new instance of itself with the pow variable reducing by 1 each time. By the time pow reaches zero, there are four instances of the function on the stack. The fourth instance returns the value of 1 (as pow==0), the third instance returns the fourth instances return value multiplied by numb – i.e. 1×3=3. The second instance returns the third instances return value multiplied by numb – 3×3=9. And the fourth instance (the original function call) returns the value of 27 – ie 9×3.
And now I present a thousand words:
You see, a recursive function is elegant. Although overkill for the power function, it is absolutely perfect for backtracking.
Yes, yes, Michael, we know all about the recursive function, just get on with the algorithm to solve a Sudoku Puzzle…
…sorry, a backtracking function:
A perfect example of backtracking would be a maze:
You come to a junction and go left. At the next junction you go left left again. You come to a dead-end, you go back to the last junction and go right which also leads to a dead end. You go back two junctions and, this time go right. Eventually you successfully negotiate the maze.
Now onto our Sudoku Solver, it’s just like a maze but with 9 choices at each junction, rather than just two. Assuming we have our Sudoku data recorded in a 9×9 array and there are no clashes when we call the backtrack function, then a flow chart would look like this:
Okay, that probably might be more confusing than it is clarifying. We’ll go through it step by step.
Onto the first video then, give this a watch then I’ll go through it:
Well this first video is pretty simple to follow. A new class for our textboxes is written, as we need to be able to program them to only allowing digit input. A 9×9, two dimensional array named cell is created and used to create 81 sudoku_textbox objects. They are positioned, populated, initialised and a sub-routine named cell_changed is attatched. The cell-changed sub will be used to turn the text of any clashing numbers on rows, columns or boxes red.
First a 9×9 array named grid is created. This will be used for all checking functions and the backtracking function.
The cell_changed sub:
- The cell-changed sub first of all populates the grid array with the corresponding element in the cell array.
- Changes the color of all the text in the boxes to black.
- Check for clashes, if there is a clash then turn the color of the text in the text box to red.
The three checking functions - check_rows, check_columns and check_box – receive the index of the array to be checked and return true if there is not a clash and false if there is a clash.
The clear button is then coded, which is straight-forward.
Okay the first two videos are more about setting up the Sudoku solver in Visual Basic, rather than an explanation of how to code a backtracking function. Part three is where we get to the point.
Show me the beef baby:
We code the solve button to populate the grid array with the contents of the cell array. The backtrack function is then called with the first element of the array - backtrack(0,0). Then the contents of the grid array(which now contains the solved puzzle) is transferred into the cell array, populating the text boxes with the solved puzzle.
The backtrack function:
- First we create a local variable named numbers and set it to 1. This is the variable holding the number to be checked in the current array element.
- If the grid element is empty then populate with numbers variable and check for clashes.
- If there is a clash then the numbers variable is incremented and we try again,if there is no clash then we increase the array index to the next element. If the next element is the 82nd then every box in the puzzle has a none clashing number and the puzzle is solved; we return with a value of TRUE, which invokes all instances of the function to return with a value of true. If we have not reached the 82nd element , we call a new instance of the backtracking function with the new element and return a value of TRUE if the result of the function call is TRUE. If the return value is FALSE then we must try the next number – in the maze analogy we have gone back a junction to try a new route. First of all we take the index to our array back one, as the current value belongs to the next instance of the backtrack function. We then increment the numbers variable and go through the process again – check for clashes, call backtrack…. If the numbers variable reaches 10 then we need to backtrack; we return from the function with a value of FALSE.
- If the grid element is not empty, then we do the same but without trying different numbers. We increase the element, return true if 82nd and call new instance of backtrack if not the 82nd. If the return value of the function call is TRUE then we need to return with a value of TRUE. If the return value of the function call is FALSE then, unlike with the process for the empty elements, we do not need to reduce the element index back, as we will be doing nothing further with this instance of the function other than returning with a value of FALSE. Thus the line: Return backtrack(x,y)
- Finaly, because of the way the cell_changed sub works, we need to create a flag to indicate that we are in the process of backtracking and that the services of the cell_changed sub won’t be needed for the moment.
If you want to download source, get it here: www.icode4u.net/downloads/sudokuVB.zip
And there you go, hope you found it useful. If you’d like an e-mail whenever I post my
narcissistic ramblings interesting articles, then please subscribe to my blog (top of page, right hand panel).
“To part is the lot of all mankind. The world is a scene of constant leave-taking, and the hands that grasp in cordial greeting today, are doomed ere long to unite for the the last time, when the quivering lips pronounce the word – ‘Farewell” - R.M. Ballantyne