Complete the Sudoku

Hard

You get a 9 × 9 sudoku board grid. Each cell holds a digit from '1' to '9' or a dot '.', which marks an empty cell. Fill in every empty cell so that: - each row contains every digit from 1 to 9 exactly once; - so does each column; - and so does each of the nine 3 × 3 squares the board is split into. Return the filled board. The board is guaranteed to have exactly one solution.

Example 1

grid=[['.', '.', '.', '9', '7', '2', '.', '8', '5'], ['.', '.', '2', '.', '.', '.', '6', '.', '4'], ['.', '.', '.', '.', '.', '.', '3', '.', '.'], ['.', '8', '.', '.', '9', '.', '.', '5', '.'], ['4', '5', '.', '2', '.', '3', '.', '7', '6'], ['.', '7', '.', '.', '6', '.', '.', '1', '.'], ['.', '.', '6', '.', '.', '.', '.', '.', '.'], ['9', '.', '5', '.', '.', '.', '2', '.', '.'], ['8', '2', '.', '6', '1', '4', '.', '.', '.']] → [['3', '6', '4', '9', '7', '2', '1', '8', '5'], ['7', '1', '2', '3', '5', '8', '6', '9', '4'], ['5', '9', '8', '1', '4', '6', '3', '2', '7'], ['6', '8', '3', '7', '9', '1', '4', '5', '2'], ['4', '5', '1', '2', '8', '3', '9', '7', '6'], ['2', '7', '9', '4', '6', '5', '8', '1', '3'], ['1', '3', '6', '5', '2', '9', '7', '4', '8'], ['9', '4', '5', '8', '3', '7', '2', '6', '1'], ['8', '2', '7', '6', '1', '4', '5', '3', '9']]

In the returned board every dot is replaced by a digit, and each row, column and 3 × 3 square holds the digits 1 to 9 without repeats.

Example 2

grid=[['.', '.', '.', '9', '7', '2', '.', '8', '5'], ['.', '.', '2', '.', '.', '.', '6', '.', '4'], ['.', '.', '.', '.', '.', '.', '3', '.', '.'], ['.', '8', '.', '.', '9', '.', '.', '5', '.'], ['4', '5', '.', '2', '.', '3', '.', '7', '6'], ['.', '7', '.', '.', '6', '.', '.', '1', '.'], ['.', '.', '6', '.', '.', '.', '.', '.', '.'], ['9', '.', '5', '.', '.', '.', '2', '.', '.'], ['8', '2', '.', '6', '1', '4', '.', '.', '.']] → [['3', '6', '4', '9', '7', '2', '1', '8', '5'], ['7', '1', '2', '3', '5', '8', '6', '9', '4'], ['5', '9', '8', '1', '4', '6', '3', '2', '7'], ['6', '8', '3', '7', '9', '1', '4', '5', '2'], ['4', '5', '1', '2', '8', '3', '9', '7', '6'], ['2', '7', '9', '4', '6', '5', '8', '1', '3'], ['1', '3', '6', '5', '2', '9', '7', '4', '8'], ['9', '4', '5', '8', '3', '7', '2', '6', '1'], ['8', '2', '7', '6', '1', '4', '5', '3', '9']]

Constraints

grid has 9 rows of 9 cells
Each cell is a digit from '1' to '9' or '.'
The filled cells do not break the rules
The board has exactly one solution

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table Backtracking Matrix

Similar problems

Every Way to Space the Words Hard Words Hidden in a Letter Grid Hard Six-Cell Tile Slider Hard Square-Sum Chains Hard Rectangles With a Given Sum Hard

Input

grid=[['.', '.', '.', '9', '7', '2', '.', '8', '5'], ['.', '.', '2', '.', '.', '.', '6', '.', '4'], ['.', '.', '.', '.', '.', '.', '3', '.', '.'], ['.', '8', '.', '.', '9', '.', '.', '5', '.'], ['4', '5', '.', '2', '.', '3', '.', '7', '6'], ['.', '7', '.', '.', '6', '.', '.', '1', '.'], ['.', '.', '6', '.', '.', '.', '.', '.', '.'], ['9', '.', '5', '.', '.', '.', '2', '.', '.'], ['8', '2', '.', '6', '1', '4', '.', '.', '.']]

Expected

[['3', '6', '4', '9', '7', '2', '1', '8', '5'], ['7', '1', '2', '3', '5', '8', '6', '9', '4'], ['5', '9', '8', '1', '4', '6', '3', '2', '7'], ['6', '8', '3', '7', '9', '1', '4', '5', '2'], ['4', '5', '1', '2', '8', '3', '9', '7', '6'], ['2', '7', '9', '4', '6', '5', '8', '1', '3'], ['1', '3', '6', '5', '2', '9', '7', '4', '8'], ['9', '4', '5', '8', '3', '7', '2', '6', '1'], ['8', '2', '7', '6', '1', '4', '5', '3', '9']]

Run checks the first 3 tests in your browser. Submit checks all 30 tests on the server, hidden ones included.