10
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ To clarify, you mean the minimum number of moves necessary to solve the configuration with the longest solution? $\endgroup$ – DiscOH Oct 29 '14 at 23:02
  • $\begingroup$ @DiscOH yes. That's what I mean. $\endgroup$ – warspyking Oct 30 '14 at 0:14
  • 2
    $\begingroup$ Btw, I'll accept brute force methods. $\endgroup$ – warspyking Oct 30 '14 at 10:30
  • $\begingroup$ I feel like we're close... Just not quite there. Are we missing any obvious detail? $\endgroup$ – warspyking Nov 2 '14 at 1:33
3
+50
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ It seems pretty solid, but I'm not entirely sure if it's correct. I'll accept and if no one objects saying this is wrong within a day or so, I'll award the bounty. $\endgroup$ – warspyking Nov 24 '14 at 0:03
  • 1
    $\begingroup$ An exhaustive search of 3x3 shows 16 moves as the worst case scenario. $\endgroup$ – Michael Nov 24 '14 at 20:53
  • $\begingroup$ @Michael I can't seem to find a way to the reversed square in under 18. Can you post your example or the code you used ? $\endgroup$ – KSab Nov 25 '14 at 5:06
  • 1
    $\begingroup$ @KSab Sure. Forgive the obnoxiously long comment: (8, 7, 6) (5, 4, 3) (2, 1, 0) → (5, 7, 6) (8, 4, 3) (2, 1, 0) → (5, 4, 6) (8, 7, 3) (2, 1, 0) → (4, 5, 6) (8, 7, 3) (2, 1, 0) → (4, 5, 6) (2, 7, 3) (8, 1, 0) → (4, 5, 6) (2, 1, 3) (8, 7, 0) → (4, 5, 6) (2, 1, 3) (7, 8, 0) → (4, 5, 6) (2, 1, 3) (7, 0, 8) → (4, 5, 6) (2, 1, 3) (0, 7, 8) → (4, 6, 5) (2, 1, 3) (0, 7, 8) → (4, 1, 5) (2, 6, 3) (0, 7, 8) → (4, 1, 5) (6, 2, 3) (0, 7, 8) → (4, 1, 5) (0, 2, 3) (6, 7, 8) → (0, 1, 5) (4, 2, 3) (6, 7, 8) → (0, 1, 5) (4, 3, 2) (6, 7, 8) → (0, 1, 2) (4, 3, 5) (6, 7, 8) → (0, 1, 2) (3, 4, 5) (6, 7, 8) $\endgroup$ – Michael Nov 25 '14 at 17:08
  • $\begingroup$ @KSab Easier to read: pastebin.com/raw.php?i=WHhHyGw6 $\endgroup$ – Michael Nov 25 '14 at 17:14
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Symmetry is your friend. Steps you need to move from the far left to the far right, can be combined in the steps of moving the ones from the far right to the far left. So your worst case on the top two corners being on the opposite corner takes 11 steps maximum instead of 12, on the second row it's 9 instead of 10, and on the third row it's 7 instead of 8. That cuts down your upper boundary to 61. Similary, there will be cases you can save a move on the center two, by putting them in opposing places and then switching between those.. $\endgroup$ – Tim Couwelier Oct 30 '14 at 16:26
  • 1
    $\begingroup$ Re: "at each step, there are 18 possible moves": Surely there are 24? $\endgroup$ – ruakh Nov 1 '14 at 7:15
  • $\begingroup$ There probably isn't a nice trick, because if there were then there's no obvious reason why it shouldn't apply to all permutation groups, and in particular why it was necessary to apply a lot of brute force to find the diameter of the Rubik's cube group. $\endgroup$ – Peter Taylor Nov 1 '14 at 14:17
  • $\begingroup$ The limit for the final row is wrong. 3+2+2+3, should be 3+2+1. 3+2+2+3 assumes that the tiles to place is in a spot taken by an earlier tile. $\endgroup$ – Taemyr Nov 6 '14 at 15:51
  • $\begingroup$ @Taemyr - the limit is wrong in the sense that the final row can (and will) be sorted faster than my suggestion, but it is correct in that it does provide an absolute upper limit for the tile sorting problem (as I stated). $\endgroup$ – Penguino Nov 9 '14 at 20:02
4
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ Seems like we're getting closer... $\endgroup$ – warspyking Oct 30 '14 at 17:18
  • $\begingroup$ The funny thing is: if you make the top row, then the left column, then the 2nd row, then the 2nd column, etc. you still get 48 moves as upper bound. $\endgroup$ – Florian F Oct 31 '14 at 22:07
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ So just to be clear, this does not answer the 4x4 question? $\endgroup$ – warspyking Nov 1 '14 at 1:03
  • $\begingroup$ I kinda need 4x4 to accept a solution, so um, is there a pattern in the move numbers? $\endgroup$ – warspyking Nov 1 '14 at 1:05
  • $\begingroup$ It is not a definitive answer. Just contributing to a solution. I was hoping to find some regularity in the numbers. What I found is that the reverse board is probably the worst case and that the formula for the upper bound used so far isn't optimal for smaller cases. 3x3 gives an upper bound of 18 but 16 is possible. $\endgroup$ – Florian F Nov 1 '14 at 1:13
  • $\begingroup$ Seems like this is a hard question! $\endgroup$ – warspyking Nov 1 '14 at 1:26
  • 1
    $\begingroup$ Your 3x4 case of 24 moves gives an upper bound of 18+24=42. $\endgroup$ – Taemyr Nov 6 '14 at 16:14
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ This sounds more like a guess. $\endgroup$ – warspyking Nov 23 '14 at 17:02
  • $\begingroup$ Are you allowed to rotate the entire square? $\endgroup$ – tjbtech Nov 23 '14 at 19:09
  • $\begingroup$ Hello! Would it be possible for you to edit in an explanation? Otherwise, the answer may be removed. Thank you! $\endgroup$ – Aza Nov 23 '14 at 21:43

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.