DSA interview question

Sudoku Solver

Hard · Algorithms · Topics: recursion, backtracking

The problem

A puzzle app lets users photograph a newspaper Sudoku and wants the solution filled in. Each row, column and 3 × 3 box must contain the digits 1–9 exactly once, and the given digits can't change. The classic approach is backtracking: pick an empty cell, try each digit that doesn't clash with its row, column or box, recurse, and undo on failure. Two refinements make it fast. Bitmasks per row, column and box make the clash check O(1), and always filling the empty cell with the fewest candidates first (the "minimum remaining values" heuristic) cuts the search dramatically.

Example: the LeetCode board beginning 53..7.... / 6..195... → its unique solution beginning 534678912 / 672195348.

Function signature

void solveSudoku(vector<vector<char>>& board);  // '.' marks empty cells; solved in place

Test cases

Input	Output	Explanation
The LeetCode 37 example board	`534678912 / 672195348 / 198342567 / 859761423 / 426853791 / 713924856 / 961537284 / 287419635 / 345286179`	The unique solution
The solution above with cell (0, 0) blanked	`5` placed at (0, 0)	Only one digit fits
An empty board	Any valid completed grid	Many solutions; the solver returns one

(Confirm: the input has at least one solution; givens must not change; the board is 9 × 9 with '.' for blanks.)

How interviewers phrase it

"Write a program to solve a Sudoku puzzle by filling the empty cells" (LeetCode 37).
Checking a partially filled board without solving it is LeetCode 36 (Valid Sudoku).

Clarifying questions to ask

Is a solution guaranteed to exist? (Yes, in LeetCode's version.)
Should the board be modified in place?
Is any valid solution acceptable if several exist?

Follow-ups to expect

"How do you check a digit is allowed in O(1)?"
"Which cell do you fill next?"
"How do you undo?"
"What's the complexity?"
"More advanced techniques?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview