Sudoku Solver

Given a 9×9 Sudoku board, where empty cells are represented by a dot (.), fill the board so that each row, each column, and each of the nine 3×3 sub-boxes contains all of the digits from 1 to 9 exactly once.

You are required to implement a backtracking algorithm to complete the board. In mathematical terms, if we denote the board as \(board[i][j]\) for \(0 \le i,j < 9\), then for all indices \(i\) and \(j\), the following must hold:

• Each row \(i\) contains digits \(1,2,...,9\) without repetition.
• Each column \(j\) contains digits \(1,2,...,9\) without repetition.
• Each 3×3 box contains digits \(1,2,...,9\) without repetition.

You must read the board from standard input and output the solved board to standard output.

inputFormat

The input consists of exactly 9 lines. Each line contains a string of 9 characters. Each character is either a digit ('1'-'9') indicating a filled cell or a dot ('.') indicating an empty cell.

outputFormat

Output the completed sudoku board in 9 lines, where each line is a string of 9 digits (with no spaces) representing a row of the solved board.

## 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>