Write a program to solve a Sudoku puzzle by filling the empty cells. A sudoku solution must satisfy all of the following rules:
-
Each of the digits
1-9
must occur exactly once in each row. -
Each of the digits
1-9
must occur exactly once in each column. -
Each of the digits
1-9
must occur exactly once in each of the 9 3x3 sub-boxes of the grid.
Problem Note:
-
The given board contains only digits 1-9 and the character
'.'
. - Empty cells are shown by the character ' . '
- You may assume that the given Sudoku puzzle will have a single unique solution.
- The board size is always 9x9.
Example
Input: A given sudoku puzzle:
Output: Solution numbers are marked in blue.