Sudoku Solver

Q: What is the time complexity of a backtracking sudoku solver?

Exponential in the worst case, O(9^m) for m empty cells, because each cell can branch into up to 9 digits. On real puzzles the row, column and box rules cut most branches, and filling the emptiest cell first cuts most of the rest.

HardBacktracking

+10

A sudoku board is a 9 × 9 grid divided into nine 3 × 3 boxes. On a solved board every row, every column and every box holds each digit from 1 to 9 exactly once.

The puzzle arrives as 9 strings, one per row from the top; a . is an empty cell. Fill every empty cell and return the solved board in the same form. The board has exactly one solution.

Function

solveSudoku(board: string-array) → string-array

boardstring-array: the 9 rows of the puzzle, a dot in each empty cell
Returnsstring-array: the 9 rows of the solved board

Constraints

board holds 9 strings of length 9.
Every character is . or one of the digits 1 to 9.
The given digits never repeat within a row, a column or a box.
The board has exactly one solution.

Examples

Input: board = ["9.7.....6", "824.3....", "..1..9..2", ".9...2.18", "...4....5", "1325.8...", "...687...", "......8.9", ".4.9...5."]
Output: ["957214386", "824736591", "361859742", "495372618", "786491235", "132568974", "519687423", "273145869", "648923157"]
Explanation: The top row 9.7.....6 already holds 9, 7 and 6, so its six empty cells take 1, 2, 3, 4, 5 and 8. The columns and boxes decide where each one goes, and the row becomes 957214386.

Follow-up

In a killer sudoku, cages of cells must also add up to given sums. How would you add that rule to the search and use it to cut branches early?

Solution

Solve it by backtracking: place a digit that fits, continue, and undo it when the board cannot be finished. The order of the cells decides the speed. On a hard board, reading order can visit hundreds of millions of partial boards; filling the cell with the fewest options first takes about a hundred.

Backtracking in reading order

Correct, but does not finish on the largest tests

Intuition

Fill the empty cells in reading order, each with the smallest digit that fits. When a cell has no digit left, go back to the previous cell and try its next one. Every combination that respects the rules is tried in turn, so the search finds the solution.

Three tables make each fit test O(1): rowUsed[r][d], colUsed[c][d] and boxUsed[b][d], with box b = (r / 3) * 3 + c / 3. Placing a digit sets three entries and removing it clears them.

The fixed order is the weak point: the search can fill a whole row with digits that fit locally and learn many cells later that they leave no room. A board whose top rows hold almost no clues, with high digits as their answers, sends it through over 300 million partial boards.

Algorithm

Read the board into a grid with 0 for an empty cell, fill rowUsed, colUsed and boxUsed, and list the empty cells in reading order.
backtrack(k): if k equals the number of empty cells, return true.
For each digit d from 1 to 9 unused in the row, column and box of cell k, place it, mark it, and return true if backtrack(k+1) does; otherwise unmark it.
If no digit works, clear the cell and return false. Call backtrack(0) and turn the grid back into strings.

