Sudoku Solver

🎯

Sudoku Solver

hardBACKTRACKINGAmazonFacebookGoogle

Imagine you have a partially completed Sudoku puzzle and want a program to fill in the missing numbers correctly, respecting all Sudoku rules.

💡 Sudoku Solver is a classic backtracking problem where beginners often struggle because it requires understanding how to systematically try possibilities and backtrack when a choice leads to a dead end. The challenge is managing constraints efficiently and implementing recursion correctly.

📋

Problem Statement

Given a 9x9 Sudoku board partially filled with digits 1-9 and empty cells represented by '.', fill the board so that every row, every column, and every 3x3 sub-box contains the digits 1 through 9 exactly once. Modify the board in-place.

board is a 9x9 gridEach cell contains a digit '1'-'9' or '.' for emptyThe input board is guaranteed to have a valid solution

💡

Example

Input"[[\"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"]]

The solver fills each empty cell by trying digits 1-9 and backtracking when constraints are violated, eventually completing the board correctly.

• Board with only one empty cell → should fill that cell correctly
• Board with multiple empty cells in the same row/column/box → must respect all constraints
• Board with minimal clues (17 clues) → still solvable by backtracking
• Board already solved → should return immediately without changes

⚠️

Common Mistakes

Not backtracking properly by resetting the cell after failed recursion

Leads to incorrect board state and wrong answers

✅ Always reset the cell to '.' after backtracking

Checking validity inefficiently by scanning entire row/column/box every time

Causes timeouts or slow performance

✅ Use sets or arrays to track used digits for O(1) checks

Not handling the 3x3 box indexing correctly

Allows invalid placements violating Sudoku rules

