Sudoku (Hard)

Sudoku comes from the "Latin square" puzzle invented by an 18th-century Swiss mathematician, and it is very popular today. The game is played on a square board made of 81 small cells, 9 across and 9 down, as shown below. Before the game starts, some cells already contain one of the digits from 1 to 9.

The remaining empty cells are filled as follows.

1. Each row and each column must contain the digits 1 to 9 exactly once.
2. Each 3x3 square separated by the thick lines must also contain the digits 1 to 9 exactly once.

In the example above, the first row already contains 2 to 9, so the empty cell in the first row must contain 1.

Also, the 3x3 square in the upper middle already contains every digit except 3, so the empty cell in its middle must contain 3.

Filling the empty cells one after another this way gives the final result below.

Given the digits written on the Sudoku board before the game starts, write a program that prints the final board with every empty cell filled.

Nine lines are given. Each line contains the 9 digits written in one row of the Sudoku board before the game starts, separated by single spaces. An empty cell is given as 0. The input never describes a board that cannot be filled according to the rules.

Print the final Sudoku board with every empty cell filled, over nine lines, with the 9 digits in each line separated by single spaces.

If there is more than one way to fill the board, print any one of them.