Given a 9x9 grid represented as a list of lists of strings, where each element is either a digit 1-9 or the character ., fill the empty cells (.) so that each digit 1-9 appears exactly once in each row, column, and each of the nine 3x3 subgrids. The input grid is guaranteed to have exactly one solution. Return the solved grid as a list of lists of strings.
Example 1
Input: [[., 2, ., 4, 5, ., 7, ., 9], [1, ., ., ., ., 6, ., 8, .], [., ., 3, ., ., ., 1, ., .], [., ., ., 2, ., ., ., 5, .], [., 6, ., ., ., ., ., 3, .], [., 1, ., ., ., 7, ., ., .], [., ., 8, ., ., ., 4, ., .], [., 9, ., 6, ., ., ., ., 2], [5, ., 7, ., 8, 4, ., 1, .]]
Output: [[8, 2, 1, 4, 5, 3, 7, 6, 9], [1, 5, 9, 7, 2, 6, 3, 8, 4], [6, 7, 3, 8, 9, 2, 1, 5, 2], [3, 8, 4, 2, 1, 9, 6, 5, 7], [7, 6, 5, 9, 4, 8, 2, 3, 1], [9, 1, 2, 5, 6, 7, 8, 4, 3], [2, 4, 8, 1, 3, 5, 4, 9, 6], [4, 9, 6, 6, 7, 1, 5, 2, 8], [5, 3, 7, 3, 8, 4, 9, 1, 5]]
Explanation: A new valid Sudoku solution for the given input grid.
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 new valid Sudoku solution for the given input grid.
Constraints
Case 1
Input: [['.', '7', '.', '.', '4', '.', '.', '2', '6'], ['6', '.', '.', '1', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '9', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '2', '.', '.'], ['.', '3', '.', '.', '.', '.', '.', '7', '.'], ['.', '.', '8', '.', '.', '.', '.', '.', '.'], ['.', '.', '.', '6', '.', '.', '.', '.', '.'], ['.', '.', '.', '.', '.', '.', '.', '.', '9'], ['2', '6', '.', '.', '8', '.', '.', '1', '.']]
Expected: [['8', '7', '9', '3', '4', '1', '5', '2', '6'], ['6', '2', '3', '1', '7', '5', '9', '8', '4'], ['1', '4', '5', '2', '6', '9', '7', '3', '8'], ['7', '8', '6', '4', '9', '3', '2', '5', '1'], ['5', '3', '2', '8', '1', '6', '4', '7', '9'], ['4', '9', '8', '5', '2', '7', '1', '6', '3'], ['3', '1', '4', '6', '5', '8', '8', '9', '7'], ['2', '5', '7', '7', '3', '4', '6', '1', '9'], ['2', '6', '1', '9', '8', '5', '3', '1', '7']]
Case 2
Input: [['.', '.', '5', '3', '.', '.', '.', '.', '.'], ['8', '.', '.', '.', '.', '.', '.', '2', '.'], ['.', '7', '.', '.', '1', '.', '5', '.', '.'], ['4', '.', '.', '.', '.', '5', '3', '.', '.'], ['.', '1', '.', '.', '7', '.', '.', '.', '6'], ['.', '.', '3', '2', '.', '.', '.', '8', '.'], ['.', '6', '.', '5', '.', '.', '.', '.', '9'], ['.', '.', '4', '.', '.', '.', '.', '3', '.'], ['.', '.', '.', '.', '.', '9', '7', '.', '.']]
Expected: [['1', '4', '5', '3', '2', '7', '6', '9', '8'], ['8', '3', '9', '6', '5', '4', '1', '2', '7'], ['6', '7', '2', '9', '1', '8', '5', '4', '3'], ['4', '9', '6', '1', '8', '5', '3', '7', '2'], ['2', '1', '8', '4', '7', '3', '9', '5', '6'], ['7', '5', '3', '2', '9', '6', '8', '1', '4'], ['3', '6', '7', '5', '4', '2', '2', '8', '9'], ['5', '8', '4', '7', '6', '1', '2', '3', '9'], ['9', '2', '1', '8', '3', '9', '7', '6', '5']]