Sudoku Solver

Hard

#0037Time: O(9^m), where 'm' is the number of empty cells. In the worst case, we have to explore all possible number combinations for the empty cells.Space: O(m) or O(81) for the recursion stack depth. Since the board size is fixed, this can be considered O(1).18 companies

Patterns

Backtracking

Data structures

Array Hash Table Matrix

Companies

Adobe Amazon Apple Bloomberg

Prompt

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.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach uses a standard recursive backtracking algorithm. It iterates through the grid to find an empty cell, then tries to place each digit from 1 to 9 in that cell. For each attempt, it checks if the placement is valid according to Sudoku rules. If it is, it proceeds recursively. If a path leads to a dead end, it backtracks and tries the next digit.

Algorithm

Define a recursive function, solve(), that attempts to solve the board.
Iterate through each cell of the board from (0,0) to (8,8).
If a cell (row, col) is empty, loop through digits '1' to '9'.
For each digit, check its validity using a helper function isValid() which scans the current row, column, and 3x3 sub-grid.
If the digit is valid, place it and make a recursive call to solve().
If the recursive call returns true, a solution is found, so return true.
If it returns false, backtrack by resetting the cell to '.' and try the next digit.
If all digits fail for a cell, return false.
If the entire board is scanned without finding empty cells, return true.

Walkthrough

This method employs a brute-force recursive strategy. The main solve function iterates through the grid. Upon finding an empty cell, it tries to fill it with a digit from 1 to 9. For each digit, it calls a helper function isValid to check if the move is legal. The isValid function performs three checks: whether the digit already exists in the current row, the current column, or the current 3x3 sub-grid. If the move is valid, the function calls itself recursively. If the recursion leads to a dead end (returns false), it backtracks by undoing the move and trying the next digit. This process continues until a full solution is found or all possibilities are exhausted.

