Given a 9x9 grid represented as a list of lists of strings, where each string is either a digit 1-9 or . indicating an empty cell, fill the grid so that each row, each column, and each of the nine 3x3 sub-grids contains all digits from 1 to 9 exactly once. The input is guaranteed to have exactly one solution. Return the solved grid as a list of lists of strings.
Example 1
Input: [[., 2, 3, 4, 5, 6, 7, 8, 9], [1, ., ., ., ., ., ., ., .], [., ., ., ., ., ., ., ., .], [., ., ., ., ., ., ., ., .], [., ., ., ., ., ., ., ., .], [., ., ., ., ., ., ., ., .], [., ., ., ., ., ., ., ., .], [., ., ., ., ., ., ., ., .], [., ., ., ., ., ., ., ., .]]
Output: [[1, 2, 3, 4, 5, 6, 7, 8, 9], [1, 3, 4, 5, 6, 7, 8, 9, 2], [2, 4, 5, 6, 7, 8, 9, 1, 3], [3, 5, 6, 7, 8, 9, 1, 2, 4], [4, 6, 7, 8, 9, 1, 2, 3, 5], [5, 7, 8, 9, 1, 2, 3, 4, 6], [6, 8, 9, 1, 2, 3, 4, 5, 7], [7, 9, 1, 2, 3, 4, 5, 6, 8], [8, 1, 2, 3, 4, 5, 6, 7, 9]],
Explanation: A simple grid with only the first row filled except for the first cell.
Example 2
Input: [[., ., ., 2, 6, ., 7, ., 1], [6, 8, ., ., 7, ., ., 9, .], [1, 9, ., ., ., 4, 5, ., .], [8, 2, ., 1, ., ., ., 4, . ], [., ., 4, 6, ., 2, 9, ., .], [., 5, ., ., ., 3, ., 2, 8], [., ., 9, 3, ., ., ., 7, 4], [., 4, ., ., 5, ., ., 3, 6], [7, ., 3, ., 1, 8, ., ., .]]
Output: [[4, 3, 5, 2, 6, 9, 7, 8, 1], [6, 8, 2, 5, 7, 1, 4, 9, 3], [1, 9, 7, 8, 3, 4, 5, 6, 2], [8, 2, 6, 1, 9, 5, 3, 4, 7], [3, 7, 4, 6, 8, 2, 9, 1, 5], [9, 5, 1, 7, 4, 3, 6, 2, 8], [5, 1, 9, 3, 2, 6, 8, 7, 4], [2, 4, 8, 9, 5, 7, 1, 3, 6], [7, 6, 3, 4, 1, 8, 2, 5, 9]]
Explanation: A partially filled grid with a unique solution.
Constraints
Case 1
Input: [['.', '.', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', '.', '.']]
Expected: [['1', '2', '3', '4', '5', '6', '7', '8', '9'], ['2', '3', '4', '5', '6', '7', '8', '9', '1'], ['3', '4', '5', '6', '7', '8', '9', '1', '2'], ['4', '5', '6', '7', '8', '9', '1', '2', '3'], ['5', '6', '7', '8', '9', '1', '2', '3', '4'], ['6', '7', '8', '9', '1', '2', '3', '4', '5'], ['7', '8', '9', '1', '2', '3', '4', '5', '6'], ['8', '9', '1', '2', '3', '4', '5', '6', '7'], ['9', '1', '2', '3', '4', '5', '6', '7', '8']]
Case 2
Input: [['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']]
Expected: [['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']]