Fill the empty cells of a Sudoku puzzle and return the finished board.
The board has 9 rows and 9 columns. A filled cell holds a digit from "1" to "9". An empty cell is the character ".". A correct solution follows all these rules:
- Each row has the digits
1 to 9, each exactly once.
- Each column has the digits
1 to 9, each exactly once.
- Each of the nine
3 x 3 boxes has the digits 1 to 9, each exactly once.
Return the board with every empty cell filled.
Examples
Example 1:
Input: board = [["3","9",".","1",".","2","5","6","4"],["4","6",".","8","9","3","1","7","2"],["2","7","1","5","6","4","8","9","3"],["8","4","9",".","3","1","6","2","5"],["1","3","7","6","2","5","9","4","."],["5","2","6","9","4","8","7","3","1"],["9","5","4","3","8","7","2","1","6"],["7","8","3","2",".","6","4","5","9"],["6","1","2","4","5","9","3","8","7"]]
Output: [["3","9","8","1","7","2","5","6","4"],["4","6","5","8","9","3","1","7","2"],["2","7","1","5","6","4","8","9","3"],["8","4","9","7","3","1","6","2","5"],["1","3","7","6","2","5","9","4","8"],["5","2","6","9","4","8","7","3","1"],["9","5","4","3","8","7","2","1","6"],["7","8","3","2","1","6","4","5","9"],["6","1","2","4","5","9","3","8","7"]]
Explanation: Only a few cells are empty. Each of them has just one digit that fits.
Example 2:
Input: board = [[".","1",".",".","6",".",".","3","9"],[".","5","6",".",".","9","8",".","."],[".",".","2","4",".","1","6",".","."],["5",".","3",".",".","8","7","1","6"],[".",".",".","5",".",".",".",".","."],[".","8","4","1",".","6",".","5","."],[".","7","1",".","5",".",".","2","."],[".","4","9",".",".",".",".","6","3"],["6","3","5",".",".",".","1","8","."]]
Output: [["4","1","8","7","6","5","2","3","9"],["7","5","6","3","2","9","8","4","1"],["3","9","2","4","8","1","6","7","5"],["5","2","3","9","4","8","7","1","6"],["1","6","7","5","3","2","4","9","8"],["9","8","4","1","7","6","3","5","2"],["8","7","1","6","5","3","9","2","4"],["2","4","9","8","1","7","5","6","3"],["6","3","5","2","9","4","1","8","7"]]
Explanation: Many cells are empty, but this puzzle still has exactly one solution.