1class Solution {2    public void solveSudoku(char[][] board) {3        solve(board);4    }5 6    private boolean solve(char[][] board) {7        for (int i = 0; i < 9; i++) {8            for (int j = 0; j < 9; j++) {9                if (board[i][j] == '.') {10                    for (char c = '1'; c <= '9'; c++) {11                        if (isValid(board, i, j, c)) {12                            board[i][j] = c;13                            if (solve(board)) {14                                return true;15                            } else {16                                board[i][j] = '.'; // Backtrack17                            }18                        }19                    }20                    return false; // No valid number found for this cell21                }22            }23        }24        return true; // Board is solved25    }26 27    private boolean isValid(char[][] board, int row, int col, char c) {28        for (int i = 0; i < 9; i++) {29            // Check row30            if (board[row][i] == c) {31                return false;32            }33            // Check column34            if (board[i][col] == c) {35                return false;36            }37            // Check 3x3 box38            int boxRow = 3 * (row / 3) + i / 3;39            int boxCol = 3 * (col / 3) + i % 3;40            if (board[boxRow][boxCol] == c) {41                return false;42            }43        }44        return true;45    }46}

Complexity

Time

O(9^m), where 'm' is the number of empty cells. In the worst case, we have to explore all possible number combinations for the empty cells.

Space

O(m) or O(81) for the recursion stack depth. Since the board size is fixed, this can be considered O(1).

Trade-offs

Pros

Simple to understand and implement.
Guaranteed to find the solution for a valid puzzle.

Cons

Inefficient due to repeated validation checks.
Can be very slow for puzzles with a large number of empty cells.

This approach improves upon the simple backtracking by optimizing the validation step. Instead of repeatedly scanning rows, columns, and boxes, it uses boolean arrays (or hash sets) to keep track of which numbers are already used in each row, column, and 3x3 sub-grid. This reduces the time to check for a valid placement from O(N) to O(1).

Algorithm

Initialize boolean arrays rows[9][10], cols[9][10], and boxes[9][10].
Scan the initial board to populate these arrays with used numbers.
Implement a recursive backtracking function backtrack(row, col).
The function moves to the next cell (nextRow, nextCol) in each call.
If the current cell (row, col) is empty, loop through digits '1' to '9'.
Check validity in O(1) time using the boolean arrays.
If a digit is valid, place it, update the boolean arrays, and recurse with backtrack(nextRow, nextCol).
If the recursion fails, backtrack by resetting the cell and the boolean arrays.
The base case for recursion is when row == 9, indicating the board is solved.

Walkthrough

This approach significantly optimizes the validation step of the simple backtracking algorithm. It maintains three 2D boolean arrays: rows, cols, and boxes. These arrays act as a cache to store which numbers are already present in each row, column, and 3x3 sub-grid. Before starting the backtracking process, these arrays are populated based on the initial numbers on the board. During backtracking, checking if a number can be placed in a cell becomes an O(1) operation by simply looking up the values in these three arrays. When a number is placed, the corresponding entries in the arrays are updated. If backtracking is needed, these entries are reverted.

1class Solution {2    private boolean[][] rows = new boolean[9][10];3    private boolean[][] cols = new boolean[9][10];4    private boolean[][] boxes = new boolean[9][10];5    private char[][] board;6    private boolean solved = false;7 8    public void solveSudoku(char[][] board) {9        this.board = board;10        // Pre-fill the boolean arrays11        for (int i = 0; i < 9; i++) {12            for (int j = 0; j < 9; j++) {13                if (board[i][j] != '.') {14                    int num = board[i][j] - '0';15                    int boxIndex = (i / 3) * 3 + j / 3;16                    rows[i][num] = true;17                    cols[j][num] = true;18                    boxes[boxIndex][num] = true;19                }20            }21        }22        backtrack(0, 0);23    }24 25    private void backtrack(int row, int col) {26        if (row == 9) {27            solved = true;28            return;29        }30 31        int nextRow = (col == 8) ? row + 1 : row;32        int nextCol = (col == 8) ? 0 : col + 1;33 34        if (board[row][col] != '.') {35            backtrack(nextRow, nextCol);36        } else {37            int boxIndex = (row / 3) * 3 + col / 3;38            for (int num = 1; num <= 9; num++) {39                if (!rows[row][num] && !cols[col][num] && !boxes[boxIndex][num]) {40                    placeNumber(row, col, num);41                    backtrack(nextRow, nextCol);42                    if (!solved) {43                        removeNumber(row, col, num); // Backtrack44                    }45                }46            }47        }48    }49 50    private void placeNumber(int row, int col, int num) {51        int boxIndex = (row / 3) * 3 + col / 3;52        board[row][col] = (char) (num + '0');53        rows[row][num] = true;54        cols[col][num] = true;55        boxes[boxIndex][num] = true;56    }57 58    private void removeNumber(int row, int col, int num) {59        int boxIndex = (row / 3) * 3 + col / 3;60        board[row][col] = '.';61        rows[row][num] = false;62        cols[col][num] = false;63        boxes[boxIndex][num] = false;64    }65}

Complexity

Time

O(9^m), where 'm' is the number of empty cells. While the theoretical worst-case is the same as the simple backtracking, the practical performance is significantly better due to O(1) validation checks.

Space

O(m) for the recursion stack plus O(1) for the boolean arrays (since their size is fixed: 9x10 x 3). Total space is O(m) or effectively O(1).

Trade-offs

Pros

Much faster than simple backtracking.
O(1) time complexity for validating a number placement.

Cons

Still a brute-force search, which can be slow for the hardest puzzles.
Slightly more complex due to the management of auxiliary data structures.

This is the most efficient backtracking approach. It enhances the previous method by adding a heuristic for selecting which empty cell to fill next. Instead of processing cells in a fixed order (e.g., row-by-row), it scans all empty cells and chooses the one with the 'Minimum Remaining Values' (MRV). This means it picks the cell that has the fewest legal numbers that can be placed in it. This strategy helps to prune the search tree more aggressively by tackling the most constrained parts of the puzzle first, leading to earlier detection of dead ends.

Algorithm

Set up boolean arrays rows, cols, boxes as in the previous approach.
Implement a recursive solve() function.
Inside solve(), first find the most constrained empty cell (the one with the Minimum Remaining Values or MRV). This involves scanning all empty cells and counting their valid placement options.
If no empty cells exist, the puzzle is solved; return true.
Let the most constrained cell be (bestRow, bestCol).
Iterate through the valid digits for (bestRow, bestCol).
For each valid digit, place it, update the boolean arrays, and call solve() recursively.
If the recursive call returns true, propagate true.
Otherwise, backtrack by resetting the cell and boolean arrays.
If all valid digits for the cell fail, return false.

Walkthrough

This advanced backtracking method incorporates a powerful heuristic to guide the search more intelligently. Instead of filling empty cells in a fixed order, at each step, it first identifies the most constrained cell—the one with the Minimum Remaining Values (MRV). To do this, it iterates through all empty cells and counts the number of valid candidate numbers for each. The cell with the fewest candidates is chosen to be filled next. This strategy prioritizes choices that are most likely to lead to a conflict, thereby pruning large portions of the search tree early. This makes the algorithm exceptionally fast in practice, even for very difficult Sudoku puzzles.

1class Solution {2    private boolean[][] rows = new boolean[9][10];3    private boolean[][] cols = new boolean[9][10];4    private boolean[][] boxes = new boolean[9][10];5    private char[][] board;6 7    public void solveSudoku(char[][] board) {8        this.board = board;9        for (int i = 0; i < 9; i++) {10            for (int j = 0; j < 9; j++) {11                if (board[i][j] != '.') {12                    int num = board[i][j] - '0';13                    int boxIndex = (i / 3) * 3 + j / 3;14                    rows[i][num] = true;15                    cols[j][num] = true;16                    boxes[boxIndex][num] = true;17                }18            }19        }20        solve();21    }22 23    private boolean solve() {24        int bestRow = -1, bestCol = -1, minOptions = 10;25 26        // Find the most constrained empty cell (Minimum Remaining Values)27        for (int r = 0; r < 9; r++) {28            for (int c = 0; c < 9; c++) {29                if (board[r][c] == '.') {30                    int options = 0;31                    int boxIndex = (r / 3) * 3 + c / 3;32                    for (int num = 1; num <= 9; num++) {33                        if (!rows[r][num] && !cols[c][num] && !boxes[boxIndex][num]) {34                            options++;35                        }36                    }37                    if (options < minOptions) {38                        minOptions = options;39                        bestRow = r;40                        bestCol = c;41                    }42                }43            }44        }45 46        // If no empty cells, puzzle is solved47        if (bestRow == -1) {48            return true;49        }50 51        // Try all valid numbers for the most constrained cell52        int r = bestRow;53        int c = bestCol;54        int boxIndex = (r / 3) * 3 + c / 3;55        for (int num = 1; num <= 9; num++) {56            if (!rows[r][num] && !cols[c][num] && !boxes[boxIndex][num]) {57                placeNumber(r, c, num);58                if (solve()) {59                    return true;60                }61                removeNumber(r, c, num); // Backtrack62            }63        }64 65        return false; // No solution found from this path66    }67 68    private void placeNumber(int row, int col, int num) {69        int boxIndex = (row / 3) * 3 + col / 3;70        board[row][col] = (char) (num + '0');71        rows[row][num] = true;72        cols[col][num] = true;73        boxes[boxIndex][num] = true;74    }75 76    private void removeNumber(int row, int col, int num) {77        int boxIndex = (row / 3) * 3 + col / 3;78        board[row][col] = '.';79        rows[row][num] = false;80        cols[col][num] = false;81        boxes[boxIndex][num] = false;82    }83}

Complexity

Time

O(9^m), where 'm' is the number of empty cells. The heuristic does not change the worst-case theoretical complexity. However, in practice, it prunes the search space so effectively that it's one of the fastest algorithms for solving Sudoku puzzles.

Space

O(m) for the recursion stack, which is effectively O(1) for a fixed-size board. The space for the boolean arrays is also O(1).

Trade-offs

Pros

Extremely fast in practice due to intelligent search space pruning.
Finds solutions for even very difficult puzzles quickly.

Cons

More complex to implement than simpler backtracking algorithms.
The overhead of finding the most constrained cell at each recursive step, while usually beneficial, adds complexity.

Solutions

Solution

1public class Solution {2    public void SolveSudoku(char[][] board) {3        this.board = new ushort ? [9, 9];4        for (var i = 0; i < 9; ++i) {5            for (var j = 0; j < 9; ++j) {6                if (board[i][j] != '.') {7                    this.board[i, j] = (ushort)(1 << (board[i][j] - '0' - 1));8                }9            }10        }11        if (SolveSudoku(0, 0)) {12            for (var i = 0; i < 9; ++i) {13                for (var j = 0; j < 9; ++j) {14                    if (board[i][j] == '.') {15                        board[i][j] = '0';16                        while (this.board[i, j].Value != 0) {17                            board[i][j] = (char)(board[i][j] + 1);18                            this.board[i, j] >>= 1;19                        }20                    }21                }22            }23        }24    }25    private ushort ? [, ] board;26    private bool ValidateHorizontalRule(int row) {27        ushort temp = 0;28        for (var i = 0; i < 9; ++i) {29            if (board[row, i].HasValue) {30                if ((temp | board[row, i].Value) == temp) {31                    return false;32                }33                temp |= board[row, i].Value;34            }35        }36        return true;37    }38    private bool ValidateVerticalRule(int column) {39        ushort temp = 0;40        for (var i = 0; i < 9; ++i) {41            if (board[i, column].HasValue) {42                if ((temp | board[i, column].Value) == temp) {43                    return false;44                }45                temp |= board[i, column].Value;46            }47        }48        return true;49    }50    private bool ValidateBlockRule(int row, int column) {51        var startRow = row / 3 * 3;52        var startColumn = column / 3 * 3;53        ushort temp = 0;54        for (var i = startRow; i < startRow + 3; ++i) {55            for (var j = startColumn; j < startColumn + 3; ++j) {56                if (board[i, j].HasValue) {57                    if ((temp | board[i, j].Value) == temp) {58                        return false;59                    }60                    temp |= board[i, j].Value;61                }62            }63        }64        return true;65    }66    private bool SolveSudoku(int i, int j) {67        while (true) {68            if (j == 9) {69                ++i;70                j = 0;71            }72            if (i == 9) {73                return true;74            }75            if (board[i, j].HasValue) {76                ++j;77            } else {78                break;79            }80        }81        ushort stop = 1 << 9;82        for (ushort t = 1; t != stop; t <<= 1) {83            board[i, j] = t;84            if (ValidateHorizontalRule(i) && ValidateVerticalRule(j) && ValidateBlockRule(i, j)) {85                if (SolveSudoku(i, j + 1)) {86                    return true;87                }88            }89        }90        board[i, j] = null;91        return false;92    }93}

1class Solution {2private3  boolean ok;4private5  char[][] board;6private7  List<Integer> t = new ArrayList<>();8private9  boolean[][] row = new boolean[9][9];10private11  boolean[][] col = new boolean[9][9];12private13  boolean[][][] block = new boolean[3][3][9];14public15  void solveSudoku(char[][] board) {16    this.board = board;17    for (int i = 0; i < 9; ++i) {18      for (int j = 0; j < 9; ++j) {19        if (board[i][j] == '.') {20          t.add(i * 9 + j);21        } else {22          int v = board[i][j] - '1';23          row[i][v] = col[j][v] = block[i / 3][j / 3][v] = true;24        }25      }26    }27    dfs(0);28  }29private30  void dfs(int k) {31    if (k == t.size()) {32      ok = true;33      return;34    }35    int i = t.get(k) / 9, j = t.get(k) % 9;36    for (int v = 0; v < 9; ++v) {37      if (!row[i][v] && !col[j][v] && !block[i / 3][j / 3][v]) {38        row[i][v] = col[j][v] = block[i / 3][j / 3][v] = true;39        board[i][j] = (char)(v + '1');40        dfs(k + 1);41        row[i][v] = col[j][v] = block[i / 3][j / 3][v] = false;42      }43      if (ok) {44        return;45      }46    }47  }48}

1using pii = pair < int , int > ; class Solution { public: void solveSudoku ( vector < vector < char >>& board ) { bool row [ 9 ][ 9 ] = { false }; bool col [ 9 ][ 9 ] = { false }; bool block [ 3 ][ 3 ][ 9 ] = { false }; bool ok = false ; vector < pii > t ; for ( int i = 0 ; i < 9 ; ++ i ) { for ( int j = 0 ; j < 9 ; ++ j ) { if ( board [ i ][ j ] == '.' ) { t . push_back ({ i , j }); } else { int v = board [ i ][ j ] - '1' ; row [ i ][ v ] = col [ j ][ v ] = block [ i / 3 ][ j / 3 ][ v ] = true ; } } } function < void ( int k ) > dfs = [ & ]( int k ) { if ( k == t . size ()) { ok = true ; return ; } int i = t [ k ]. first , j = t [ k ]. second ; for ( int v = 0 ; v < 9 ; ++ v ) { if ( ! row [ i ][ v ] && ! col [ j ][ v ] && ! block [ i / 3 ][ j / 3 ][ v ]) { row [ i ][ v ] = col [ j ][ v ] = block [ i / 3 ][ j / 3 ][ v ] = true ; board [ i ][ j ] = v + '1' ; dfs ( k + 1 ); row [ i ][ v ] = col [ j ][ v ] = block [ i / 3 ][ j / 3 ][ v ] = false ; } if ( ok ) { return ; } } }; dfs ( 0 ); } };

1class Solution:2    def solveSudoku(self, board: List[List[str]]) -> None: def dfs(k): nonlocal ok if k == len(t): ok = True return i, j = t[k] for v in range(9): if row[i][v] == col[j][v] == block[i // 3][j // 3][v] == False: row[i][v] = col[j][v] = block[i // 3][j // 3][v] = True board[i][j] = str(v + 1) dfs(k + 1) row[i][v] = col[j][v] = block[i // 3][j // 3][v] = False if ok: return row = [[False] * 9 for _ in range(9)] col = [[False] * 9 for _ in range(9)] block = [[[False] * 9 for _ in range(3)] for _ in range(3)] t = [] ok = False for i in range(9): for j in range(9): if board[i][j] == '.': t . append((i, j)) else: v = int(board[i][j]) - 1 row[i][v] = col[j][v] = block[i // 3][j // 3][v] = True dfs(0)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem

Solution

1public class Solution {2    public void SolveSudoku(char[][] board) {3        this.board = new ushort ? [9, 9];4        for (var i = 0; i < 9; ++i) {5            for (var j = 0; j < 9; ++j) {6                if (board[i][j] != '.') {7                    this.board[i, j] = (ushort)(1 << (board[i][j] - '0' - 1));8                }9            }10        }11        if (SolveSudoku(0, 0)) {12            for (var i = 0; i < 9; ++i) {13                for (var j = 0; j < 9; ++j) {14                    if (board[i][j] == '.') {15                        board[i][j] = '0';16                        while (this.board[i, j].Value != 0) {17                            board[i][j] = (char)(board[i][j] + 1);18                            this.board[i, j] >>= 1;19                        }20                    }21                }22            }23        }24    }25    private ushort ? [, ] board;26    private bool ValidateHorizontalRule(int row) {27        ushort temp = 0;28        for (var i = 0; i < 9; ++i) {29            if (board[row, i].HasValue) {30                if ((temp | board[row, i].Value) == temp) {31                    return false;32                }33                temp |= board[row, i].Value;34            }35        }36        return true;37    }38    private bool ValidateVerticalRule(int column) {39        ushort temp = 0;40        for (var i = 0; i < 9; ++i) {41            if (board[i, column].HasValue) {42                if ((temp | board[i, column].Value) == temp) {43                    return false;44                }45                temp |= board[i, column].Value;46            }47        }48        return true;49    }50    private bool ValidateBlockRule(int row, int column) {51        var startRow = row / 3 * 3;52        var startColumn = column / 3 * 3;53        ushort temp = 0;54        for (var i = startRow; i < startRow + 3; ++i) {55            for (var j = startColumn; j < startColumn + 3; ++j) {56                if (board[i, j].HasValue) {57                    if ((temp | board[i, j].Value) == temp) {58                        return false;59                    }60                    temp |= board[i, j].Value;61                }62            }63        }64        return true;65    }66    private bool SolveSudoku(int i, int j) {67        while (true) {68            if (j == 9) {69                ++i;70                j = 0;71            }72            if (i == 9) {73                return true;74            }75            if (board[i, j].HasValue) {76                ++j;77            } else {78                break;79            }80        }81        ushort stop = 1 << 9;82        for (ushort t = 1; t != stop; t <<= 1) {83            board[i, j] = t;84            if (ValidateHorizontalRule(i) && ValidateVerticalRule(j) && ValidateBlockRule(i, j)) {85                if (SolveSudoku(i, j + 1)) {86                    return true;87                }88            }89        }90        board[i, j] = null;91        return false;92    }93}

1class Solution {2private3  boolean ok;4private5  char[][] board;6private7  List<Integer> t = new ArrayList<>();8private9  boolean[][] row = new boolean[9][9];10private11  boolean[][] col = new boolean[9][9];12private13  boolean[][][] block = new boolean[3][3][9];14public15  void solveSudoku(char[][] board) {16    this.board = board;17    for (int i = 0; i < 9; ++i) {18      for (int j = 0; j < 9; ++j) {19        if (board[i][j] == '.') {20          t.add(i * 9 + j);21        } else {22          int v = board[i][j] - '1';23          row[i][v] = col[j][v] = block[i / 3][j / 3][v] = true;24        }25      }26    }27    dfs(0);28  }29private30  void dfs(int k) {31    if (k == t.size()) {32      ok = true;33      return;34    }35    int i = t.get(k) / 9, j = t.get(k) % 9;36    for (int v = 0; v < 9; ++v) {37      if (!row[i][v] && !col[j][v] && !block[i / 3][j / 3][v]) {38        row[i][v] = col[j][v] = block[i / 3][j / 3][v] = true;39        board[i][j] = (char)(v + '1');40        dfs(k + 1);41        row[i][v] = col[j][v] = block[i / 3][j / 3][v] = false;42      }43      if (ok) {44        return;45      }46    }47  }48}

1using pii = pair < int , int > ; class Solution { public: void solveSudoku ( vector < vector < char >>& board ) { bool row [ 9 ][ 9 ] = { false }; bool col [ 9 ][ 9 ] = { false }; bool block [ 3 ][ 3 ][ 9 ] = { false }; bool ok = false ; vector < pii > t ; for ( int i = 0 ; i < 9 ; ++ i ) { for ( int j = 0 ; j < 9 ; ++ j ) { if ( board [ i ][ j ] == '.' ) { t . push_back ({ i , j }); } else { int v = board [ i ][ j ] - '1' ; row [ i ][ v ] = col [ j ][ v ] = block [ i / 3 ][ j / 3 ][ v ] = true ; } } } function < void ( int k ) > dfs = [ & ]( int k ) { if ( k == t . size ()) { ok = true ; return ; } int i = t [ k ]. first , j = t [ k ]. second ; for ( int v = 0 ; v < 9 ; ++ v ) { if ( ! row [ i ][ v ] && ! col [ j ][ v ] && ! block [ i / 3 ][ j / 3 ][ v ]) { row [ i ][ v ] = col [ j ][ v ] = block [ i / 3 ][ j / 3 ][ v ] = true ; board [ i ][ j ] = v + '1' ; dfs ( k + 1 ); row [ i ][ v ] = col [ j ][ v ] = block [ i / 3 ][ j / 3 ][ v ] = false ; } if ( ok ) { return ; } } }; dfs ( 0 ); } };

1class Solution:2    def solveSudoku(self, board: List[List[str]]) -> None: def dfs(k): nonlocal ok if k == len(t): ok = True return i, j = t[k] for v in range(9): if row[i][v] == col[j][v] == block[i // 3][j // 3][v] == False: row[i][v] = col[j][v] = block[i // 3][j // 3][v] = True board[i][j] = str(v + 1) dfs(k + 1) row[i][v] = col[j][v] = block[i // 3][j // 3][v] = False if ok: return row = [[False] * 9 for _ in range(9)] col = [[False] * 9 for _ in range(9)] block = [[[False] * 9 for _ in range(3)] for _ in range(3)] t = [] ok = False for i in range(9): for j in range(9): if board[i][j] == '.': t . append((i, j)) else: v = int(board[i][j]) - 1 row[i][v] = col[j][v] = block[i // 3][j // 3][v] = True dfs(0)

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.