I have created the following puzzle for the Puzzling Stack Exchange and I need to know if the aim of this puzzle is possible to achieve, hence why I have firstly posted it here. I hope it is not off-topic.
This puzzle is called Swap. Let's find out why!
Suppose you are given a random $\rm N\times N$ matrix with all the integers from $1$ to $\rm N^2$ each belonging in every grid square (a.k.a. cells). The integers are the elements of the matrix. The elements are ordered randomly. Let $\rm N = 3$ for the following case:
$$\begin{array}{|r|c|} \hline
\verb|9|&\verb|8| &\verb|4| \\ \hline
\verb|7|&\verb|6| &\verb|2| \\ \hline
\verb|1|&\verb|3| &\verb|5| \\ \hline
\end{array}$$
The aim of the puzzle is to reach the following configuration from the matrix above via swaps:
$$\begin{array}{|r|c|} \hline
\verb|1|&\verb|2| &\verb|3| \\ \hline
\verb|4|&\verb|5| &\verb|6| \\ \hline
\verb|7|&\verb|8| &\verb|9| \\ \hline
\end{array}$$
Swaps are movements defined by switching two orthogonally adjacent cells and exchanging their positions in the matrix (intuitively).
But, like always, there's a catch!
After every $\rm N^2$ swaps (in this case, after every $9$ swaps), the entire matrix rotates $90^\circ$ clockwise. Hah! That might be annoying.
Aim: Reach the solution in the least amount of swaps from the configuration in the sandbox.
Is the aim of this puzzle achievable, or not? I am very confident it is, but I need a proof (maybe somewhat implicit so I can figure out myself; i.e. hints are appreciated).
Apologies if this is off-topic, but a similar question of mine on this site seemed to kick off well. I hope you understand the puzzle, but more importantly, I hope not to take too much time off your hands if you are willing to answer this question and/or attempt the puzzle yourself. Again, let's find out!
Thank you in advance.
P.S. This puzzle is not related, albeit the title is very similar; but this concerns only PSE users, I suppose.
Best Answer
Yes, it is always solvable.
First suppose the board never rotates. In that case you can just solve it fairly straightforwardly (regardless of the parity of the permutation). Suppose it takes $k$ swaps to solve.
By repeatedly swapping two tiles, you can also solve it in $k+2$, $k+4$, $k+6$, ... swaps. You return to the solved state every two swaps.
Suppose now that the board rotates every $N^2$ swaps. Simply rotate your solving method with it. The board will become solved, but possibly in the wrong orientation. By doing those additional repeated swaps, you will be able to get it solved and to the correct orientation. This is always possible because $N^2 \ge 2$ - the interval between board rotations is greater than (or equal to) the length of a repeated swap.
This is enough to show that it is always solvable. It may well be solvable in a different orientation using many fewer moves, but I'll leave that for the future puzzle question.