608. Fill the Number Grid

HardMatrix Backtracking Hash Table 3 hints

A puzzle magazine prints a 9 x 9 grid of digits split into nine 3 x 3 boxes. Some cells are filled, and the others are marked with the character .. The grid must be completed so that every row, every column and every one of the nine boxes contains each digit from 1 to 9 exactly once.

Complete the grid in place: write the missing digits into board and return nothing. Every input has exactly one solution.

Example 1

Input:: board = [[".",".",".",".",".",".",".",".","2"],[".",".","2","8",".",".","4","5","9"],["5",".",".",".","2","7","8","3","."],[".","2","3",".","5","4","9","6","7"],["4",".","5",".","7",".",".","8","3"],["6","9",".",".",".",".","1",".","."],["9","5",".","7",".",".",".","1","4"],["1","3","4",".","6","9","7","2","."],["2","7","8","3",".",".","5","9","6"]]
Output:: [["3","8","1","4","9","5","6","7","2"],["7","6","2","8","1","3","4","5","9"],["5","4","9","6","2","7","8","3","1"],["8","2","3","1","5","4","9","6","7"],["4","1","5","9","7","6","2","8","3"],["6","9","7","2","3","8","1","4","5"],["9","5","6","7","8","2","3","1","4"],["1","3","4","5","6","9","7","2","8"],["2","7","8","3","4","1","5","9","6"]]
Explanation:: Most digits are given, so every empty cell is forced and filling them one by one completes the grid.

Example 2

Input:: board = [["9",".","3",".","2",".",".",".","."],["5","2",".",".","1",".","3","9","."],["8","1",".",".","6",".","7",".","2"],["2","7",".",".",".","9",".",".","."],[".","4",".",".","3",".","8","2","."],["6","3","5","2","7",".","9",".","4"],["3",".","2",".",".",".","6",".","9"],["7",".",".","4",".","6","2",".","."],["4",".",".",".","5","2","1","7","."]]
Output:: [["9","6","3","5","2","7","4","8","1"],["5","2","7","8","1","4","3","9","6"],["8","1","4","9","6","3","7","5","2"],["2","7","8","1","4","9","5","6","3"],["1","4","9","6","3","5","8","2","7"],["6","3","5","2","7","8","9","1","4"],["3","5","2","7","8","1","6","4","9"],["7","8","1","4","9","6","2","3","5"],["4","9","6","3","5","2","1","7","8"]]
Explanation:: Each missing digit can be deduced from what its row, column and box already contain.

Example 3

Input:: board = [["5","9",".","8",".","2","1",".","."],[".","8",".",".",".","1",".","5","9"],["7","3",".","9",".","6","2",".","."],[".",".",".","1",".",".","5",".","."],[".",".","5","2","9",".",".",".","."],["8","1","7",".",".","5",".",".","."],["6",".","9",".",".",".",".","1","."],[".",".","8","5",".","3","9","6","4"],[".","5","3","4",".",".",".",".","7"]]
Output:: [["5","9","6","8","4","2","1","7","3"],["4","8","2","3","7","1","6","5","9"],["7","3","1","9","5","6","2","4","8"],["9","2","4","1","8","7","5","3","6"],["3","6","5","2","9","4","7","8","1"],["8","1","7","6","3","5","4","9","2"],["6","4","9","7","2","8","3","1","5"],["2","7","8","5","1","3","9","6","4"],["1","5","3","4","6","9","8","2","7"]]
Explanation:: Some cells have several candidates, but only one choice leads to a full grid; the others run into a dead end.

Constraints

board.length == 9 and board[i].length == 9
Each cell is a digit character '1' to '9' or '.'.
The given digits do not break the rules, and exactly one completion exists.

How this problem is judged

Answers: Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Graded: Your answer is read from board after your method returns.

Expected complexity

Time: O(9^m) worst case, far less with pruning
Space: O(1)

What the author was aiming for. Your own solution is not measured against it.

Were you asked this in an interview? Say where, anonymously.

CodeStarter code

Loading the editor…

board =