✅ Calculate box index as (row//3)*3 + (col//3)

Not choosing the next empty cell carefully, leading to unnecessary branching

Slower solution and possible timeouts

✅ Implement heuristic to pick cell with fewest candidates

Modifying the input board incorrectly or not in-place

May cause unexpected side effects or fail problem requirements

✅ Modify the board in-place as required

🧠

Brute Force Backtracking

💡 This approach is the foundation for solving Sudoku: try every possible number in every empty cell and backtrack when a conflict arises. It teaches the core recursive backtracking technique.

Intuition

Try placing digits 1-9 in the first empty cell, check if valid, then recursively solve the rest. If stuck, backtrack and try a different digit.

Algorithm

1. Find the next empty cell on the board.
2. Try placing digits 1 through 9 in that cell.
3. For each digit, check if placing it violates Sudoku rules (row, column, box).
4. If valid, recursively solve the rest of the board; if recursion fails, backtrack and try next digit.

💡 The challenge is managing the recursion and constraint checks clearly; beginners often miss backtracking or constraint validation.

</>

Code

def solveSudoku(board):
    def is_valid(r, c, ch):
        for i in range(9):
            if board[r][i] == ch: return False
            if board[i][c] == ch: return False
            if board[3*(r//3)+i//3][3*(c//3)+i%3] == ch: return False
        return True

    def backtrack():
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    for ch in '123456789':
                        if is_valid(i, j, ch):
                            board[i][j] = ch
                            if backtrack():
                                return True
                            board[i][j] = '.'
                    return False
        return True

    backtrack()

# Example usage:
if __name__ == '__main__':
    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"]
    ]
    solveSudoku(board)
    for row in board:
        print(row)

Line Notes

def is_valid(r, c, ch):Defines a helper to check if placing ch at (r,c) is valid

for i in range(9):Outer loop to find empty cell row

if board[r][i] == ch: return FalseChecks if ch already exists in the same row

if board[i][c] == ch: return FalseChecks if ch already exists in the same column

if board[3*(r//3)+i//3][3*(c//3)+i%3] == ch: return FalseChecks if ch exists in the 3x3 box

for j in range(9):Inner loop to find empty cell column

if board[i][j] == '.':Found an empty cell to fill

for ch in '123456789':Try all digits 1-9 in the empty cell

if is_valid(i, j, ch):Check if placing ch is valid

board[i][j] = chPlace ch tentatively

if backtrack():Recursively solve rest of board

board[i][j] = '.'Backtrack if recursion fails

return TrueReturn True if entire board is solved

public class SudokuSolver {
    public void solveSudoku(char[][] board) {
        backtrack(board);
    }

    private boolean isValid(char[][] board, int row, int col, char c) {
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == c) return false;
            if (board[i][col] == c) return false;
            if (board[3*(row/3)+i/3][3*(col/3)+i%3] == c) return false;
        }
        return true;
    }

    private boolean backtrack(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    for (char c = '1'; c <= '9'; c++) {
                        if (isValid(board, i, j, c)) {
                            board[i][j] = c;
                            if (backtrack(board)) return true;
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        SudokuSolver solver = new SudokuSolver();
        char[][] 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'}
        };
        solver.solveSudoku(board);
        for (char[] row : board) {
            System.out.println(java.util.Arrays.toString(row));
        }
    }
}

Line Notes

public void solveSudoku(char[][] board)Entry point to start solving the Sudoku

for (int i = 0; i < 9; i++)Loop over rows to find empty cell

for (int j = 0; j < 9; j++)Loop over columns to find empty cell

if (board[i][j] == '.')Check if cell is empty

for (char c = '1'; c <= '9'; c++)Try digits 1-9 in empty cell

if (isValid(board, i, j, c))Check if placing c is valid

board[i][j] = c;Place digit tentatively

if (backtrack(board)) return true;Recursively solve rest of board

board[i][j] = '.';Backtrack if recursion fails

return true;Return true if board is solved

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    bool isValid(vector<vector<char>>& board, int row, int col, char c) {
        for (int i = 0; i < 9; i++) {
            if (board[row][i] == c) return false;
            if (board[i][col] == c) return false;
            if (board[3*(row/3)+i/3][3*(col/3)+i%3] == c) return false;
        }
        return true;
    }

    bool backtrack(vector<vector<char>>& board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    for (char c = '1'; c <= '9'; c++) {
                        if (isValid(board, i, j, c)) {
                            board[i][j] = c;
                            if (backtrack(board)) return true;
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

    void solveSudoku(vector<vector<char>>& board) {
        backtrack(board);
    }
};

int main() {
    vector<vector<char>> 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'}
    };
    Solution sol;
    sol.solveSudoku(board);
    for (auto& row : board) {
        for (auto& c : row) cout << c << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

bool isValid(vector<vector<char>>& board, int row, int col, char c)Checks if placing c at (row,col) is valid

for (int i = 0; i < 9; i++)Find empty cell row

if (board[row][i] == c) return false;Check row for duplicate

if (board[i][col] == c) return false;Check column for duplicate

if (board[3*(row/3)+i/3][3*(col/3)+i%3] == c) return false;Check 3x3 box for duplicate

for (int j = 0; j < 9; j++)Find empty cell column

if (board[i][j] == '.')Empty cell found

for (char c = '1'; c <= '9'; c++)Try digits 1-9

board[i][j] = c;Place digit tentatively

if (backtrack(board)) return true;Recurse to solve rest

board[i][j] = '.';Backtrack if needed

return true;Return true if solved

var solveSudoku = function(board) {
    function isValid(r, c, ch) {
        for (let i = 0; i < 9; i++) {
            if (board[r][i] === ch) return false;
            if (board[i][c] === ch) return false;
            if (board[3 * Math.floor(r / 3) + Math.floor(i / 3)][3 * Math.floor(c / 3) + i % 3] === ch) return false;
        }
        return true;
    }

    function backtrack() {
        for (let i = 0; i < 9; i++) {
            for (let j = 0; j < 9; j++) {
                if (board[i][j] === '.') {
                    for (let ch = 1; ch <= 9; ch++) {
                        let c = ch.toString();
                        if (isValid(i, j, c)) {
                            board[i][j] = c;
                            if (backtrack()) return true;
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

    backtrack();
};

// Example usage:
let 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']
];
solveSudoku(board);
console.log(board.map(row => row.join(' ')).join('\n'));

Line Notes

function isValid(r, c, ch)Helper to check if placing ch at (r,c) is valid

for (let i = 0; i < 9; i++)Find empty cell row

if (board[r][i] === ch) return false;Check row for duplicate

if (board[i][c] === ch) return false;Check column for duplicate

if (board[3 * Math.floor(r / 3) + Math.floor(i / 3)][3 * Math.floor(c / 3) + i % 3] === ch) return false;Check 3x3 box for duplicate

for (let j = 0; j < 9; j++)Find empty cell column

if (board[i][j] === '.')Empty cell found

for (let ch = 1; ch <= 9; ch++)Try digits 1-9

board[i][j] = c;Place digit tentatively

if (backtrack()) return true;Recursively solve rest

board[i][j] = '.';Backtrack if needed

return true;Return true if solved

⏱

Complexity

TimeO(9^(m)) where m is number of empty cells

SpaceO(m) recursion stack for m empty cells

In worst case, each empty cell tries 9 digits, leading to exponential time. Space is proportional to recursion depth.

💡 If there are 20 empty cells, worst case is 9^20 ≈ 1.2e19 operations, which is huge and impractical without pruning.

Interview Verdict: Accepted but slow for large empty boards

This approach is the baseline; it works but can be slow. Interviewers expect you to optimize or explain pruning.

🧠

Backtracking with Constraint Propagation (Using Row, Column, Box Sets)

💡 This approach improves efficiency by precomputing and maintaining sets of used digits per row, column, and box, so validity checks become O(1) instead of O(9). It teaches how to optimize backtracking with auxiliary data structures.

Intuition

Keep track of which digits are already used in each row, column, and box. When trying a digit, quickly check these sets instead of scanning the board.

Algorithm

1. Initialize sets for digits used in each row, column, and 3x3 box.
2. Fill these sets based on the initial board.
3. Backtrack over empty cells, trying digits not in the corresponding sets.
4. Update sets when placing a digit and revert on backtracking.

💡 The key is to maintain and update these sets correctly during recursion to avoid invalid placements efficiently.

</>

Code

def solveSudoku(board):
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    empties = []

    for i in range(9):
        for j in range(9):
            if board[i][j] == '.':
                empties.append((i,j))
            else:
                val = board[i][j]
                rows[i].add(val)
                cols[j].add(val)
                boxes[(i//3)*3 + j//3].add(val)

    def backtrack(idx=0):
        if idx == len(empties):
            return True
        r, c = empties[idx]
        b = (r//3)*3 + c//3
        for ch in '123456789':
            if ch not in rows[r] and ch not in cols[c] and ch not in boxes[b]:
                board[r][c] = ch
                rows[r].add(ch)
                cols[c].add(ch)
                boxes[b].add(ch)
                if backtrack(idx+1):
                    return True
                board[r][c] = '.'
                rows[r].remove(ch)
                cols[c].remove(ch)
                boxes[b].remove(ch)
        return False

    backtrack()

# Example usage:
if __name__ == '__main__':
    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"]
    ]
    solveSudoku(board)
    for row in board:
        print(row)

Line Notes

rows = [set() for _ in range(9)]Initialize sets to track digits used in each row

cols = [set() for _ in range(9)]Initialize sets to track digits used in each column

boxes = [set() for _ in range(9)]Initialize sets to track digits used in each 3x3 box

empties = []List to store coordinates of empty cells

for i in range(9):Iterate over rows to populate sets and empties

if board[i][j] == '.':Record empty cell positions

rows[i].add(val)Add digit to row set

cols[j].add(val)Add digit to column set

boxes[(i//3)*3 + j//3].add(val)Add digit to box set

def backtrack(idx=0):Recursive backtracking over empty cells by index

if idx == len(empties):Base case: all empty cells filled

if ch not in rows[r] and ch not in cols[c] and ch not in boxes[b]:Check if digit can be placed without conflict

rows[r].add(ch)Mark digit as used in row

cols[c].add(ch)Mark digit as used in column

boxes[b].add(ch)Mark digit as used in box

board[r][c] = '.'Backtrack by resetting cell

rows[r].remove(ch)Remove digit from row set on backtrack

cols[c].remove(ch)Remove digit from column set on backtrack

boxes[b].remove(ch)Remove digit from box set on backtrack

import java.util.*;
public class SudokuSolver {
    private Set<Character>[] rows = new HashSet[9];
    private Set<Character>[] cols = new HashSet[9];
    private Set<Character>[] boxes = new HashSet[9];
    private List<int[]> empties = new ArrayList<>();

    public void solveSudoku(char[][] board) {
        for (int i = 0; i < 9; i++) {
            rows[i] = new HashSet<>();
            cols[i] = new HashSet<>();
            boxes[i] = new HashSet<>();
        }
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c == '.') {
                    empties.add(new int[]{i, j});
                } else {
                    rows[i].add(c);
                    cols[j].add(c);
                    boxes[(i/3)*3 + j/3].add(c);
                }
            }
        }
        backtrack(board, 0);
    }

    private boolean backtrack(char[][] board, int idx) {
        if (idx == empties.size()) return true;
        int[] pos = empties.get(idx);
        int r = pos[0], c = pos[1];
        int b = (r/3)*3 + c/3;
        for (char ch = '1'; ch <= '9'; ch++) {
            if (!rows[r].contains(ch) && !cols[c].contains(ch) && !boxes[b].contains(ch)) {
                board[r][c] = ch;
                rows[r].add(ch);
                cols[c].add(ch);
                boxes[b].add(ch);
                if (backtrack(board, idx+1)) return true;
                board[r][c] = '.';
                rows[r].remove(ch);
                cols[c].remove(ch);
                boxes[b].remove(ch);
            }
        }
        return false;
    }

    public static void main(String[] args) {
        SudokuSolver solver = new SudokuSolver();
        char[][] 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'}
        };
        solver.solveSudoku(board);
        for (char[] row : board) {
            System.out.println(Arrays.toString(row));
        }
    }
}

Line Notes

private Set<Character>[] rows = new HashSet[9];Sets to track digits used in each row

private List<int[]> empties = new ArrayList<>();List to store empty cell positions

if (c == '.') { empties.add(new int[]{i, j}); }Record empty cells

rows[i].add(c);Add digit to row set

cols[j].add(c);Add digit to column set

boxes[(i/3)*3 + j/3].add(c);Add digit to box set

private boolean backtrack(char[][] board, int idx)Recursive backtracking over empty cells

if (idx == empties.size()) return true;Base case: all empty cells filled

if (!rows[r].contains(ch) && !cols[c].contains(ch) && !boxes[b].contains(ch))Check if digit can be placed

rows[r].add(ch);Mark digit used in row

board[r][c] = '.';Backtrack by resetting cell

rows[r].remove(ch);Remove digit from row set on backtrack

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

class Solution {
    vector<unordered_set<char>> rows, cols, boxes;
    vector<pair<int,int>> empties;
public:
    void solveSudoku(vector<vector<char>>& board) {
        rows = vector<unordered_set<char>>(9);
        cols = vector<unordered_set<char>>(9);
        boxes = vector<unordered_set<char>>(9);
        empties.clear();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c == '.') {
                    empties.emplace_back(i, j);
                } else {
                    rows[i].insert(c);
                    cols[j].insert(c);
                    boxes[(i/3)*3 + j/3].insert(c);
                }
            }
        }
        backtrack(board, 0);
    }

    bool backtrack(vector<vector<char>>& board, int idx) {
        if (idx == (int)empties.size()) return true;
        int r = empties[idx].first, c = empties[idx].second;
        int b = (r/3)*3 + c/3;
        for (char ch = '1'; ch <= '9'; ch++) {
            if (rows[r].count(ch) == 0 && cols[c].count(ch) == 0 && boxes[b].count(ch) == 0) {
                board[r][c] = ch;
                rows[r].insert(ch);
                cols[c].insert(ch);
                boxes[b].insert(ch);
                if (backtrack(board, idx+1)) return true;
                board[r][c] = '.';
                rows[r].erase(ch);
                cols[c].erase(ch);
                boxes[b].erase(ch);
            }
        }
        return false;
    }
};

int main() {
    vector<vector<char>> 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'}
    };
    Solution sol;
    sol.solveSudoku(board);
    for (auto& row : board) {
        for (auto& c : row) cout << c << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

vector<unordered_set<char>> rows, cols, boxes;Sets to track digits used in rows, columns, boxes

vector<pair<int,int>> empties;Stores empty cell coordinates

if (c == '.') { empties.emplace_back(i, j); }Record empty cells

rows[i].insert(c);Add digit to row set

cols[j].insert(c);Add digit to column set

boxes[(i/3)*3 + j/3].insert(c);Add digit to box set

bool backtrack(vector<vector<char>>& board, int idx)Recursive backtracking function

if (idx == (int)empties.size()) return true;Base case: all empty cells filled

if (rows[r].count(ch) == 0 && cols[c].count(ch) == 0 && boxes[b].count(ch) == 0)Check if digit can be placed

rows[r].insert(ch);Mark digit used in row

board[r][c] = '.';Backtrack by resetting cell

rows[r].erase(ch);Remove digit from row set on backtrack

var solveSudoku = function(board) {
    const rows = Array.from({length:9}, () => new Set());
    const cols = Array.from({length:9}, () => new Set());
    const boxes = Array.from({length:9}, () => new Set());
    const empties = [];

    for (let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {
            const c = board[i][j];
            if (c === '.') {
                empties.push([i, j]);
            } else {
                rows[i].add(c);
                cols[j].add(c);
                boxes[Math.floor(i/3)*3 + Math.floor(j/3)].add(c);
            }
        }
    }

    function backtrack(idx=0) {
        if (idx === empties.length) return true;
        const [r, c] = empties[idx];
        const b = Math.floor(r/3)*3 + Math.floor(c/3);
        for (let ch = 1; ch <= 9; ch++) {
            const val = ch.toString();
            if (!rows[r].has(val) && !cols[c].has(val) && !boxes[b].has(val)) {
                board[r][c] = val;
                rows[r].add(val);
                cols[c].add(val);
                boxes[b].add(val);
                if (backtrack(idx+1)) return true;
                board[r][c] = '.';
                rows[r].delete(val);
                cols[c].delete(val);
                boxes[b].delete(val);
            }
        }
        return false;
    }

    backtrack();
};

// Example usage:
let 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']
];
solveSudoku(board);
console.log(board.map(row => row.join(' ')).join('\n'));

Line Notes

const rows = Array.from({length:9}, () => new Set());Sets to track digits used in rows

const empties = [];Array to store empty cell positions

if (c === '.') { empties.push([i, j]); }Record empty cells

rows[i].add(c);Add digit to row set

cols[j].add(c);Add digit to column set

boxes[Math.floor(i/3)*3 + Math.floor(j/3)].add(c);Add digit to box set

function backtrack(idx=0)Recursive backtracking over empty cells

if (idx === empties.length) return true;Base case: all empty cells filled

if (!rows[r].has(val) && !cols[c].has(val) && !boxes[b].has(val))Check if digit can be placed

rows[r].add(val);Mark digit used in row

board[r][c] = '.';Backtrack by resetting cell

rows[r].delete(val);Remove digit from row set on backtrack

⏱

Complexity

TimeStill O(9^m) worst case but faster pruning and O(1) validity checks

SpaceO(m) recursion stack plus O(27*9) for sets

Using sets reduces validity check from O(9) to O(1), speeding up backtracking significantly.

💡 For 20 empty cells, this approach reduces overhead drastically compared to brute force, making it practical.

Interview Verdict: Accepted and efficient for typical Sudoku puzzles

This is the recommended approach to implement in interviews for Sudoku Solver.

🧠

Backtracking with Heuristic: Most Constrained Cell First

💡 This approach further optimizes backtracking by always choosing the empty cell with the fewest valid options next, reducing the search space drastically.

Intuition

By picking the cell with the least possible digits to try, we minimize branching and detect dead ends earlier.

Algorithm

1. Initialize sets for rows, columns, and boxes as before.
2. Maintain a list of empty cells.
3. At each recursion, pick the empty cell with the fewest valid digits.
4. Try each valid digit, update sets, recurse, and backtrack if needed.

💡 The key is dynamically selecting the most constrained cell to prune the search tree aggressively.

</>

Code

def solveSudoku(board):
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    empties = []

    for i in range(9):
        for j in range(9):
            if board[i][j] == '.':
                empties.append((i,j))
            else:
                val = board[i][j]
                rows[i].add(val)
                cols[j].add(val)
                boxes[(i//3)*3 + j//3].add(val)

    def get_candidates(r, c):
        b = (r//3)*3 + c//3
        return [ch for ch in '123456789' if ch not in rows[r] and ch not in cols[c] and ch not in boxes[b]]

    def backtrack():
        if not empties:
            return True
        # Choose empty cell with fewest candidates
        empties.sort(key=lambda x: len(get_candidates(x[0], x[1])))
        r, c = empties.pop(0)
        b = (r//3)*3 + c//3
        for ch in get_candidates(r, c):
            board[r][c] = ch
            rows[r].add(ch)
            cols[c].add(ch)
            boxes[b].add(ch)
            if backtrack():
                return True
            board[r][c] = '.'
            rows[r].remove(ch)
            cols[c].remove(ch)
            boxes[b].remove(ch)
        empties.insert(0, (r, c))
        return False

    backtrack()

# Example usage:
if __name__ == '__main__':
    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"]
    ]
    solveSudoku(board)
    for row in board:
        print(row)

Line Notes

def get_candidates(r, c):Helper to get all valid digits for cell (r,c)

empties.sort(key=lambda x: len(get_candidates(x[0], x[1])))Sort empties by fewest candidates to pick most constrained cell

r, c = empties.pop(0)Choose cell with fewest options

for ch in get_candidates(r, c):Try all valid digits for chosen cell

empties.insert(0, (r, c))Backtrack by reinserting cell if no digit fits

rows[r].add(ch)Mark digit used in row

board[r][c] = '.'Reset cell on backtrack

import java.util.*;
public class SudokuSolver {
    private Set<Character>[] rows = new HashSet[9];
    private Set<Character>[] cols = new HashSet[9];
    private Set<Character>[] boxes = new HashSet[9];
    private List<int[]> empties = new ArrayList<>();

    public void solveSudoku(char[][] board) {
        for (int i = 0; i < 9; i++) {
            rows[i] = new HashSet<>();
            cols[i] = new HashSet<>();
            boxes[i] = new HashSet<>();
        }
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c == '.') {
                    empties.add(new int[]{i, j});
                } else {
                    rows[i].add(c);
                    cols[j].add(c);
                    boxes[(i/3)*3 + j/3].add(c);
                }
            }
        }
        backtrack(board);
    }

    private List<Character> getCandidates(int r, int c) {
        List<Character> candidates = new ArrayList<>();
        int b = (r/3)*3 + c/3;
        for (char ch = '1'; ch <= '9'; ch++) {
            if (!rows[r].contains(ch) && !cols[c].contains(ch) && !boxes[b].contains(ch)) {
                candidates.add(ch);
            }
        }
        return candidates;
    }

    private boolean backtrack(char[][] board) {
        if (empties.isEmpty()) return true;
        empties.sort(Comparator.comparingInt(a -> getCandidates(a[0], a[1]).size()));
        int[] pos = empties.remove(0);
        int r = pos[0], c = pos[1];
        int b = (r/3)*3 + c/3;
        for (char ch : getCandidates(r, c)) {
            board[r][c] = ch;
            rows[r].add(ch);
            cols[c].add(ch);
            boxes[b].add(ch);
            if (backtrack(board)) return true;
            board[r][c] = '.';
            rows[r].remove(ch);
            cols[c].remove(ch);
            boxes[b].remove(ch);
        }
        empties.add(0, pos);
        return false;
    }

    public static void main(String[] args) {
        SudokuSolver solver = new SudokuSolver();
        char[][] 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'}
        };
        solver.solveSudoku(board);
        for (char[] row : board) {
            System.out.println(Arrays.toString(row));
        }
    }
}

Line Notes

private List<Character> getCandidates(int r, int c)Returns valid digits for cell (r,c)

empties.sort(Comparator.comparingInt(a -> getCandidates(a[0], a[1]).size()));Sort empties by fewest candidates

int[] pos = empties.remove(0);Choose most constrained cell

for (char ch : getCandidates(r, c))Try all valid digits

empties.add(0, pos);Backtrack by reinserting cell

rows[r].add(ch);Mark digit used in row

board[r][c] = '.';Reset cell on backtrack

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;

class Solution {
    vector<unordered_set<char>> rows, cols, boxes;
    vector<pair<int,int>> empties;
public:
    void solveSudoku(vector<vector<char>>& board) {
        rows = vector<unordered_set<char>>(9);
        cols = vector<unordered_set<char>>(9);
        boxes = vector<unordered_set<char>>(9);
        empties.clear();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c == '.') {
                    empties.emplace_back(i, j);
                } else {
                    rows[i].insert(c);
                    cols[j].insert(c);
                    boxes[(i/3)*3 + j/3].insert(c);
                }
            }
        }
        backtrack(board);
    }

    vector<char> getCandidates(int r, int c) {
        vector<char> candidates;
        int b = (r/3)*3 + c/3;
        for (char ch = '1'; ch <= '9'; ch++) {
            if (rows[r].count(ch) == 0 && cols[c].count(ch) == 0 && boxes[b].count(ch) == 0) {
                candidates.push_back(ch);
            }
        }
        return candidates;
    }

    bool backtrack(vector<vector<char>>& board) {
        if (empties.empty()) return true;
        sort(empties.begin(), empties.end(), [&](const pair<int,int>& a, const pair<int,int>& b) {
            return getCandidates(a.first, a.second).size() < getCandidates(b.first, b.second).size();
        });
        auto pos = empties.front();
        empties.erase(empties.begin());
        int r = pos.first, c = pos.second;
        int b = (r/3)*3 + c/3;
        for (char ch : getCandidates(r, c)) {
            board[r][c] = ch;
            rows[r].insert(ch);
            cols[c].insert(ch);
            boxes[b].insert(ch);
            if (backtrack(board)) return true;
            board[r][c] = '.';
            rows[r].erase(ch);
            cols[c].erase(ch);
            boxes[b].erase(ch);
        }
        empties.insert(empties.begin(), pos);
        return false;
    }
};

int main() {
    vector<vector<char>> 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'}
    };
    Solution sol;
    sol.solveSudoku(board);
    for (auto& row : board) {
        for (auto& c : row) cout << c << ' ';
        cout << '\n';
    }
    return 0;
}

Line Notes

vector<char> getCandidates(int r, int c)Returns valid digits for cell (r,c)

sort(empties.begin(), empties.end(), [&](const pair<int,int>& a, const pair<int,int>& b)Sort empties by fewest candidates

auto pos = empties.front();Choose most constrained cell

empties.erase(empties.begin());Remove chosen cell from empties

for (char ch : getCandidates(r, c))Try all valid digits

empties.insert(empties.begin(), pos);Backtrack by reinserting cell

rows[r].insert(ch);Mark digit used in row

board[r][c] = '.';Reset cell on backtrack

var solveSudoku = function(board) {
    const rows = Array.from({length:9}, () => new Set());
    const cols = Array.from({length:9}, () => new Set());
    const boxes = Array.from({length:9}, () => new Set());
    const empties = [];

    for (let i = 0; i < 9; i++) {
        for (let j = 0; j < 9; j++) {
            const c = board[i][j];
            if (c === '.') {
                empties.push([i, j]);
            } else {
                rows[i].add(c);
                cols[j].add(c);
                boxes[Math.floor(i/3)*3 + Math.floor(j/3)].add(c);
            }
        }
    }

    function getCandidates(r, c) {
        const b = Math.floor(r/3)*3 + Math.floor(c/3);
        const candidates = [];
        for (let ch = 1; ch <= 9; ch++) {
            const val = ch.toString();
            if (!rows[r].has(val) && !cols[c].has(val) && !boxes[b].has(val)) {
                candidates.push(val);
            }
        }
        return candidates;
    }

    function backtrack() {
        if (empties.length === 0) return true;
        empties.sort((a,b) => getCandidates(a[0], a[1]).length - getCandidates(b[0], b[1]).length);
        const [r, c] = empties.shift();
        const b = Math.floor(r/3)*3 + Math.floor(c/3);
        for (const ch of getCandidates(r, c)) {
            board[r][c] = ch;
            rows[r].add(ch);
            cols[c].add(ch);
            boxes[b].add(ch);
            if (backtrack()) return true;
            board[r][c] = '.';
            rows[r].delete(ch);
            cols[c].delete(ch);
            boxes[b].delete(ch);
        }
        empties.unshift([r, c]);
        return false;
    }

    backtrack();
};

// Example usage:
let 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']
];
solveSudoku(board);
console.log(board.map(row => row.join(' ')).join('\n'));

Line Notes

function getCandidates(r, c)Returns valid digits for cell (r,c)

empties.sort((a,b) => getCandidates(a[0], a[1]).length - getCandidates(b[0], b[1]).length);Sort empties by fewest candidates

const [r, c] = empties.shift();Choose most constrained cell

for (const ch of getCandidates(r, c))Try all valid digits

empties.unshift([r, c]);Backtrack by reinserting cell

rows[r].add(ch);Mark digit used in row

board[r][c] = '.';Reset cell on backtrack

⏱

Complexity

TimeBetter than previous approaches due to reduced branching, but still exponential worst case

SpaceO(m) recursion stack plus auxiliary sets and empties list

Choosing the most constrained cell reduces the search tree size significantly, improving average runtime.

💡 This heuristic is a common optimization in constraint satisfaction problems to prune search early.

Interview Verdict: Accepted and fastest among backtracking variants

This approach is ideal for interviews if time permits; it shows deeper understanding of heuristics.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, approach 2 (backtracking with sets) is the best balance of clarity and efficiency to implement.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force Backtracking	O(9^m) worst case	O(m) recursion stack	Yes (deep recursion)	N/A (in-place modification)	Mention only - never code due to inefficiency
2. Backtracking with Constraint Sets	O(9^m) but faster due to O(1) checks	O(m) recursion + O(27*9) sets	Yes but manageable	N/A	Code this approach in 95% of interviews
3. Backtracking with Most Constrained Cell Heuristic	Better average case than approach 2	Similar to approach 2 plus sorting overhead	Yes but manageable	N/A	Mention or code if time permits to impress

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain brute force, and progressively optimize. Practice coding and testing thoroughly.

How to Present

Clarify input format and constraints.Describe brute force backtracking approach and its complexity.Explain how to optimize validity checks using sets.Discuss heuristic of choosing the most constrained cell.Write clean, modular code with helper functions.Test on sample and edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 15min → Test: 8min. Total ~30min

What the Interviewer Tests

Interviewer tests your understanding of backtracking, constraint checking, recursion, pruning, and code correctness.

Common Follow-ups

• How to handle boards with multiple solutions? → Return one valid solution or all solutions with modifications.
• Can you optimize further? → Use bitmasks or dancing links algorithm.

💡 Follow-ups test your knowledge of advanced techniques and problem variants.

🔍

Pattern Recognition

When to Use

1) Problem involves filling a grid with constraints; 2) Need to try multiple options per cell; 3) Constraints involve rows, columns, and boxes; 4) Backtracking or DFS is natural solution.

