Sudoku Solver

Patrick Leaton
Published: Dec. 5, 2021, 8:17 p.m.
Problem Description

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

  1. Each of the digits 1-9 must occur exactly once in each row.
  2. Each of the digits 1-9 must occur exactly once in each column.
  3. Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

The '.' character indicates empty cells.

 

Example 1:

Input: board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
Output: [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
Explanation: The input board is shown above and the only valid solution is shown below:

 

Constraints:

  • board.length == 9
  • board[i].length == 9
  • board[i][j] is a digit or '.'.
  • It is guaranteed that the input board has only one solution.

 

The description was taken from https://leetcode.com/problems/sudoku-solver/.

Problem Solution

#(9^N^2) Time, O(N^2) Space
#Complexities are estimated since this problem is NP-Complete
class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        n = 9
        rows, cols, squares = {}, {}, {}
        for row in range(n):
            for col in range(n):
                value = board[row][col]
                square = (row//3, col//3)
                if row not in rows:
                    rows[row] = set()
                if col not in cols:
                    cols[col] = set()
                if square not in squares:
                    squares[square] = set()
                rows[row].add(value)
                cols[col].add(value)
                squares[square].add(value)
       
        def valid_spot(row:int, col:int, square:tuple, value:int) -> bool:
            if value in cols[col] or value in rows[row] or value in squares[square]:
                return False
            return True
       
        def backtrack(row:int, col:int) -> bool:
            if (row, col) == (n-1, n):
                return True
            if col == n:
                row, col = row+1, 0
            if board[row][col] != ".":
                return backtrack(row, col+1)
            for i in range(1, n+1):
                value = str(i)
                square = (row//3, col//3)
                if valid_spot(row, col, square, value):
                    board[row][col] = value
                    rows[row].add(value)
                    cols[col].add(value)
                    squares[square].add(value)
                    if backtrack(row, col+1):
                        return True
                    board[row][col] = "."
                    rows[row].remove(value)
                    cols[col].remove(value)
                    squares[square].remove(value)

        backtrack(0, 0)

 

Problem Explanation

In the previous problem, Valid Sudoku, we were just required to validate that a Sudoku board was valid based on the following three constraints:

  1. The same element doesn't occur more than once in any given row.

  2. The same element doesn't occur more than once in any given square.

  3. The same element doesn't occur more than once in any given 3X3 sub-matrix.

On top of these constraints, each element is within the range of [1,9]. We didn't have to validate that though in the previous question, nor do we in this question.

 

Here, we are actually required to fill in the board.  

What makes this task difficult is we know if we have made an immediate wrong placement based on the three constraints previously listed, but we won't know until further down the line whether we made a wrong placement in the past.  With that, we need to give ourselves some flexibility to backtrack on wrong choices so that we can switch them out with different number placements that may lead to a valid fill of the board.

This will be the same idea as the N-Queens problem except here we will only have one combination as stated in the constraints.  The approach will be very similar though. 

To solve this, we will first need to take inventory of the numbers that are already on the board given to us so that we know what our baseline is.  We'll do this by making an initial scan and placing each value within their appropriate row, column, and square HashMaps/HashSets.  From there, we will create a recursive backtrack function that we will use for attempting to place each number within each empty cell until we have filled the last cell of the board.

A general template for backtracking problems is to consider a placement based on whether it would be valid, if so, make the placement and continue down the Depth-First Search path with that placement made, and if that placement didn't lead to an answer or didn't lead to every combination then backtrack by reverting the placement. 

Let's start by writing the length and width of the board to the variable n, so that we don't have to keep rewriting this later.

        n = 9

 

We'll also need some storage to hold visited numbers within each row, column, and square.  We'll use dictionaries for that.

        rows, cols, squares = {}, {}, {}

 

Similar to the Valid Sudoku solution, hashing a row or column value is simple enough to see whether the current number has been visited within the current row or column, but for hashing the 3x3 sub-matrix, we'll need to utilize a trick.

The rows and columns divided by three will make them fall into one of these nine boxes and we can hash the box through a tuple of those row and column quotients.

0,0 0,1 0,2
1,0 1,1 1,2
2,0 2,1 2,2

 

So, we'll make a scan through the board and add each value to its row, column, and square set within their respective dictionaries.  If the sets haven't already been initialized within the dictionaries, we will initialize them before adding the value to them.

        for row in range(n):
            for col in range(n):
                value = board[row][col]
                square = (row//3, col//3)
                if row not in rows:
                    rows[row] = set()
                if col not in cols:
                    cols[col] = set()
                if square not in squares:
                    squares[square] = set()
                rows[row].add(value)
                cols[col].add(value)
                squares[square].add(value)

Next, let's create a helper function that will let us know in our DFS whether the number we are about to place is a valid spot.

        def valid_spot(row:int, col:int, square:tuple, value:int) -> bool:

 

If the value has already been seen within the current column, row, or square, then the answer would be false.

            if value in cols[col] or value in rows[row] or value in squares[square]:
                return False

 

Otherwise, the answer would be true.  At least for the moment that we made the placement, we wouldn't know until later whether it was actually false, as mentioned in the beginning.

            return True

Next, we'll make our backtrack function.

Our function will return a boolean variable.  Since we are doing these placements within the input board in place, we will want to terminate our DFS the moment we have successfully filled the board so that we don't overwrite all the correct values and end up with nothing.

To do this, we will check if our recursive DFS returned true and return if so.

        def backtrack(row:int, col:int) -> bool:

 

Let's set a few base cases.

Within our DFS, we will be recursing the next column at each cell.  

If we are at the last row of the board and have gone past the last column, remember that arrays index at zero, then we know that we have successfully filled the board so we will return true.

            if (row, col) == (n-1, n):
                return True

 

If we are not at the last row but have gone past the last column then we will just drop down to the next row.

            if col == n:
                row, col = row+1, 0

 

Also, if the current cell has already been filled by the input then we will backtrack the next cell within the current row.

We'll want to return the result for this because if we don't and just try to recurse the next cell without returning anything then later on in our function we will be trying to fill this current nonempty cell with a number and won't end up getting any result because there are no numbers we could place here.

            if board[row][col] != ".":
                return backtrack(row, col+1)

 

Okay, so if we have gotten to this point in our logic then that means we are still in the grid and have an empty cell to fill with a number.

We'll try to fill it with every number from one to nine.

We'll iterate each digit, setting its value to a string since that is the data type of the values in the board.

            for i in range(1, n+1):
                value = str(i)

 

We'll calculate the current 3x3 sub-matrix by dividing the row and column by three.

                square = (row//3, col//3)

 

Then, if we find that this is a valid spot for this value, we will place this number by writing it on the board and adding it to each respective set.

                if valid_spot(row, col, square, value):
                    board[row][col] = value
                    rows[row].add(value)
                    cols[col].add(value)
                    squares[square].add(value)

 

We'll then backtrack with this placement and continue our DFS on the next cell within the current row, but remember, we'll want to terminate immediately if this placement leads to a valid fill of the board later down the line.

                    if backtrack(row, col+1):
                        return True

 

If it didn't and later down the line, we found that we ran out of numbers to place between the ones already input onto the board and the ones we placed, we'll backtrack so that we can try the next number in our loop at this depth of our DFS.

This will entail marking the cell back to empty and removing the number from its respective sets.

                    board[row][col] = "."
                    rows[row].remove(value)
                    cols[col].remove(value)
                    squares[square].remove(value)

Now that our helper functions are made and we have noted what numbers we have on the board to start with, all we need to do now is make the initial call on the first cell of the grid.

        backtrack(0, 0)