L15. Sudoko Solver | Backtracking

Main ideas / concepts covered

• The video explains how to solve an incomplete Sudoku (a puzzle that has at least one valid solution, possibly more than one) using backtracking.
• It begins by defining Sudoku structure and rules, then outlines the solving strategy:
  • Find the first empty cell.
  • Try placing digits 1 through 9 in that cell if the placement is valid (respects Sudoku constraints).
  • Recurse to solve the rest of the board.
  • If a choice leads to a dead end, undo it (backtrack) and try the next digit.
• The approach is described as returning one valid Sudoku solution, not all possible solutions, and therefore stops searching once a valid completion is found.

Sudoku rules (constraints the solver must satisfy)

• The Sudoku board is 9×9, divided into nine 3×3 subgrids (boxes).
• For every placement of numbers 1–9, the following must hold:

1. Row rule: Each digit 1–9 appears exactly once in every row.
2. Column rule: Each digit 1–9 appears exactly once in every column.
3. Box rule: Each digit 1–9 appears exactly once in every 3×3 subgrid.

Backtracking methodology (detailed step-by-step)

• Data representation

  • The Sudoku is stored as a 9×9 grid of characters (conceptually mentioned as C++ vector<vector<char>>).

• Core recursive function: solve(board) (Boolean return)

  • Step 1: Find the first empty cell

    • Traverse the grid in row-major order.
    • Select the first cell marked as “empty”.

  • Step 2: Try digits 1 through 9

    • For each candidate digit val from 1 to 9:
      • Check whether placing val at the empty cell is valid with respect to:
        • the current row,
        • the current column,
        • the current 3×3 box.
      • If valid:
        • Place the digit.
        • Recurse: call solve(board) again.
      • If recursion returns true:
        • Propagate true upward (solution found).
      • If recursion returns false:
        • Backtrack by clearing/removing the digit and try the next candidate.

  • Step 3: Dead-end handling

    • If no digit 1–9 can be placed in the empty cell, return false.

  • Step 4: Completion handling

    • If there are no empty cells left:
      • The board is fully filled consistently, so return true.

• Important stopping logic

  • Once a recursive path returns true, the solver stops and does not try additional digits/branches.
  • The video contrasts:
    • solving for one valid Sudoku (stop early),
    • vs. enumerating all solutions (more complex).

Validity checking (“isValid”) logic

• To test whether a number can be placed:

  • Ensure the candidate does not already appear in the row, column, or 3×3 box.

• 3×3 subgrid identification

  • The subgrid location is computed using division and modulo by 3:
    • Use division by 3 to find the block row/box row.
    • Use modulo 3 to determine position within the block grid.

• The described approach uses single-iteration checks across row/column/box elements (rather than separate loops per structure).

Subgrid indexing approach (as described)

• For a cell at position (i, j):
  • The subgrid boundaries are determined by grouping indices into blocks of size 3.
  • The video mentions formulas like:
    • block base row: (i / 3) * 3
    • block base column: (j / 3) * 3
  • It also discusses modulo 3 to handle offsets within the 3×3 span.

Note: The subtitles’ math/wording is sometimes garbled, but the core intent is to locate the 3×3 box using division/modulo by 3.

Speakers / sources featured

• Primary speaker: “Striver” (referred to by the narrator as “hey striver”)
• Company/source mentioned (promotional segment): Coding Ninjas (an external coding education provider, mentioned during an advertisement)