Write a program to solve a Sudoku puzzle by filling the empty cells.
A sudoku solution must satisfy all of the following rules:
1-9 must occur exactly once in each row.1-9 must occur exactly once in each column.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 == 9board[i].length == 9board[i][j] is a digit or '.'.The classic way to solve Sudoku Solver is using backtracking. The board is a 9×9 matrix where each empty cell must be filled with a digit from 1-9 while respecting Sudoku rules: no duplicates in the same row, column, or 3×3 subgrid.
The key idea is to try placing valid numbers in empty cells and recursively continue solving the remaining board. If a placement leads to a conflict later, the algorithm backtracks and tries another number. To make this efficient, we maintain quick lookups using arrays or hash sets to track which numbers are already used in each row, column, and subgrid.
By pruning invalid choices early, the search space is significantly reduced. The worst-case time complexity is exponential because we may explore many board states, but constraint checks make it practical for standard Sudoku boards. Space complexity mainly comes from recursion depth and auxiliary tracking structures.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Backtracking with constraint tracking (rows, columns, boxes) | O(9^(n)) in worst case search space | O(n) recursion stack + O(1) board tracking |
NeetCode
The backtracking approach is a classic method to solve problems like Sudoku that require exploring all configurations to find a valid solution. This involves recursively trying all numbers from 1 to 9 in each cell and verifying if they meet Sudoku rules. If a number fits, move to the next cell. If stuck, backtrack to the previous cell and try a different number. This method ensures all constraints are respected at each step.
Time Complexity: O(9^(N*N)), where N = 9 (the size of the board), as each empty cell has 9 possibilities.
Space Complexity: O(N*N) for the recursion stack.
1#include <stdbool.h>
2
3bool isValid(char board[9][9], int row, int col, char num) {
4 for
This solution implements a backtracking algorithm in C. The isValid function checks if placing a digit in a particular cell violates Sudoku rules. The solveSudokuHelper function tries placing digits and uses recursion to backtrack if necessary until the board is completely filled.
This approach enhances the basic backtracking method by introducing constraint propagation. Before choosing a number for a cell, it checks constraints upfront, reducing unnecessary exploration by propagating constraints once a number is filled. This technique decreases the number of options that need to be tried, thereby optimizing the backtracking process.
Time Complexity: Expected better than O(9^(N*N)), depending on effectiveness of constraint propagation reducing possible combinations.
Space Complexity: O(N*N), influenced by recursion.
1class Solution:
2 def solveSudoku(self, board: List[List
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of the Sudoku Solver problem appear in coding interviews at top tech companies. Interviewers often use it to evaluate a candidate's understanding of recursion, backtracking, pruning techniques, and constraint validation.
Sudoku is a constraint satisfaction problem where many combinations are possible but only a few are valid. Backtracking systematically explores possibilities and abandons invalid paths early, making it a natural fit for this type of puzzle.
Arrays or hash sets are commonly used to track digits already present in each row, column, and subgrid. Some optimized solutions also use bitmasks to represent used digits efficiently and speed up constraint checks.
The most common and effective approach is backtracking with constraint checking. At each empty cell, you try digits 1–9 and verify whether the placement is valid for the row, column, and 3×3 box. If a choice leads to a dead end, the algorithm backtracks and tries another number.
This Python solution incorporates constraint propagation into the backtracking method. It attempts to minimize choices by evaluating constraints before any number is placed, helping to reduce the branching factor in the search tree. If a valid scenario is found using propagation, it progresses further in solving the Sudoku.