Sudoku Solver

Sudoku is a popular puzzle that originated in 18th-century Switzerland. The puzzle consists of a 9 × 9 grid. Some cells are pre-filled with digits, and the goal is to fill the remaining cells so that each row, each column, and each of the nine 3 × 3 sub-grids contains all the digits from \(1\) to \(9\) without repetition.

Formally, let \(G\) be a 9 × 9 matrix. The objective is to fill the empty cells (denoted by 0) such that:

1. Every row contains each of the digits \(1\) through \(9\) exactly once.
2. Every column contains each of the digits \(1\) through \(9\) exactly once.
3. Every \(3 \times 3\) sub-grid (delineated by bold lines) contains each of the digits \(1\) through \(9\) exactly once.

inputFormat

The input consists of 9 lines, each line containing 9 space-separated integers. The integer 0 represents an empty cell in the Sudoku board.

outputFormat

Output the solved Sudoku board in the same format: 9 lines where each line contains 9 space-separated integers. It is guaranteed that the puzzle has a unique solution.

sample

5 3 0 0 7 0 0 0 0
6 0 0 1 9 5 0 0 0
0 9 8 0 0 0 0 6 0
8 0 0 0 6 0 0 0 3
4 0 0 8 0 3 0 0 1
7 0 0 0 2 0 0 0 6
0 6 0 0 0 0 2 8 0
0 0 0 4 1 9 0 0 5
0 0 0 0 8 0 0 7 9

5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9