Limit to Minimizing Doubleswaps

[MichaelZ]

Has anyone else noticed that no matter how you try to solve a puzzle, and no matter what order you rearrange the tiles, if you make no mistakes, you're always left with the same number of doubleswaps for that particular puzzle?

I stumbled upon this realization today while playing with rearranging puzzle tiles in an image editor. Starting with the same base unsolved puzzle image:


and rearranging its tiles results in 5 doubleswaps. I solved this puzzle from scratch eight times, keeping track of my moves in a spreadsheet, and each of the eight times I solved it, it took a total of 43 moves, 5 of which were doubleswaps.

Each time I made a concerted effort to concentrate on a different area of the puzzle first, but the number of moves and doubleswaps remained the same.

So I grabbed a second image and tried it with that one:


I solved this one six times. The first time I was pleased to find that I was forced into only 4 doubleswaps, and I thought my experience with the Cristo Redentor puzzle had just been a fluke, but the next five times I solved the Eiffel Tower puzzle I could not avoid getting 4 doubleswaps.

I still couldn't believe my results, so I tried once more with a third image:

This image has one doubleswap that is apparent up front (tile at 4th column, 2nd row swaps with tile at 2nd row, 8th column), but still every time I solve it, I am forced into exactly 3 doubleswaps -- no less.

It's obvious that every puzzle must have at least one double-swap, i.e. the last move of the puzzle, but I never realized it wasn't possible to minimize the number of double-swaps lower than a given number for a certain arrangement of the tiles.

[robin74]

if you make no mistakes, you're always left with the same number of doubleswaps for that particular puzzle?

Isn't it just a mathematical (though maybe not so obvious) fact?
Unless you rearrange the puzzle ("make mistakes"), the number of double swaps will stay constant. Optimally you wan't to do the double swaps as early as possible, possibly eliminating some before you actually start doing the puzzle.

[churd]

If it is true that the opening formation of a puzzle has a set number of double-swaps, you should be able to highlight them in the images you present. The only time double-swaps are absolutely unavoidable is if they start as a double-swap naturally, or if three pieces form a circular position where A->B, B->C, and C->A. Either way, if you want to do legitimate analysis, you should be able to highlight these squares in your paint/photoshop program and show which squares will create double-swaps.

If you really want to make your case undeniable, label each piece with its final destination on a grid from A1-H6 or (1,1) to (6, 8) if you like the XY axes.

The more likely scenario is that you are moving pieces in a sequence which results in double swaps; a sequence which could have been avoided had you moved your pieces differently. Getting the same number is probably a reflection of user bias, based on your experiences and priority moving pieces. My personal experiences with puzzle have been vastly different.

I can tell you just from viewing the images that none of the pieces that make up Christ The Redeemer will result in innate double-swaps. I didn't do the second-level analysis to see if they will result in A->B->C forced double-swaps. Feel free to prove me wrong. But as of right now, I just don't buy it.

[phenomist]

It's obvious that the number of double-swaps stays constant if you play perfectly (i.e. never swapping two pieces where neither of them reach their destination)

Consider any piece. Consider its target square. Consider that piece. Consider that piece's target square, and recursively do this until you reach your original square. In other words, you've partitioned the pieces on the board into cycles.

Now, to show that you get exactly one doubleswap per cycle:

Let's define function f(A) to be where the piece should map to, in otherwords:

f(A)=B, f(B)=C, etc. to f(Z)=A. (or however long the cycle is)

If there is a 2-cycle then that is a forced doubleswap.

Otherwise, you actually can't doubleswap in a >2-cycle (until you reduce it into a 2-cycle)! This is because there do not exist pieces I and J where f(I)=J and f(J)=I.

So, if you play perfectly, you must singleswap. What does that mean? You must swap piece X with f(X). By doing so, piece X becomes completed, and Y=f(X)'s location becomes that of X's location, in other words f(W)! This creates a cycle of length n-1. Since the number of cycles remains invariant, and in each cycle, you can only get one doubleswap per cycle, and hence no matter what you do, the number of doubleswaps is the same for a fixed puzzle.

If you want to doubleswap early, analyze the starting puzzle and measure cycle lengths. Then solve each cycle from shortest to longest.

[churd]

Hmmm. The function idea does make sense. I'd still like to see it, though.

[Aeruthas]

wow phenomist, love your explanation. Finally someone is talking sense
I was wondering what is the average number of cycles/double swaps for a completely randomized 8x6 puzzle?

[robin74]

wow phenomist, love your explanation. Finally someone is talking sense
I was wondering what is the average number of cycles/double swaps for a completely randomized 8x6 puzzle?

But it's not completely randomised, is it? No tile is ever at the right position in the beginning.

[Dave Hazard]

This is all way over my head... but chances are, by the time you figure this out for a given puzzle someone else will log in and screw with it.

I thought perhaps that the initial placement of the tiles was not that random at all - that a bot could figure it out and auto-play the puzzle, as I have seen certain players solve a difficult puzzle as fast as you can click the pieces.