Sudoku Solver

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

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)), where n is the number of empty cells. For each empty cell, we try up to 9 possibilities, and backtrack if invalid. In practice, pruning (isValid) makes it much faster. time and O(1) extra space (excluding recursion stack), as the board is modified in-place. The recursion stack can go up to O(n), where n is the number of empty cells (at most 81). 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

Problems related to Sudoku Solver

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

Preparing this workspace.