Signature Phrases

fill empty cellsno duplicates in row/column/boxbacktrackingconstraint satisfaction

NOT This Pattern When

Problems that only require greedy or DP without backtracking, e.g., Sudoku Validator (just check validity).

Similar Problems

N-Queens - similar grid backtracking with constraintsWord Search - backtracking on grid with path constraints

Practice

1. You need to generate all combinations of balanced parentheses pairs for a given number n. Which algorithmic approach guarantees generating only valid sequences without generating invalid ones first?

easy

A. Brute force: generate all possible sequences of '(' and ')' of length 2n, then filter valid ones

B. Backtracking with pruning: build sequences by adding '(' or ')' only when it keeps the sequence valid

C. Greedy approach: always add '(' until n is reached, then add ')' to close all opened parentheses

D. Dynamic programming: count the number of valid sequences using Catalan number formula

Solution

1. Step 1: Understand problem constraints

   We want to generate all valid parentheses sequences without generating invalid ones first.

2. Step 2: Analyze approaches

   Brute force generates all sequences including invalid ones, greedy fails to generate all valid sequences, DP counts sequences but does not generate them. Backtracking with pruning adds '(' or ')' only when valid, thus generating only valid sequences.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Backtracking with pruning avoids invalid sequences [OK]

Hint: Backtracking prunes invalid sequences early [OK]

