Sudoku Solver

Solve the classic Sudoku puzzle. The Sudoku board is a 9x9 grid divided into nine 3x3 subgrids. Some cells contain digits from 1 to 9 while others are empty (represented by 0). Your task is to fill the empty cells so that each row, each column, and each 3x3 subgrid contains all the digits from 1 to 9 exactly once.

In mathematical terms, if we let \(B_{ij}\) be the digit in row \(i\) and column \(j\), then for all rows \(i\), columns \(j\), and each 3x3 box, we must have: \[ \{B_{i1}, B_{i2}, \ldots, B_{i9}\} = \{1,2,\ldots,9\}, \quad \{B_{1j}, B_{2j}, \ldots, B_{9j}\} = \{1,2,\ldots,9\} \] and similarly for every 3x3 subgrid.

inputFormat

The input consists of 9 lines. Each line contains 9 digits (0-9) without any spaces. The digit 0 represents an empty cell.

outputFormat

Output the solved Sudoku board in the same format as the input – 9 lines with 9 digits (without spaces) per line.

sample

530070000
600195000
098000060
800060003
400803001
700020006
060000280
000419005
000080079

534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179