P1784 Sudoku

Sudoku is to infer the numbers for all remaining empty cells on a $9 \times 9$ board from the given numbers, such that every row, every column, and each $3 \times 3$ box contains the digits $1 - 9$ without repetition. Every valid Sudoku puzzle has exactly one solution; solving methods are based on this. Any puzzle with no solution or multiple solutions is invalid. A mathematician from Finland claimed to have designed the world’s hardest "Sudoku game" and published it in a newspaper for everyone to challenge. He said he believes only people with "the very top intelligence" might be able to crack this "Sudoku mystery." It is said that the difficulty of Sudoku is usually graded from one to five, where one is beginner level and five is relatively difficult. However, this mathematician said the difficulty level of his design is eleven, which can be called the highest level among all Sudoku games. He also said that he has not yet encountered a Sudoku he could not solve, so he believes the "most challenging" Sudoku has not yet appeared.

An unsolved Sudoku: a $9 \times 9$ grid where $0$ denotes an empty cell and $1$–$9$ are given digits. The numbers are separated by single spaces, one row per line.

The completed Sudoku, in the same format.

On 2022-04-17, @farteryhr contributed three sets of hack testdata. Two were added. The third is too strong (source: ), and is provided below for self-testing. ``` 9 0 0 8 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 1 0 0 0 3 0 1 0 0 0 0 0 6 0 0 0 0 4 0 0 0 7 0 7 0 8 6 0 0 0 0 0 0 0 0 0 3 0 1 0 0 4 0 0 0 0 0 2 0 0 ``` Output ``` 9 7 2 8 5 3 6 1 4 1 4 6 2 7 9 5 3 8 5 8 3 1 4 6 7 2 9 6 2 4 7 1 8 9 5 3 8 1 7 3 9 5 4 6 2 3 5 9 4 6 2 8 7 1 7 9 8 6 2 1 3 4 5 2 6 5 9 3 4 1 8 7 4 3 1 5 8 7 2 9 6 ``` Translated by ChatGPT 5