What's the Maximum Moves Needed for this kind of Puzzle?

Question

Imagine a 4x4 square with a picture you need to make with tiles in it, now imagine you can swap any 2 pieces next to eachother (horizontal, and vertical, not diagonal.) What's the maximum amount of moves needed for this type of game? What's the setup required for this game? Label it 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 for the tiles.

By maximum number of moves I mean the minimum number of moves necessary to solve the configuration with the longest solution?

Answer 1

Edit: As others have pointed out this is incorrect, I realize that my solutions below only apply as upper bounds. It seems that the actual solution is somewhat more complicated.

I attempted to formally prove these results:

---

First consider a single dimension, a simple permutation of tiles such as ABCD. In this case the only valid operation is of course flipping two adjacent tiles.

Let $M(n)$ denote a function representing the maximum number of moves required to sort a set of tiles of size $n$.

It is clear that $M(1)=0$. When considering $M(n)$ for the list of tiles $T_1,T_2...T_n$ we can apply the following method: flip the tile which belongs at the leftmost position with its neighbor to the left until it reaches said position. After this is completed, we simply have to sort the rest of the n-1 members, meaning $M(n)=F+M(n-1)$ where F is the number of times a flip was necessary. Since the largest possible value of $F$ is obviously $n-1$ (if the tile began at the rightmost spot) we can say that $M(n) \leq n-1+M(n-1)$.

With a little math this is $M(n) \leq \frac{n(n-1)}{2}$ (we are essentially writing a formula for 1+2+...+n-1)

We can also see that when the tiles begin in the reversed order from how they should be, each tile, $T_i$, must move to the right $n-i$ times (one for every tile to the right of it which has to switch with it to get to the left of it) and then left $i-1$ times to get to its correct spot. The total moves each tile performs is $n-1$, meaning the total number of moves all the tiles have to undergo is $n(n-1)$ and since each switch moves two tiles this will take at least $\frac{n(n-1)}{2}$ switches.

Since we have shown that this example takes at least $\frac{n(n-1)}{2}$ switches, we can confirm that the maximum number of switches required for any set of tiles of size $n$ must be at least that much: $M(n)\geq \frac{n(n-1)}{2}$ and with the result we determined before, we can conclude that $M(n)= \frac{n(n-1)}{2}$

---

Let us now consider a two dimensional, $n$ x $n$ grid. Using our last result we can see that it takes $\frac{n(n-1)}{2}$ switches to sort any individual row, meaning it would take $\frac{n^2(n-1)}{2}$ switches to sort every row. This is effectively moving each tile to the correct column. Similarly, if we have already sorted rows, we would need to switch rows at most $\frac{n(n-1)}{2}$ times, or $\frac{n^2(n-1)}{2}$ total tile switches. This is effectively moving each tile to the correct row.

As frodoskywalker also briefly described in his answer, it does not affect the answer if tiles which do not belong to the same row begin in the same row before they are moved to their respective columns. This is because the vertical moves to correct it can double as also moving them toward correct row. Specifically if two tiles do not belong to the same row but are currently in the same row, one should be flipped vertically away towards its correct row, taking an extra move to sort the columns, but also lessening the number of moves required to sort the rows by 1. Since the gains and losses are equivalent in this method we can conclude that the total number of switches required is $\frac{n^2(n-1)}{2} + \frac{n^2(n-1)}{2}$ or simply $n^2(n-1)$.

I am not sure about this part, but it seems to be intuitively true that this can be extended to higher dimensions; for each additional dimension, every tile must undergo at most $\frac{n(n-1)}{2}$ switches to reach its correct position in that dimension. Multiplying this by the number of dimensions and the number of tiles leads to the formula $\frac{n(n-1)}{2}n^{d-1}d$ or $\frac{d}{2}n^d(n-1)$.

---

Whew, I hope everything I said made sense, I spent a lot more time writing this than I first intended but it was pretty fun, and I'm glad I managed to get the results that I did (I think anyway). If anyone doesn't understand something or thinks I might have goofed somewhere please comment.

Answer 2

