P8549 Xiao Wa’s Nuclear Fuel Refill

When Xiao Wa was doing Web design, the story included a cool nuclear refilling scene. But sadly, due to technical limits, the corresponding game turned out to be Sudoku... At the beginning, you are given an already completely correctly filled $n$-order Sudoku. It has $n \times n$ **blocks**, and each block contains $n \times n$ elements. The detailed representation and rules of Sudoku in this problem are given in **“Additional Notes”** below. However, Xiao Wa will rotate **some blocks left or right by $90$ degrees / $180$ degrees**. For example, if a block initially is ```cpp 087 654 321 ``` then after rotating it left by $90$ degrees, it becomes: ```cpp 741 852 063 ``` When you restore the Sudoku, you are also **only allowed to rotate some blocks left by $90$ degrees**. Each rotation counts as one step. Now Xiao Wa wants to test you: if you restore the operated Sudoku back into a valid Sudoku, what is the minimum number of steps needed? If the Sudoku configuration given by Xiao Wa at the start cannot be obtained by any number of left rotations at any positions, output $-1$. ~~Why? Because Xiao Wa thinks it is “completely correct”, but in fact it may not be.~~

Line $1$ contains a positive integer $n$. Lines $2$ to $n^2+1$ each contain $n^2$ hexadecimal integers, describing a given Sudoku configuration, which is the game state after Xiao Wa’s operations.

Line $1$ outputs an integer, the minimum number of steps $s$. Lines $2$ to $s+1$ each output two integers $x_i, y_i$, meaning you rotate the block at row index $x_i$ and column index $y_i$ left by $90$ degrees. The testdata guarantees that when a solution exists, the optimal solution is unique. When outputting, please follow these rules: Let $i

For $40\%$ of the testdata, $2 \le n \le 3$. For $100\%$ of the testdata, $2 \le n \le 4$. ## Hint The validity conditions for an $n$-order Sudoku: in every row, every column, and every thick-lined block $(n \times n)$, the numbers contain $0 \sim n^2-1$ with no repetition. Note that in this problem’s representation for $4$-order Sudoku, numbers $>9$ are written in hexadecimal. More precisely, $\mathrm A = 10$, $\mathrm B = 11$, $\mathrm C = 12$, $\mathrm D = 13$, $\mathrm E = 14$, $\mathrm F = 15$. Translated by ChatGPT 5