Common Mistakes:

• Thinking greedy can generate all valid sequences
• Confusing counting with generating sequences

2. Given the following code snippet for getPermutation, what is the returned value when calling getPermutation(3, 3)?

easy

A. '123'

B. '312'

C. '213'

D. '231'

Solution

Solution:

1. Step 1: Trace factorial array computation

   factorial = [1, 1, 2] for n=3.

2. Step 2: Calculate indices and build result

   k=3 -> k=2 zero-based. For i=2: idx=2//2=1, pick '2'. For i=1: k=2%2=0, idx=0//1=0, pick '1'. For i=0: k=0%1=0, idx=0//1=0, pick '3'. Result = '213'.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches expected k-th permutation '213' [OK]

Hint: Remember to convert k to zero-based before indexing [OK]

Common Mistakes:

• Off-by-one error in k adjustment
• Wrong index calculation in loop
• Not popping used numbers

3. Consider the following buggy implementation of next permutation. Which line contains the subtle bug that causes incorrect output when the input array is in descending order?

medium

A. Line 5: if i >= 0:

B. Line 13-16: reversing the suffix after pivot

C. Line 10: nums[i], nums[j] = nums[j], nums[i]

D. Line 2: while i >= 0 and nums[i] >= nums[i + 1]: i -= 1

