6
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • $\begingroup$ Sorry, my bad, it does make a difference. I'll delete my comment. $\endgroup$
    – hexomino
    Apr 8, 2019 at 16:52
  • $\begingroup$ @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 ;) $\endgroup$
    – Mr Pie
    Apr 8, 2019 at 16:54
  • $\begingroup$ 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. $\endgroup$
    – Eagle
    Apr 8, 2019 at 17:10
  • $\begingroup$ 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 $\endgroup$
    – Mr Pie
    Apr 8, 2019 at 17:25
  • $\begingroup$ @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. $\endgroup$
    – noedne
    Apr 8, 2019 at 17:43

2 Answers 2

Reset to default
9
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – Mr Pie
    Apr 8, 2019 at 23:37
  • 1
    $\begingroup$ @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. $\endgroup$
    – noedne
    Apr 9, 2019 at 2:03
3
$\begingroup$

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}}$$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.