Sudoku Solver Problem | using Backtracking | Leetcode Hard

Main ideas / lesson conveyed

• The video explains how to solve Sudoku using recursion + backtracking (referred to as “reaction/backtracking” as the core approach).
• Sudoku rules are enforced via three constraints for every candidate digit:
  1. Row constraint (horizontal): A digit cannot repeat anywhere else in the same row.
  2. Column constraint (vertical): A digit cannot repeat anywhere else in the same column.
  3. 3×3 subgrid constraint (individual grid): A digit cannot repeat anywhere else within the cell’s 3×3 box.
• The algorithm fills the board row-wise (left to right, top to bottom) and uses backtracking when a placement leads to a dead end.
• Assumption: the given Sudoku has a unique solution.

Problem setup (what the input represents)

• The Sudoku board is a 9×9 grid, represented as vector<vector<char>> board.
• Empty cells are represented by a dot character '.'.
• Digits are represented as characters '1' to '9'.

Methodology / step-by-step algorithm (backtracking)

1) Recursive solver: SudokuSolve(board, row, column) (conceptual flow)

• Start call: from (row=0, column=0).

Base case (termination success)

• When row == 9, all rows have been processed → return true (Sudoku solved).

If current cell already has a digit

• If the current cell is not '.':
  • Move to the next cell (compute next row/column).
  • Recurse and return that result.

If current cell is empty ('.')

• Try all digits '1' to '9':
  • For each digit:
    • Check whether it is safe to place it using the safety rules (below).
    • If safe:
      • Place the digit in board[row][column].
      • Recurse to the next cell.
      • If recursion returns true, propagate true upward.
    • If recursion returns false:
      • Backtrack by resetting board[row][column] = '.'.
• If no digit works → return false.

Next cell computation (row-wise traversal)

• Normally:
  • nextRow = row
  • nextCol = column + 1
• Exception when column == 8 (end of the row):
  • nextRow = row + 1
  • nextCol = 0

2) Helper / safety function: isSafe(board, row, column, digit) (three checks)

A) Row check (horizontal)

• Scan all columns j from 0 to 8 in the same row:
  • If board[row][j] == digit for any j, return false.

B) Column check (vertical)

• Scan all rows i from 0 to 8 in the same column:
  • If board[i][column] == digit for any i, return false.

C) 3×3 subgrid check

• Compute the subgrid’s top-left starting indices:
  • startRow = (row / 3) * 3
  • startCol = (column / 3) * 3
• Scan the 3×3 box:
  • for i from startRow to startRow + 2
  • for j from startCol to startCol + 2
  • if board[i][j] == digit, return false
• If all three checks pass → return true.

3) Backtracking intuition (what happens when stuck)

• The solver places digits greedily among valid options.
• Eventually it may reach an empty cell where no digit from '1' to '9' is safe.
• Then it:
  • returns false from the recursion,
  • undoes the last placement (sets the cell back to '.'),
  • tries the next candidate digit in the previous cell.

Complexity discussion (as stated)

• Time complexity is hard to compute precisely due to pruning and varying puzzle structure.
• Conceptually:
  • For each empty cell you might try up to 9 digits.
  • If there are x empty cells, the worst-case search space is about 9^x combinations.
• The 3×3 box check is small/constant work (bounded by scanning at most 9 cells).

Speakers / sources featured

• Primary speaker: The YouTube presenter/author (no name given in subtitles).
• Source referenced: LeetCode (Sudoku Solver problem, mentioned as “problem number 37”).
• Other concept referenced: N-Queens problem (from previous lecture).