Sudoku

Sudoku is a number puzzle played on a 9×9 grid. Every row, every column, and each of the nine 3×3 subgrids must contain each digit from 1 through 9 exactly once.

You are given a partially filled Sudoku board. Fill every empty cell and print a completed board.

The board is given in 9 lines. Each line contains 9 digits, and an empty cell is written as 0.

Print the completed Sudoku board in 9 lines. If there is more than one solution, print the one whose 81-character string, formed by reading the rows from top to bottom, is lexicographically smallest.

• Every input is a Sudoku puzzle that can be solved within the time limit.
• Time limit: 2 seconds
• Memory limit: 256 MB