Sudoku

Sudoku is a puzzle played on a 9x9 board. Some cells already contain a digit from 1 through 9, and the remaining empty cells must be filled according to the rules.

Fill the empty cells using these rules.

1. Each row must contain every digit from 1 through 9 exactly once.
2. Each column must contain every digit from 1 through 9 exactly once.
3. Each 3x3 square marked by the thick lines must also contain every digit from 1 through 9 exactly once.

In the first picture, the first row already contains every digit from 2 through 9, so the empty cell in that row must be 1.

In the upper middle 3x3 square, every digit except 3 is already present, so the empty middle cell must be 3.

Filling the remaining cells in this way gives the completed board below.

Given the Sudoku board at the start of the game, write a program that completes the board and prints the final state.

Nine lines are given. Each line contains 9 integers separated by spaces, describing one row of the Sudoku board. Filled cells contain a digit from 1 through 9, and empty cells contain 0. Inputs that cannot be completed according to the rules are not given.

Print the completed Sudoku board in nine lines. Each line must contain 9 digits separated by spaces.

If there is more than one valid completion, print any one of them.

Every input board can be completed according to the Sudoku rules.

Reference execution times are as follows.

• C++14: 80ms
• Java: 292ms
• PyPy3: 1172ms