# Swap — A Puzzle I Created

This puzzle is called Swap. Let's find out why!

Suppose you are given a random $$\rm N\times N$$ matrix (grid) 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$$ swaps (in this case, after every $$3$$ swaps), the entire matrix rotates $$90^\circ$$ clockwise. Hah! That might be annoying.

Reach the solution in the least amount of swaps, from the configuration presented in the sandbox above.

Good luck! :D

P.S. This puzzle is solvable, and this puzzle is not related, albeit the title is very similar.

P.P.S. I will award a $$+50$$ rep bounty to whoever attempts — and solves! — a $$5\times 5$$ case (the elements ranging from $$1$$ to $$25$$ and quite randomly placed, and the matrix rotating $$90^\circ$$ clockwise every $$5$$ swaps).

# Edit

Is there anything I might add that could improve the difficulty of this puzzle? Don't go too deep into this particular question, though — I prefer that we don't veer from the actual question itself; i.e. the puzzle.

• Sorry, my bad, it does make a difference. I'll delete my comment. – hexomino Apr 8 '19 at 16:52
• @hexomino each time the board rotates, the orientation is different from the solution provided (or must I say, the aim), hence why I added that feature. So, yeah, it might make a difference... but to someone as clever as yourself, perhaps not ;) – Mr Pie Apr 8 '19 at 16:54
• If you're asking to make the question more difficult, then I thought about this: If we consider it to be N squares centered around the middle point, then instead of rotating the entire grid (after every N moves), you could rotate alternate squares in opposite direction? For example, For a 4X4, You'd have two squares - one as the boundary, and one as the central 4 pieces. So rotating them in opposite directions after every N moves seems to make it a bit difficult. – Eagle Apr 8 '19 at 17:10
• This was very close to the original rule that I proposed, though mine was only about rotating the boundary squares clockwise by one unit — but your idea is more general, and difficult! In fact, with that rule included, I cannot tell if the puzzle would be solvable anymore! Nice suggestion, nevertheless! I will definitely keep that in mind :P – Mr Pie Apr 8 '19 at 17:25
• @user477343 I don't think solvability should be an issue because you can always idly swap the same pair until the desired orientation comes around. – noedne Apr 8 '19 at 17:43

I can do it in 6 moves:
1

9 8 4
6 7 2
1 3 5

2

9 8 4
6 7 2
3 1 5

3

3 6 9
1 2 8
5 7 4

4

3 6 9
1 2 8
5 4 7

5

3 6 9
5 2 8
1 4 7

6

1 2 3
4 5 6
7 8 9

• Good job, you did it! First time I tried, it took me $14$ moves and I just tried getting lower and lower. I couldn't beat your answer, so I just presumed this was the lowest. I conjecture that the lowest amount of moves is $\rm N^2-N$ for an $\rm N\times N$ puzzle (although I need a proof), but given just that, I will give you the tick in $24$ hours from now (and upvote in $22$ minutes after my daily voting limit). Nice work! :D – Mr Pie Apr 8 '19 at 23:37
• @user477343 You can force at least a fraction of $N^3$ moves by placing corner numbers in the center, numbers next to the corner next to the center, etc. – noedne Apr 9 '19 at 2:03

Another solution (still in six moves, but the second move requires swapping the leftmost and rightmost elements from the second row, so not adjacent)

$$\overset{\LARGE \verb|1|}{\begin{array}{|r|c|} \hline \verb|9|&\verb|8| &\verb|4| \\ \hline \verb|7|&\verb|6| &\verb|2| \\ \hline \verb|5|&\verb|3| &\verb|1| \\ \hline \end{array}} \rightarrow\overset{\LARGE \verb|2|}{\begin{array}{|r|c|} \hline \verb|9|&\verb|8| &\verb|4| \\ \hline \verb|2|&\verb|6| &\verb|7| \\ \hline \verb|5|&\verb|3| &\verb|1| \\ \hline \end{array}}\rightarrow\overset{\LARGE \verb|3|}{\begin{array}{|r|c|} \hline \verb|5|&\verb|2| &\verb|9| \\ \hline \verb|3|&\verb|6| &\verb|8| \\ \hline \verb|1|&\verb|4| &\verb|7| \\ \hline \end{array}}\rightarrow\overset{\LARGE \verb|4|}{\begin{array}{|r|c|} \hline \verb|2|&\verb|5| &\verb|9| \\ \hline \verb|3|&\verb|6| &\verb|8| \\ \hline \verb|1|&\verb|4| &\verb|7| \\ \hline \end{array}}\rightarrow\overset{\LARGE \verb|5|}{\begin{array}{|r|c|} \hline \verb|3|&\verb|5| &\verb|9| \\ \hline \verb|2|&\verb|6| &\verb|8| \\ \hline \verb|1|&\verb|4| &\verb|7| \\ \hline \end{array}}\rightarrow\overset{\LARGE \verb|6|}{\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}}$$

• (+1): very interesting! @Sconibulus's answer is more compliant with the rules, but this answer ain't too shabby itself :P – Mr Pie Apr 9 '19 at 11:19