Sudoku solver in Java, using backtracking and recursion
I am programming a Sudoku solver in Java for a 9x9 grid.
I have methods for:
printing the grid
initializing the board with given values
testing for conflicts (if same number is in same line or 3x3 sub-grid)
a method to place the digits, one by one, which requires the most work.
Before I go into detail with that method, keep in mind that I have to use recursion to solve it, as well as backtracking (watch the applet here as an example http://www.heimetli.ch/ffh/simplifiedsudoku.html )
Also, I am solving this Sudoku by moving vertically downwards, starting from the top left, through the first column, and then through the second column, etc.
So far, I have the following:
public boolean placeNumber(int column){
if (column == SUDOKU_SIZE){ // we have went through all the columns, game is over
return true;
}
else
{
int row=0; //takes you to the top of the row each time
while (row < SUDOKU_SIZE) loops through the column downwards, one by one
{
if (puzzle[row][column]==0){ //skips any entries already in there (the given values)
puzzle[row][column]=1; //starts with one
while(conflictsTest(row,column)){ //conflictsTest is the method I wrote, which checks if the given parameters are in conflict with another number
puzzle[row][column] += 1;
}
//BACK TRACKING
placeNumber(column); //recursive call
}
else{
row++; // row already has a number given, so skip it
}
}
column++; // move on to second column
placeNumber(column);
}
return false; // no solutions to this puzzle
}
Where I labeled BACKTRACKING is where I believe the remainder of my code needs to go.
I thought up of something along the lines of:
- if the value is 10, set that value back to zero, go back a row, and increment that value by 1
That backtracking 'strategy' doesn't exactly work for several reasons:
what if the previous row, was a given value (aka I'm not supposed to increment it or touch it, but instead, go back to the last value that I placed there)
what if the previous value was a 9. and if I incremented that by 1, now we're at 10, which won't work.
Can someone please help me out?
Answer
I do not know how you're going to solve the sudoku, but even if you use the brute force method (and so it sounds to me what you describe) you should consider that your data structure is not appropriate.
With that I mean that every cell should not just be a number, but a set of numbers (that may be possibly placed there).
Hence, the given numbers will be represented as singleton sets, while the empty ones you can initialize with {1,2,3,4,5,6,7,8,9}. And then the goal is to reduce the non-singleton cells until all cells are singletons.
(Note that, while solving a sudoku with pencil and paper, one often writes small numbers in the blank cells to keep track of what numbers are possible there, as far as one has solved it.)
And then, when "trying the next number" you take the next number from the set. Given cells have no next number, so you can't change them. This way, the difficulties you describe vanish (a bit, at least).
------ EDIT, AFTER HAVING LEARNED THAT BRUTE FORCE IS REQUIRED.
Your teacher obviously wants to teach you the wonders of recursion. Very good!
In that case, we just need to know which cells are given, and which are not.
A particular easy way that could be used here is to place a 0 in any non-given cell, as given cells are by definition one of 1,2,3,4,5,6,7,8,9.
Now lets think about how to make the recursive brute force working.
We have the goal to solve a sudoku with n empty cells. If we had a function that would solve a sudoku with n-1 empty cells (or signal that it is not solvable), then this task would be easy:
let c be some empty cell.
let f be the function that solves a sudoku with one empty cell less.
for i in 1..9
check if i can be placed in c without conflict
if not continue with next i
place i in c
if f() == SOLVED then return SOLVED
return NOTSOLVABLE
This pseudo code picks some empty cell, and then tries all numbers that fit there. Because a sudoku has - by definition - only a single solution, there are only the following cases:
- we picked the correct number. Then f() will find the rest of the solution and return SOLVED.
- we picked a wrong number: f() will signal that the sudoku is not solvable with that wrong number in our cell.
- we checked all numbers, but no one was correct: Then we have got an unsolvable sudoku ourselves and we signal this to our caller.
Needless to say, the algorithm rests on the assumption that we only ever place numbers that are not
conflicting with the current state. For example, we do not place a 9 there when in the same row, column or box there is already a 9.
If we now think about how our mysterious, yet unknown function f() looks like, it turns out that it will be almost the same as what we already have!
The only case we have not yet considered is a sudoku with 0 empty cells. This means, if we find that there are no more empty cells, we know that we have just solved the sudoku and return just SOLVED.
This is the common trick when writing a recursive function that is supposed to solve a problem. We We are writing solve(), and we know, that the problem is solvable at all. Hence, we can already use the function we are just writing as long as we make sure that with every recursion, the problem somehow gets closer to the solution. At the end, we reach the so called base case, where we can give the solution without further recursion.
In our case we know that Sudoku is solvable, moreover, we know it has exactly one solution. By placing a piece in an empty cell, we come closer to the solution (or to the diagnosis that there is none) and give the new, smaller problem recursively to the function we are just writing. The base case is the "Sudoku with 0 empty cells" which actually is the solution.
(Things get a bit more complicated if there are many possible solutions, but we leave that for the next lesson.)