The Ultimate Sudoku Challenge

Sudoku is a popular logic-based number-placement puzzle. The objective is to fill a 9 \times 9 grid with digits so that each column, each row, and each of the nine \(3 \times 3\) sub-grids (also known as blocks) contain all of the digits from 1 to 9. A valid Sudoku puzzle must have exactly one solution. Any puzzle that has no solution or more than one solution is considered invalid.

A renowned Finnish mathematician once claimed to have designed the hardest Sudoku in the world. While standard Sudoku puzzles are classified into 5 levels of difficulty (with 1 being beginner and 5 being quite challenging), his creation was leveled at 11 – suggesting a degree of difficulty far beyond the norm. He boldly declared that only the brightest minds could ever hope to crack his puzzle, and he maintained that he had yet to encounter a Sudoku that was unsolvable. In this problem, you are tasked with solving such a Sudoku puzzle.

inputFormat

The input consists of 9 lines. Each line contains 9 space-separated integers. The number 0 represents an empty cell that needs to be filled. It is guaranteed that the provided puzzle has a unique solution.

outputFormat

Output the solved Sudoku grid in the same format as the input: 9 lines with 9 space-separated integers on each line.

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