1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 45 degrees? Don't you mean 90 degrees? $\endgroup$ – Jaap Scherphuis Apr 8 at 14:24
  • $\begingroup$ @JaapScherphuis facepalm woop-dee-doo $\endgroup$ – Mr Pie Apr 8 at 14:25
  • $\begingroup$ "orthogonally adjacent" = "touching themselves on a single corner" ? $\endgroup$ – Jean Marie Apr 8 at 15:03
  • $\begingroup$ @JeanMarie what do you mean? $[1]$ (Cell numbered $1$) is in a corner, and the cells orthogonally adjacent to it are $[7]$ (above) and $[3]$ (right). "Orthogonally adjacent" means "edge adjacent" in other words, as I have been told. $\endgroup$ – Mr Pie Apr 8 at 15:10
  • 1
    $\begingroup$ Yes, orthogonal is very commonly used to mean horizontal and vertical directions, as opposed to diagonal. $\endgroup$ – Jaap Scherphuis Apr 8 at 15:18
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So actually, if I instead rotate the board every $3$ swaps, then since $3 > 2$, this is still solvable? $\endgroup$ – Mr Pie Apr 8 at 15:24
  • $\begingroup$ @user477343 Yes. Actually, it is still solvable if you rotate it every 2 moves. I just edited it to make it a $\ge$ instead of $>$ sign. $\endgroup$ – Jaap Scherphuis Apr 8 at 15:26
  • $\begingroup$ I presume it will be harder to reach a solution if it rotates very $2$ moves as opposed to $N^2$ moves. How long do you think it would take one to solve this puzzle if it rotated every $2$ moves, you reckon? I would like this puzzle to consume within $15$ minutes of time to solve. Do you think that's plenty of time for, say, yourself? $\endgroup$ – Mr Pie Apr 8 at 15:28
  • 2
    $\begingroup$ @user477343 Solving it without worrying about optimality is in my opinion easy. You can simply ignore the rotation of the board (i.e. rotate along with it), solve one tile at a time without disturbing previously solved tiles. At the end do swaps until the board is the correct way up. To aim for optimality, you'd have to try solving it in each of the four orientations, and pick the best one. However, getting near optimal solutions by hand (i.e. without computer) can be tricky, even with a simple puzzle as this. On 3x3, maybe best to do corners first and then at most 6 swaps for the cross. $\endgroup$ – Jaap Scherphuis Apr 8 at 15:41
  • $\begingroup$ Perhaps for optimality, I might even change the game a bit: instead of the board rotating, I could let the outer edge cells (every cell except the centre one) shift clockwise by one cell across the outer edge. So we can have for example: $$\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}\implies\begin{array}{|r|c|} \hline \verb|7|&\verb|9| &\verb|8| \\ \hline \verb|1|&\verb|6| &\verb|4| \\ \hline \verb|3|&\verb|5| &\verb|2| \\ \hline \end{array}$$ ($[6]$ being unchanged, of course). $\endgroup$ – Mr Pie Apr 8 at 15:55
3
$\begingroup$

Yes it is always solvable and the board will never rotate more than once. No tile can be more than $2N-2$ steps from home, so the maximum number of moves is less than $2N^2-2N$. In fact it will be less than this because later tiles cannot be even that far away. See if you can solve it in $N^2$ moves with no rotation. If not, you will have only one rotation so you know where each tile goes relative to the board and move it there. The rotation will get the ones you already placed where they belong.

$\endgroup$
  • $\begingroup$ So $N^2$ is too big a number. Hmm... I don't know which answer is better: yours, or @JaapScherphuis's... oh no. $\endgroup$ – Mr Pie Apr 8 at 15:58
  • $\begingroup$ Hey, would you look at that! Funnily enough, I can reach the following configuration in exactly $N^2$ swaps given that $N=3$. $$\begin{array}{|r|c|} \hline \verb|1|&\verb|2| &\verb|3| \\ \hline \verb|8|&\verb|9| &\verb|4| \\ \hline \verb|7|&\verb|6| &\verb|5| \\ \hline \end{array}$$ Fascinating! Is this a coincidence, or not? Do you know? (If you don't believe me on this, I can reveal to you the swaps :P) $\endgroup$ – Mr Pie Apr 8 at 16:12
  • 1
    $\begingroup$ In the spirit of JaapScherphui's answer, if the rotation is shorter you can solve the board for each of the four orientations. Take the fastest solution in each orientation, then see how many moves you have to wait for each to turn right side up. That gives you the fastest solution. $\endgroup$ – Ross Millikan Apr 8 at 16:14
  • 1
    $\begingroup$ I can solve your board above in $5$, doing $49, 48,68,59,56$ $\endgroup$ – Ross Millikan Apr 8 at 16:16
  • 1
    $\begingroup$ Yes, my maximum included some rounding up. Only corner tiles can be $2N-2$ moves from home and getting some tiles home can move others closer to home. It was a good enough upper bound for what I wanted at the time, which was to show the board would only rotate once if it rotates every $N^2$ moves. $\endgroup$ – Ross Millikan Apr 9 at 2:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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