20096번 - Sudoku 3 점수다국어언어 제한

문제

Fereydun, the legendary Persian hero whose prophecy was to overcome Zahhak, believes that he needs a powerful mind together with a powerful body. He has just learned a new brain teaser, called Sudoku, from a Japanese trader.

Sudoku is played on a board that is a grid of $n^2 \times n^2$ cells. The whole grid is also partitioned into $n^2$ sub-grids, each of size $n \times n$. Each cell can be empty or contain an integer from 1ドル$ to $n^2$ (inclusive). A Sudoku board is valid if it meets the following conditions:

1. All numbers in each row are distinct.
2. All numbers in each column are distinct.
3. All numbers in each sub-grid are distinct.

The following figure shows two valid Sudoku boards with no empty cells:

Fereydun has a valid board with some empty cells and has asked for your help. Your task is to fill as many empty cells as you can while keeping the board valid. It is guaranteed that there is at least one way to fill all the empty cells while keeping the board valid.

This is an output-only problem, so no source code submission is required. There are 10ドル$ test cases. For each test case, you are given an input file containing a table $A$ as the initial state of a Sudoku board, and your task is to submit an output file containing a table $B$ as the final state of that Sudoku board after filling some of its empty cells. All $A[i][j]$ and $B[i][j]$ values (for 1ドル \leq i,j \leq n^2$) are integers between 0ドル$ and $n^2$ (inclusive), where value 0ドル$ indicates an empty cell.

입력

The input is in the following format:

• line 1ドル$: $\;\;n$
• line 1ドル+i$ (for 1ドル \leq i \leq n^2$): $\;\; A[i][1] \;\; A[i][2] \;\ldots \; A[i][n^2]$

출력

The output must be in the following format:

• line $i$ (for 1ドル \leq i \leq n^2$): $\;\; B[i][1] \;\; B[i][2] \;\ldots \; B[i][n^2]$

제한

• 2ドル \leq n \leq 20,ドル
• 0ドル \leq A[i][j] \leq n^2,ドル
• The board $A$ is valid, and all of its empty cells can be filled while keeping it valid.

점수

Your output for a test case will get 0ドル$ score if $B$ is not a valid board, or some non-empty cell of $A$ has a different value in $B$. Otherwise, the score will be 10ドル \times (p-q)/p$ where $p$ and $q$ are the number of empty cells in $A$ and $B,ドル respectively.

It is not necessary that the empty cells of $B$ can be completely filled while keeping the board valid.

힌트

첨부

• 03.in