Sudoku solver in Java, using backtracking and recursion

Question

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:

1. 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)

2. 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?

Rutland

+1 for wanting to learn, and not just wanting to be fed code. – Naima

+1 from me for the same reason. But you know what? I bet, there will be code nevertheless. Some people just can't resist. – Delila

Answer 1

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.)

Delila

Yes, I am using a brute force method, as is required by the assignment requirements. And the reason I chose this data structure, was because of a similar example that was in my textbook. We were told that we could implement our own solution, or use the one in the textbook as a starting place. The example in the textbook I am referring to is a backtracking, recursive solution to the '8 queens' problem, which is slightly different than implementing sudoku – Rutland

Well, in this case, you don't need a set, but maybe just a flag that tells you if the cell was given or not. – Delila

Do you have any advice or hints on how such a flag could be implemented? – Rutland

Thank you for the quick response. I'm gonna re-read it and let it sink it, before I get back to my code – Rutland

The pseudocode is wonderful, thank you. After where you placed your code, you brought up the three different case scenerios that could happen, which reminded me of another part of the assignment that I had forgotten about. My assignment states: – Rutland

"Implement a recursive solution that employs backtracking to determine, for a given Sudoku puzzle, whether the puzzle only has one unique solution. That requires you to read in a given puzzle, and solve it. Once you found one solution, you are not necessarily done, but you need to continue to explore for further solutions. At the end, one of three possible outcomes should be reported: the puzzle is not solvable at all, the puzzle has a unique solution, or the puzzle has multiple solutions. " How would I go on about continuing to solve all possible puzzles? – Rutland

lol "Things get a bit more complicated if there are many possible solutions, but we leave that for the next lesson." Thank you for your time, your explanation has enlightened me to other ways of looking at this problem, rather than my original program. Please describe what would be different if we were to solve it for multiple solutions. – Rutland

I would replace the return type of our solver with a number that gives the number of solutions found. In the trivial case, return 1. In all other cases, return the sum of the recursive results. (Don't try that with an empty board, unless you're about to go on vacation for some weeks.) Things would get more complicated if we had to keep all solutions (rather than just their number). – Delila

Unfortunately, we are required to print out all solutions (including none, or one, or many). We have been provided with 2 sudoku's to test our code on, one of which has exactly 1 answer, and the other which has 400 answers. We are expected to solve all 400 and print them out. :( – Rutland

Printing is not an issue (in Java, that is). There is only one place (the trivial case), where you have a solution. Just print it before returning 1. If we had to keept it, we would have to maintain a list or some container, and copy things around. But with this requirement, it doesn't get that complicated. Print it, and forget it. (If I were your teacher, I would give extra credit for printing the number of solutions first, followed by the solutions themselves.) – Delila

Answer 2

Firstly, a suggestion for optimization: While checking whether, the number you're going to put in a cell, is already present in the same row, column or minigrid, you don't have to run a loop or something like that. You can perform an instant check by array indexing.

Consider 3 9x9 boolean double dimensional arrays:

boolean row[9][9], col[9][9], minigrid[9][9]

We'll be using the first array for checking whether a number is present in the same row, the second array for checking if a number is present in the same column, and the third for the mini grid.

Supposing you want to put a number n in your cell i, j. You will check if row[i][n-1] is true. If yes, then i^th row already contains n. Similarly, you will check if col[j][n-1] and minigrid[gridnum][n-1] is true.

Here gridnum is the index of mini grid, where the cell you want to insert a number, lies in. To calculate mini grid number for cell i,j, divide i & j by 3, multiply the integral part of former with 3, and add it to the integral part of the latter.

This how it looks:

gridnum = (i/3)*3 + j/3

By looking at values of i/3 and j/3 for all i and j, you will get an idea of how this works. Also, if you put a number in a cell, update the arrays too. E.g. row[i][n-1] = true

If there is a part you don't understand, post a comment and I'll edit my answer to explain it.

Secondly, using recursion & backtracking to solve this is pretty easy.

boolean F( i, j) // invoke this function with i = j = 0
{
If i > 8: return true // solved

for n in 1..9
 {
 check if n exists in row, column, or mini grid by the method I described

 if it does: pass ( skip this iteration )

 if it doesn't
  {
   grid[i][j] = n
   update row[][], col[][], minigrid[][]

   if F( if j is 8 then i+1 else i, if j is 8 then 0 else j+1 ) return true // solved
  }
 }
 return false // no number could be entered in cell i,j
}

Libbie

Answer 3

i suggest passing both the current row and column to the recursive method then find all allowed numbers for THAT cell, for each allowed number recursivly call the method for the next column (or next row if at last column) and undo the move if it leads to a dead track

public boolean fillCell(int r, int c) {
    if last row and last cell {
        //report success
        return true
    }
    for i 1 to 9 {
        if can place i on r, c {
            board[r][c] = i
            if !fillCell(next empty row, next empty column) { //DONT change r or c here or you will not be able to undo the move
                board[r][c] = 0
            }
            /*
            else {
                return true; //returning true here will make it stop after 1 solution is found, doing nothing will keep looking for other solutions also
            }
            */

        }
    }
    return false        
}

Eft

Answer 4

I would check each cell and go back a recursion step if no solution can be found.