Before getting the correct answer (someone else may have a nice trick to come up with the exact number immediately, but it isn't obvious to me) it may be useful to first generate some absolute limits.

Firstly, I think it is obvious that any starting point can reach any finishing point, so the problem is always soluble in some N moves.

A naive solution would be to correct the top row of tiles first (left to right) then the second row etc, until all was solved. It takes no more than 6 swaps to get 1 into position, 5 swaps to get each of 2 and 3 into position and 6 swaps for 4 (the top right tile). The next row will take no more than 5 + 4 + 4 + 3, the third row no more than 4 + 3 + 3 + 4, and the final row 3 + 2 + 2 + 3, so an absolute upper limit to N is 64 moves. This should be a grossly pessimistic.

As a similarly naive guesstimate for the lower limit, there are 16! starting positions and, at each step, there are 18 possible moves. It is impossible to reach more then 18^k positions in k moves (actually will be far less as many moves are independent) so there will be positions that are at least ln(16!)/ln(18) ~= 10.6 moves apart. Thus N has an absolute lower limit (grossly optimistic) of 11.

Conclusion so far: 64 >= N >=11

Answer 3

Following Penguino, I'll put tighter limits on the solution.

As a lower limit to N, let's define the 'disorder' of a piece as the sum of its horizontal and vertical distance from where it should be. The disorder of the square is then the sum of the disorder of all 16 pieces. A given move can change the disorder by at most 2, and disorder must be 0 for the solved puzzle.

If we translate each piece through the centre (in the hope of maximising disorder) we go from:

ABCD EFGH IJKL MNOP

to

PONM LKJI HGFE DCBA

Giving a disorder for each piece of

6446 4224 4224 6446

Totalling 64. Since we saw that a move changes disorder by no more than 2, at least 32 moves are needed to solve this setup.

As for upper limits, if the top row starts at the bottom in a maximally disordered state, you can get it to the top in (4*3 moves) 12 moves and give it the correct order in (3+2+1) 6 moves. You cannot make this worse by, for example, placing abcd in the bottom right quadrant because every left-right move used to fit them all into the top row will reduce the number of left-right moves needed to make them ordered.

So 18 moves gives us the top row in order. The second row is the same but with one less vertical space for the 4 pieces to travel, giving 14 moves maximum. Same argument again for row three gives us 10 more, and row 4 is automatically in place, needing a maximum of 6 moves to have the correct order.

This gives an upper limit of 18+14+10+6=48 moves for any arrangement.

$48\geq N\geq 32$

Answer 4

Experimenting with smaller boards

I did a computer search.

But 4x4 is too big for a brute-force search. The case 3x4 took a night to complete.

But here are the maximum nb of moves for smaller sizes:

     1  2  3  4  5  6  7  8  9 10
  +-------------------------------
1 |  0  1  3  6 10 15 21 28 36 45
2 |  1  4  9 14 21 30
3 |  3  9 16 24
4 |  6 14 24 ??

Note that in all these cases, the inverted board was among the worst cases. Sometime, as for 3x4, it is the only one.

Sometimes other starting positions are equally bad. For example, the following board for 2x5 is also a worst case with 21 moves:

4 8 7 6 0  ->  0 1 2 3 4
9 3 2 1 5      5 6 7 8 9

Upper bound for the 4x4 case

This does not answer the 4x4 case, but it gives a better upper bound. As frododkywalker explained, the 1st row can be done in 18 moves. Taemyr noted that a first row at 18 moves + the 3x4 board at 24 moves gives an upper bound of $N \le 42$.

If the reversed board is the worst case then $N$ is even. This, with the trend in the table above, seems to indicate a value of $N=36$.

Lower bound for the 4x4 case

I could brute-force a simpler problem which is to reverse the columns of the 4x4 board and minimizing horizontal flips. I counted how many times you need to exchange any 2 numbers in 2 adjacent columns to arrive at a board where the outer left and right columns are exchanged and the inner left and right columns are exchanged. I arrived at 18 moves.

It is easy to solve that by hand, but it is not obvious it cannot be done in 17 moves.

If you use frodoskywalker's measure of disorder but only horizontally, you get a disorder of 32. And every horizontal move reduces it by no more than 2, this means a minimum of 16 moves. But that minimum cannot be realized. Because when you move out the first number from the left column, you need to put in a number from the right column to reduce the disorder. That means you need a number from the right column nearby. So you need to remove that number from the right column. But to do that while reducing the disorder, similarily, you need a number from the left column nearby. So the first move that affects a number from the outer columns cannot reduce the disorder, and therefore you need at least 17 moves.

The fact that you need 18 is a result of my computer search. Maybe some kind of parity is involved.

The implication for the original problem is that a solution that reverses the 4x4 board solves the simpler problem by columns and by rows. It reverses the columns left-to-right, which requires at least 18 horizontal moves. Likewise, it reversese the rows upside-down which requires 18 vertical moves.

That gives: $N \geq 18+18 = 36$.

Estimation for the 4x4 case

Note that sizes 3x3 and 3x4 are exactly 4 moves above frodoskywalker's minimum of 12 resp. 20 moves. It is my impression that this is a general formula. That would give $N = 32+4 = 36$.

Answer 5

Is the answer 48? I don't feel like writing out a proof, given that I'm not even certain it's correct.

[Edit: Adding brief explanation...]

The most pessimum initial configuration would be the inverse of the final design, so the equivalent matrix would be...

$\begin{bmatrix}16 & 15 & 14 & 13\\12 & 11 & 10 & 9\\ 8 & 7 & 6 & 5\\4 & 3 & 2 & 1\end{bmatrix}$

Starting with the first piece, it would take six moves at a minimum to place it properly. It would take five moves for the second...then, four for the third, and three for the fourth. (6 + 5 + 4 + 3...) We're up to eighteen moves at this point - first row down. The matrix becomes...

$\begin{bmatrix}1 & 2 & 3 & 4\\16 & 15 & 14 & 13\\12 & 11 & 10 & 9\\ 8 & 7 & 6 & 5\end{bmatrix}$

In fixing the second row, each cell would take one less move than its corresponding one (cell above) in the first row. So #5 takes five moves; #6 takes four; #7 takes three; #8 takes two. (5 + 4 + 3 + 2...) That's another 14 moves for a subtotal of 32.

The third row then takes (4 + 3 + 2 + 1) = 10 moves, and the last row takes (3 + 2 + 1) = 6.

The total number of moves for the most efficient solution to the most pessimum starting setup is, then, 48.

But if you can rotate the puzzle, everything changes; the matrix shown above would not take any moves, aside from a 180 degree spin. My guess for least moves in that case is 33.

Incidentally, this question was posted weeks ago with no confirmed answer. Why not just give the solution at this point?? I only posted to ask whether 48 was actually the answer you wanted since it was already the answer given in an earlier response, and it seems to be the right one, unless there's a hack to be used.