UVA989 Su Doku

很多报纸上都会登载智力趣题，数独就是其中之一。给你一个 $9\times9$ 的方格，其中一些格子被填入了数字。你的目标是填满这个方格并保证每行、每列和每个 $3\times3$ 的宫都包含数字 $1$ 至 $9$。

有多组数据，数据之间用空行隔开。每个数据包含一个整数 $n (1 \leq n\leq 3)$ 和一个 $n^2\times n^2$ 的方格，其中一些格子被填入了介于 $1$ 至 $n^2$ 的数字（一个没填的格子用 $0$ 代替）。你的目标是填满这个方格并保证每行、每列和每个 $n\times n$ 的宫都包含数字 $1$ 至 $n^2$。

对于每个数据，输出一个解。如果有多个解，输出第一行字典序最小的，如果第一行相同，输出第二行字典序最小的，以此类推。如果无解，输出 `NO SOLUTION`。注意，不允许有行末空格；如果某个测试数据有解则在这组测试数据的最后输出一个空行，无解则不输出空行。 $\texttt{Translated by yhk1001.}$