Solution

Solution:

1. Step 1: Identify the bug

   The comment indicates the reversal of the suffix is missing or incorrectly implemented, which is critical when the array is descending (no pivot found).

2. Step 2: Analyze the reversal code

   The reversal loop runs regardless of whether i is -1, which causes incorrect behavior when the entire array is descending; the suffix should be reversed to the lowest permutation.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing or incorrect suffix reversal causes wrong output on descending arrays [OK]

Hint: Suffix reversal must always happen after pivot swap or when no pivot found [OK]

Common Mistakes:

• Not reversing suffix after swap
• Swapping with wrong element
• Ignoring descending array edge case

4. Suppose the problem is modified so that numbers can be reused multiple times in the arrangement. Which change to the backtracking algorithm correctly adapts to this variant?

hard

A. Keep the 'used' bitmask but reset bits after each recursive call to allow reuse.

B. Remove the 'used' bitmask and allow all numbers at every position, checking divisibility only.

C. Use a frequency array to track counts of each number and decrement/increment during recursion.

D. Modify the divisibility condition to allow partial matches and keep the bitmask unchanged.

Solution

1. Step 1: Understand reuse implication

   Allowing reuse means numbers are no longer unique per position, so tracking used numbers is unnecessary.

2. Step 2: Adapt algorithm

   Removing the 'used' bitmask and checking only divisibility conditions at each position correctly counts valid arrangements with reuse.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Without uniqueness constraint, 'used' tracking is redundant [OK]

