Sudoku Solver (Taco Edition)

In this problem, you are given a partially filled Sudoku board and you need to complete it following the standard Sudoku rules:

• Each row must contain the digits 1-9 without repetition.
• Each column must contain the digits 1-9 without repetition.
• Each of the 3×3 sub-grids must contain the digits 1-9 without repetition.

If a valid solution exists, output the solved board; otherwise, output No solution exists.

The problem may also present an empty board (all cells are '.') which must be completed into a valid Sudoku solution. Note that for an empty board, multiple solutions exist; you may output any valid solution.

The underlying algorithm is based on backtracking. Good luck!

inputFormat

The input consists of 9 lines, each containing exactly 9 characters. Each character is either a digit ('1'-'9') indicating a prefilled number, or a dot ('.') indicating an empty cell.

outputFormat

If a valid solution exists, output the completed Sudoku board as 9 lines with 9 digits each. If no solution exists, output the string No solution exists.

## sample

53..7....
6..195...
.98....6.
8...6...3
4..8.3..1
7...2...6
.6....28.
...419..5
....8..79

534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179

</p>