37. Sudoku Solver

Sudoku Solver (LeetCode 37) is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Backtracking Patterns pattern, in the N-Queens / Constraint Satisfaction subpattern.

How to solve Sudoku Solver

Sudoku Solver is a N-Queens and Constraint Satisfaction problem, part of Backtracking Patterns. Solve N-Queens and Sudoku using backtracking with constraint propagation.

Work towards the solution in these steps:

1. Consider using a backtracking approach to fill the empty cells systematically and retract when a conflict arises.
2. Think about how to verify if placing a digit in a certain cell is valid by checking the row, column, and 3x3 sub-box constraints.
3. Implement a helper function that checks whether a given number placement in a cell maintains Sudoku rules before moving forward.

The reference solution runs in O(9^(n)) time and O(1) space.

The Sudoku Solver solution and editorial walks through the full approach with reference code.

Problem statement

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

A sudoku solution must satisfy all of the following rules:

- Each of the digits 1-9 must occur exactly once in each row.

- Each of the digits 1-9 must occur exactly once in each column.

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

Topics and companies

Topics: Array, Hash Table, Backtracking, Matrix.

Reported in interviews at DoorDash, Amazon, Oracle, Pinterest, Facebook, Intuit.

How to practise Sudoku Solver on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(9^(n)) time and O(1) space.

Open Sudoku Solver in the code editor, or read the Sudoku Solver editorial for a worked solution with its approach and complexity analysis.

Where Sudoku Solver sits in the DSA pattern sheet

• Backtracking Patterns pattern guide
• N-Queens / Constraint Satisfaction subpattern
• The full DSA patterns sheet

Problems related to Sudoku Solver

Other problems that use the same N-Queens / Constraint Satisfaction and Backtracking Patterns techniques:

• Matchsticks to Square — Medium, same subpattern
• N-Queens — Hard, same subpattern
• N-Queens II — Hard, same subpattern
• Check if Word Can Be Placed In Crossword — Medium, same pattern
• Combinations — Medium, same pattern
• Combination Sum — Medium, same pattern

Sudoku Solver FAQ