Hint: Reuse means no need to track used numbers [OK]

Common Mistakes:

• Trying to reset bitmask bits incorrectly
• Using frequency arrays unnecessarily

5. Suppose the problem changes so that each element in the input array can be used multiple times in each permutation (i.e., unlimited reuse). Which modification to the backtracking algorithm correctly generates all unique permutations with duplicates allowed and reuse permitted?

hard

A. Use backtracking without swapping, but at each recursion level, iterate over all elements and skip duplicates using a 'used' boolean array to avoid repeated elements at the same recursion depth.

B. Remove the 'seen' set and allow swapping elements freely without skipping duplicates.

C. Sort the array and use the same swapping and 'seen' set logic as before, but do not increment the recursion start index to allow reuse.

D. Generate all permutations without sorting or skipping duplicates, then filter duplicates at the end using a hash set.

Solution

Solution:

1. Step 1: Understand reuse requirement

   Unlimited reuse means elements can be chosen multiple times at each recursion level, so swapping and incrementing start index is not suitable.

2. Step 2: Identify correct approach

   Backtracking without swapping, iterating over all elements at each recursion level, and using a 'used' boolean array to skip duplicates at the same depth ensures unique permutations with reuse.

3. Step 3: Evaluate other options

   Removing 'seen' causes duplicates; swapping without incrementing start index breaks logic; filtering duplicates after generation is inefficient.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Backtracking with reuse requires iteration over all elements each recursion, not swapping with start index increment [OK]

Hint: Reuse requires iteration over all elements each recursion, not swapping with start index increment [OK]

Common Mistakes:

• Trying to reuse elements by swapping without adjusting recursion index or skipping duplicates properly