In more detail: Go to next cell, if value x == 0, check if x+1 would be valid, if true, go to next cell by calling the method recursively with the next possible cell. If the number is not valid check x+2 etc. if no number is valid return false and repeat the x+1 step in the previous call. If you hit a cell with a number inside, do not call the recursion but directly go to the next, thus you need not to flag any pre entered cells.

Pseudo code:

fillcell cell
 while cell is not 0
  cell = next cell
 while cell value < 10
  increase cell value by one
  if cell is valid 
    if fillcell next cell is true
      return true
return false

Not sure if this correct but it should show the idea.

Britney

Answer 5

some ideas that might be helpful (concerning recursion and backtracking)

//some attributes you might need for storing e.g. the configuration to track back to.

boolean legal(Configuration configuration) {

}

int partSolution(Configuration configuration) {
  if (legal(configuration))
    return partSolution(nextConfiguration())
  else
    return partSolution(previousConfiguration())    
}

Configuration nextConfiguration() {
 //based on the current configuration and the previous tried ones,
 //return the next possible configuration:
 //next number to enter, next cell to visit
}

Configuration previousConfiguration() {
 //backtrack
}

solve () {
  call partSolution with start configuration while partSolution < 9x9
}

write a Configuration class that holds the grid with the entered numbers and some other attributes like the size and #numbers entered and think about what else is needed

Windmill

Answer 6

The other answers on this page have covered Backtracking Algorithm. Interestingly, with just a bit optimization, you can improve this backtracking algorithm significantly. The idea is to use Greedy Best-First Search: Instead of picking the 'next' cell top to bottom, left to right, you pick the next cell as the cell with the least number of possibilities.

For example, if the row containing that cell has already had number 1 2 3, the column's had 4 5 6, and the 3x3 block's had 7, then there are only 2 possibilities left: 8 and 9. This looks like a pretty good cell to pick.

This improvement speeds up the program quite a bit and makes the program run fast enough for my Real-time Sudoku Solver

You can check out the animation of this algorithm here.

Link to Visualizer Code and Real-time Solver Code

The code for Greedy Best First Search is below:

# Keep data about the "Best" cell
class EntryData:
    def __init__(self, r, c, n):
        self.row = r
        self.col = c
        self.choices = n

    def set_data(self, r, c, n):
        self.row = r
        self.col = c
        self.choices = n

# Solve Sudoku using Best-first search
def solve_sudoku(matrix):
    cont = [True]
    # See if it is even possible to have a solution
    for i in range(9):
        for j in range(9):
            if not can_be_correct(matrix, i, j): # If it is not possible, stop
                return
    sudoku_helper(matrix, cont) # Otherwise try to solve the Sudoku puzzle

# Helper function - The heart of Best First Search
def sudoku_helper(matrix, cont):
    if not cont[0]: # Stopping point 1
        return

    # Find the best entry (The one with the least possibilities)
    best_candidate = EntryData(-1, -1, 100)
    for i in range(9):
        for j in range(9):
            if matrix[i][j] == 0: # If it is unfilled
                num_choices = count_choices(matrix, i, j)
                if best_candidate.choices > num_choices:
                    best_candidate.set_data(i, j, num_choices)

    # If didn't find any choices, it means...
    if best_candidate.choices == 100: # Has filled all board, Best-First Search done! Note, whether we have a solution or not depends on whether all Board is non-zero
        cont[0] = False # Set the flag so that the rest of the recursive calls can stop at "stopping points"
        return

    row = best_candidate.row
    col = best_candidate.col

    # If found the best candidate, try to fill 1-9
    for j in range(1, 10):
        if not cont[0]: # Stopping point 2
            return

        matrix[row][col] = j

        if can_be_correct(matrix, row, col):
            sudoku_helper(matrix, cont)

    if not cont[0]: # Stopping point 3
        return
    matrix[row][col] = 0 # Backtrack, mark the current cell empty again
            

# Count the number of choices haven't been used
def count_choices(matrix, i, j):
    can_pick = [True,True,True,True,True,True,True,True,True,True]; # From 0 to 9 - drop 0
    
    # Check row
    for k in range(9):
        can_pick[matrix[i][k]] = False

    # Check col
    for k in range(9):
        can_pick[matrix[k][j]] = False;

    # Check 3x3 square
    r = i // 3
    c = j // 3
    for row in range(r*3, r*3+3):
        for col in range(c*3, c*3+3):
            can_pick[matrix[row][col]] = False

    # Count
    count = 0
    for k in range(1, 10):  # 1 to 9
        if can_pick[k]:
            count += 1

    return count

# Return true if the current cell doesn't create any violation
def can_be_correct(matrix, row, col):
    
    # Check row
    for c in range(9):
        if matrix[row][col] != 0 and col != c and matrix[row][col] == matrix[row][c]:
            return False

    # Check column
    for r in range(9):
        if matrix[row][col] != 0 and row != r and matrix[row][col] == matrix[r][col]:
            return False

    # Check 3x3 square
    r = row // 3
    c = col // 3
    for i in range(r*3, r*3+3):
        for j in range(c*3, c*3+3):
            if row != i and col != j and matrix[i][j] != 0 and matrix[i][j] == matrix[row][col]:
                return False
    
    return True

# Return true if the whole board has been occupied by some non-zero number
# If this happens, the current board is the solution to the original Sudoku
def all_board_non_zero(matrix):
    for i in range(9):
        for j in range(9):
            if matrix[i][j] == 0:
                return False
    return True

Buford