Sudoku Solver

HardBacktrackingconstraint backtracking

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Write a function that solves a 9x9 Sudoku puzzle by filling in every empty cell. The board is given as a 9x9 grid of characters. Each cell holds either a digit character '1' through '9' (an already-filled clue) or '.' (an empty cell that you must fill in). A completed Sudoku must satisfy all three of the following constraints: - Every **row** contains each digit '1'-'9' exactly once. - Every **column** contains each digit '1'-'9' exactly once. - Every one of the nine **3x3 sub-boxes** (the non-overlapping blocks that tile the grid) contains each digit '1'-'9' exactly once. You are guaranteed that the input is a valid puzzle with **exactly one** solution. Modify the grid in place to hold that solution, and return the filled board. The returned value should be the same 9x9 char[][] with every '.' replaced by the correct digit.

Examples

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"]]
Every blank cell is filled so that each row, column, and 3x3 box contains the digits 1-9 with no repeats.
Input: board = [[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."],[".",".",".",".",".",".",".",".","."]]
Output: [["1","2","3","4","5","6","7","8","9"],["4","5","6","7","8","9","1","2","3"],["7","8","9","1","2","3","4","5","6"],["2","1","4","3","6","5","8","9","7"],["3","6","5","8","9","7","2","1","4"],["8","9","7","2","1","4","3","6","5"],["5","3","1","6","4","2","9","7","8"],["6","4","2","9","7","8","5","3","1"],["9","7","8","5","3","1","6","4","2"]]
An empty board admits many valid fillings; this is the first one found scanning cells left-to-right, top-to-bottom and trying digits 1-9 in order.

Constraints

  • The board is exactly 9 rows by 9 columns.
  • Each cell is one of the characters `'1'`-`'9'` or `'.'`.
  • The given clues do not violate any row, column, or box constraint.
  • The puzzle is guaranteed to have exactly one valid solution.
  • You must fill the board in place and return it.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.