All problems

Sudoku Solver

Hard · backtracking

A Sudoku board is a 9 by 9 grid split into nine 3 by 3 boxes. Some cells already hold a digit from 1 to 9; the others are empty. A solved board has a digit in every cell such that each row, each column and each of the nine 3 by 3 boxes contains every digit from 1 to 9 exactly once.

You are given board, a 9 by 9 grid of characters. A cell holds the character '1' to '9' if it is filled, or '.' if it is empty. Fill in every empty cell so that the board is solved, without changing any digit that was already there.

The board is guaranteed to have exactly one solution. Return the completed board in the same shape, with every cell a digit character.

Examples

Example 1

Input: board = [["4", "7", "3", "1", "5", "9", "6", "2", "8"], ["8", "6", "2", "3", "7", "4", "5", ".", "9"], ["9", "5", "1", "2", "6", "8", "7", "3", "4"], ["5", "1", "4", "9", "2", "6", "3", "8", "7"], ["6", ".", "9", "8", "3", ".", "1", "4", "5"], ["7", "3", "8", "4", "1", "5", "2", "9", "6"], ["2", "9", "5", "6", "8", "3", "4", "7", "1"], ["1", "4", "7", "5", "9", "2", "8", "6", "3"], ["3", "8", "6", "7", "4", "1", "9", "5", "2"]]

Output: [["4", "7", "3", "1", "5", "9", "6", "2", "8"], ["8", "6", "2", "3", "7", "4", "5", "1", "9"], ["9", "5", "1", "2", "6", "8", "7", "3", "4"], ["5", "1", "4", "9", "2", "6", "3", "8", "7"], ["6", "2", "9", "8", "3", "7", "1", "4", "5"], ["7", "3", "8", "4", "1", "5", "2", "9", "6"], ["2", "9", "5", "6", "8", "3", "4", "7", "1"], ["1", "4", "7", "5", "9", "2", "8", "6", "3"], ["3", "8", "6", "7", "4", "1", "9", "5", "2"]]

Only three cells were empty. The empty cell in the second row has to be 1, because every other digit already appears in its row or column.

Example 2

Input: board = [["8", "3", "7", "9", "5", "1", "6", "2", "4"], ["2", "4", "6", "7", "3", ".", "9", "1", "5"], ["1", "5", "9", "6", "4", "2", "7", "8", "3"], ["5", "7", "1", "2", "9", "4", "8", "3", "6"], [".", "6", "8", ".", "7", "5", "2", "4", "9"], ["4", "9", "2", "8", "6", "3", "1", "5", "7"], ["6", "2", "3", "5", "8", "7", "4", "9", "1"], ["7", "8", ".", "4", "1", "9", ".", "6", "."], ["9", "1", "4", "3", "2", "6", "5", "7", "8"]]

Output: [["8", "3", "7", "9", "5", "1", "6", "2", "4"], ["2", "4", "6", "7", "3", "8", "9", "1", "5"], ["1", "5", "9", "6", "4", "2", "7", "8", "3"], ["5", "7", "1", "2", "9", "4", "8", "3", "6"], ["3", "6", "8", "1", "7", "5", "2", "4", "9"], ["4", "9", "2", "8", "6", "3", "1", "5", "7"], ["6", "2", "3", "5", "8", "7", "4", "9", "1"], ["7", "8", "5", "4", "1", "9", "3", "6", "2"], ["9", "1", "4", "3", "2", "6", "5", "7", "8"]]

Six empty cells. Each one is forced by the digits that already appear in its row, column and box.

Constraints