def solveSudoku(board):
    grid = [[0 if ch == "." else int(ch) for ch in row] for row in board]
    # row_used[r][d] is True when digit d already sits in row r; same for
    # columns and boxes. Box b holds the cells with (r // 3) * 3 + c // 3 == b.
    row_used = [[False] * 10 for _ in range(9)]
    col_used = [[False] * 10 for _ in range(9)]
    box_used = [[False] * 10 for _ in range(9)]
    empties = []
    for r in range(9):
        for c in range(9):
            d = grid[r][c]
            if d:
                row_used[r][d] = col_used[c][d] = box_used[(r // 3) * 3 + c // 3][d] = True
            else:
                empties.append((r, c))

    def backtrack(k):
        if k == len(empties):
            return True
        r, c = empties[k]
        b = (r // 3) * 3 + c // 3
        for d in range(1, 10):
            if not row_used[r][d] and not col_used[c][d] and not box_used[b][d]:
                grid[r][c] = d
                row_used[r][d] = col_used[c][d] = box_used[b][d] = True
                if backtrack(k + 1):
                    return True
                row_used[r][d] = col_used[c][d] = box_used[b][d] = False
        grid[r][c] = 0
        return False

    backtrack(0)
    return ["".join(str(d) for d in row) for row in grid]

Fill the emptiest cell first

Intuition

The solution does not depend on the fill order, so pick the order that keeps the search small: at every step, fill the empty cell that allows the fewest digits. A cell with one allowed digit is forced and adds no branch. A cell with none is picked at once, so a wrong board is caught right away.

To count allowed digits cheaply for 81 cells per step, store each row, column and box as a bitmask: bit d of rows[r] is set when digit d is in row r. A cell allows ~(rows[r] | cols[c] | boxes[b]) & 0x3FE, where 0x3FE keeps bits 1 to 9, and the count is the number of set bits. Placing d sets bit d in three masks; an exclusive or removes it.

Algorithm

Build the grid and the masks rows, cols and boxes from the given digits.
backtrack(): scan all cells, compute each empty cell's allowed digits, and keep the first cell with the smallest count. If no cell is empty, return true.
For each allowed digit of that cell, place it, set its bit in the three masks, and return true if backtrack() does; otherwise clear the bits.
If no digit works, empty the cell and return false. Call backtrack() and turn the grid back into strings.

def solveSudoku(board):
    grid = [[0 if ch == "." else int(ch) for ch in row] for row in board]
    # Bit d of rows[r] is set when digit d already sits in row r; same for
    # columns and boxes. Box b holds the cells with (r // 3) * 3 + c // 3 == b.
    rows, cols, boxes = [0] * 9, [0] * 9, [0] * 9
    for r in range(9):
        for c in range(9):
            d = grid[r][c]
            if d:
                rows[r] |= 1 << d
                cols[c] |= 1 << d
                boxes[(r // 3) * 3 + c // 3] |= 1 << d

    def backtrack():
        # Pick the empty cell with the fewest digits left (the first one on a tie).
        best_r, best_c, best_allowed, best_count = -1, -1, 0, 10
        for r in range(9):
            for c in range(9):
                if grid[r][c] == 0:
                    # Bits 1 to 9 of 0x3FE are the nine digits.
                    allowed = ~(rows[r] | cols[c] | boxes[(r // 3) * 3 + c // 3]) & 0x3FE
                    count = bin(allowed).count("1")
                    if count < best_count:
                        best_r, best_c, best_allowed, best_count = r, c, allowed, count
        if best_r == -1:
            return True  # no empty cell is left: the board is solved
        r, c = best_r, best_c
        b = (r // 3) * 3 + c // 3
        for d in range(1, 10):
            bit = 1 << d
            if best_allowed & bit:
                grid[r][c] = d
                rows[r] |= bit
                cols[c] |= bit
                boxes[b] |= bit
                if backtrack():
                    return True
                rows[r] ^= bit
                cols[c] ^= bit
                boxes[b] ^= bit
        grid[r][c] = 0
        return False

    backtrack()
    return ["".join(str(d) for d in row) for row in grid]

Pitfalls and edge cases

Forgetting to clear a digit from the row, column and box records when you undo it. Later cells then see the digit as used, and the search misses the solution.
Using r / 3 + c / 3 for the box. Cells (0, 4) and (4, 0) both land on 1, so two boxes share one record and the board can never be filled. Use (r / 3) * 3 + c / 3 with integer division.
Not stopping at the first solution. The undo steps then empty the board again before you read it.

Frequently asked questions3

What is the time complexity of a backtracking sudoku solver?

Exponential in the worst case, O(9^m) for m empty cells, because each cell can branch into up to 9 digits. On real puzzles the row, column and box rules cut most branches, and filling the emptiest cell first cuts most of the rest.

How do you check that a sudoku has exactly one solution?

Run the same backtracking search, but count solutions and stop when the count reaches 2. A count of 1 means the puzzle is unique, 0 means it has no solution. Puzzle generators run this check after removing each clue.

Is there a faster way to solve sudoku than backtracking?

Most fast solvers still backtrack but deduce more before each guess. Constraint propagation fills every cell with a single option and every digit that fits only one cell of its row, column or box, then repeats. Sudoku can also be stated as an exact cover problem and solved with Knuth's Algorithm X.

def solveSudoku(board):
    # Write code here

Test #1

Argument

board = ["9.7.....6", "824.3....", "..1..9..2", ".9...2.18", "...4....5", "1325.8...", "...687...", "......8.9", ".4.9...5."]

Expected Output

["957214386", "824736591", "361859742", "495372618", "786491235", "132568974", "519687423", "273145869", "648923157"]