Complete the Number Grid
HardBacktracking
Problem
A 9 × 9 number grid is given as board, nine strings of nine characters; each character is a digit 1–9 or . for an empty cell. Fill every empty cell so that each row, each column and each of the nine 3 × 3 boxes contains every digit from 1 to 9 exactly once.
The puzzle is guaranteed to have exactly one solution. Return the solved grid in the same format.
Example 1
- Input:
- board = ["53..7....", "6..195...", ".98....6.", "8...6...3", "4..8.3..1", "7...2...6", ".6....28.", "...419..5", "....8..79"]
- Output:
- ["534678912", "672195348", "198342567", "859761423", "426853791", "713924856", "961537284", "287419635", "345286179"]
Each row, column and box of the result holds 1–9 once, and every given digit is kept.
Example 2
- Input:
- board = [".....8..5", "3..9..8..", "..15....9", "51.7.34.6", "8.4...1..", "...1.42..", ".6741..8.", "425.....1", "1....6..."]
- Output:
- ["249368715", "356971824", "781542639", "512783496", "874629153", "693154278", "967415382", "425837961", "138296547"]
Constraints
- board has 9 strings of length 9.
- Each character is '1'–'9' or '.'.
- The puzzle has exactly one solution.
Hint
Show the first hint
Try a digit in an empty cell, continue, and undo it if you get stuck. What makes a digit allowed?
Walkthrough
How to approach it
01Clarify before coding
- Is the solution unique? Yes, so the first complete grid found is the answer.
- Can the input already be complete? Yes; return it unchanged.
- Output format? The same nine strings with no '.' left.
02Brute force
Try every digit in every empty cell in reading order and only check validity when the grid is full.
Cost: 9^e for e empty cells: 9^51 for the first example, astronomically large.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.