Problem Statement in English

You’re given a $9x9$ Sudoku board, where some of the cells are filled with digits from ‘1’ to ‘9’ and others are empty (represented by ‘.’). The goal is to fill the empty cells such that each row, each column, and each of the nine $3x3$ sub-boxes contains all of the digits from ‘1’ to ‘9’ exactly once.

Approach

We must try out all possible combinations of numbers in the empty cells, ensuring that we adhere to the Sudoku rules. This is a classic backtracking problem. Although we can make some optimisations.

We should track the numbers already present in each row, column, and 3x3 box. This allows us to check the validity of placing a number in constant time, rather than scanning the entire row, column, or box.

So we maintain three sets for each row, column, and box to keep track of the numbers that have already been placed. When we attempt to place a number in an empty cell, we check these sets to see if the number is already present. If it is not, we place the number and update the sets accordingly. If we reach a point where no valid number can be placed, we backtrack by removing the last placed number from the board and the sets, and continue with the next possibility.

A handy formula to map a cell from a grid to a 1D array in general is:
$\text{index} = \text{row} \cdot \text{number of columns} + \text{column}$.

To reverse the mapping, we can use:
$\text{row} = \left\lfloor \dfrac{\text{index}}{\text{number of columns}} \right\rfloor$
$\text{column} = \text{index} \bmod \text{number of columns}$

And we’re done!

Solution in Python


class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        # Pre-track numbers already in rows, cols, and 3x3 boxes
        rows = [set() for _ in range(9)]
        cols = [set() for _ in range(9)]
        boxes = [set() for _ in range(9)]

        # Initialize tracking state from the initial board
        for r in range(9):
            for c in range(9):
                if board[r][c] != '.':
                    val = board[r][c]
                    rows[r].add(val)
                    cols[c].add(val)
                    boxes[(r // 3) * 3 + (c // 3)].add(val)

        def solve():
            for row in range(9):
                for col in range(9):
                    if board[row][col] == '.':
                        box_idx = (row // 3) * 3 + (col // 3)
                        for num in '123456789':
                            # O(1) validity check
                            if num not in rows[row] and num not in cols[col] and num not in boxes[box_idx]:
                                # Place choice
                                board[row][col] = num
                                rows[row].add(num)
                                cols[col].add(num)
                                boxes[box_idx].add(num)

                                if solve():
                                    return True

                                # Backtrack choice
                                board[row][col] = '.'
                                rows[row].remove(num)
                                cols[col].remove(num)
                                boxes[box_idx].remove(num)

                        return False  # Trigger backtracking if no digits fit
            return True  # Board complete

        solve()

Complexity

  • Time: $O(9^{n})$
    where $n$ is the number of empty cells in the Sudoku board. In the worst case, we may have to try all 9 digits for each empty cell, leading to an exponential time complexity.

  • Space: $O(9)$
    where 9 is the size of the Sudoku board. This is because we are using sets to track the numbers in rows, columns, and boxes, which takes constant space.

Mistakes I Made

My solution was overcomplicated

And we are done.