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?

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

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
}

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        
}

Answer 4

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

Answer 5

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.

Answer 6

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