Challenge VI: 15 Puzzle solved by Boorglar and mfb

[micromass]

NEW CHALLENGE:

This challenge was a suggestion by jgens. I am very thankful that he provided me with this neat problem.

A 15-puzzle has the following form:

The puzzle above is solved. The object of the game is to take an unsolved puzzle, such as

and to make a combination of moves to bring the puzzle in the solved position. An allowable move here is to slide 11 to the right or to slide 12 down. After you slide 11 to the right, you have the options to slide 11 to the left, to slide 3 to the right, or to slide 15 down. Etc.

The challenge question now is to take the following unsolved puzzle:

Prove that you cannot solve this puzzle. That is, there is no finite combinations of moves that can bring this position into the solved position.

Furthermore, try to devise a criterion to decide which puzzles are solvable and which are not.

 

[lugita15]

Here's a hint: odd and even permutations.

 

[Boorglar]

Well I think this one is a simple solution (finally a problem I can solve) :P

my solution for the first part:

Spoiler

Every move is a transposition of the empty cell with a neighboring numbered cell. Since the puzzle starts with the empty cell in the corner and ends with the empty cell in the corner, the empty cell has moved an even number of times (every time it goes up, it must go down, and every time it goes left, it must come back right eventually). Therefore any solvable grid needs an even number of transpositions to arrive at original position. So the numbers 1,2,...,14,15 must be in an even permutation with respect to the standard ordering and the empty cell in the lower right corner.

Now, the grid 1,2,3,...,13,14,15, empty, is solvable (it's the starting point). But switching 14 and 15 makes a transposition. Thus the permutation has 1 transposition, which is odd. By a property of permutations, every permutation is always a product of even number or odd number of transpositions, but never both even and odd.
So any permutation of 1,2,3,...,13,15,14, empty that brings it back to 1,2,3,4,...,13,14,15,empty must be odd, and therefore the puzzle is unsolvable!

For the second part, it's only an idea:

Spoiler

In general, every odd permutation of 1,2,3,...,13,14,15 and empty cell in lower-left corner is unsolvable. On the other hand, is every even permutation solvable? (Here I don't use solvable in the Galois sense)
As proven above, every solvable grid must be a permutation in A_{15} with the empty cell in the lower right corner. So the group of solvable permutations is a subgroup of A_{15}. The alternating group of n elements is generated by 3-cycles, so if every 3-cycle permutation can be obtained, we prove that every even permutation is solvable. Now the problem would be to find a set of generators that can be obtained... By moving the empty cell in closed non-intersecting loops of 2n steps, we can generate a 2n-1 cycle. But I am not sure if those odd cycles generate A_n.

 

[Boorglar]

Additional thoughts:

Spoiler

Every solvable grid is obtained by moving the empty cell in a closed curve starting in the lower-right corner, and may intersect itself arbitrarily many times. We can call the associated permutations "solvable permutations". A permutation generated from non-self-intersecting loops (with any starting point, not only the corner) can be called a "simple loop permutation". Every simple loop permutation is in the set of solvable permutations since they can be generated in the following way: from the corner to the starting point, and then do the closed loop in the specified path, and come back to the corner in the reverse way taken to the loop. Then the path leading to the simple loop is left unchanged. The question is then if every solvable permutation is a product of the simple loop permutations.

This suggests a proof by induction on the number of intersections in a path generating a solvable permutation.
If the solvable permutation is generated by a non-self-intersecting path, it is a simple loop permutation with corner as the starting point. Assume all paths with less than n intersections generate products of simple loop permutations. Now if the path interesects itself n-times, consider the subpath coming to and from a given intersection. This path has less than n intersections, and by inductive hypothesis this subpath generates a product of simple loop permutations. The total path's associated permutation is then the product of the permutations generated by each subpath.

Therefore, every solvable permutation is a product of simple loop permutations, and we are done (I think).

But now that I think of it, I'm not sure this leads anywhere in proving that every even permutation is a solvable permutation O.O I should have proven that even permutations are products of simple loop permutations

 

[micromass]

So, I think Boorglar already proved that any odd permutation is unsolvable.
And furthermore, and solvable permutations is the product of "loop permutations".

But we're still missing the proof that any even permutation actually is solvable.

 

[Boorglar]

Ok so I figured a way to make a 3 cycle involving 3 collinear squares (see attachment). Moreover, 3 squares in a "corner" can also be permuted by doing a loop permutation of length 4.

oops I erased my comment here because I think something is not right. I'm constantly finding flaws in what I wrote, so I'll explain the idea. My goal is to be able to generate any 3-cycle using only the 3-cycles of neighboring squares. I haven't found a convincing algorithm yet, though. But if this can be done, then since the 3-cycles generate A_n this would prove that every even permutation is solvable.

 

[mfb]

It is possible to find an algorithm to fix the position of 1, 2, 3 and 4, ... and so on, until 3 pieces in a 2x2 grid are left. One of those can be put in the right position, and then we have 2 options left for the remaining pieces: wrong (-> unsolvable) and correct (->solved). It could be messy to write that algorithm down, but it is easy to find if you play around with such a puzzle.

 

[Boorglar]

mfb, that might just work! Bring 1 to its position. Once you brought 1,2,3,...,n-1 in their positions, you can then bring n in its position by tracing a path which does not intersect with 1,2,...,n-1 and using the special 3-cycles to move n up to its position without touching the squares outside of the path. Such a path can always be drawn since the set of squares not in place is connected, until there are 2 squares left. Then as you said we end up with 1,2,3,...,13,14,15 or 1,2,3,...,13,15,14, one of which is the solved puzzle and the other is odd and unsolvable.
I tried doing that with my Mac's dashboard widget with a picture of a lion, and it worked. In fact corners are sufficient I think.

 

[micromass]

Maybe somebody can try to formulate an induction proof?

Anyway, it appears this challenge was solved by Boorglar and mfb. If somebody can present a nice induction proof, I'll add his name.

Another neat proof using graph theory can be found here: http://www.jstor.org/discover/10.2307/2589612?uid=3737592&uid=2&uid=4&sid=21102537901693

 

[mfb]

Consider the following 2x3-section:
C B A
D E V
where A-E are elements and V is the vacancy. Let "x" denote a move where element x moves to the vacancy. Then the sequence "ABCDEA" (read from left to right) leads to the modified
DCB
EAV
This allows to put an arbitrary element in the upper left corner.
The sequence "EBCDBE" (applied to the original layout) leads to the pattern
DCA
BEV
As you can see, we moved the relative position of C and A by one.

Combining both patterns, we can freely put elements in the leftmost column.

It is trivial to extend this to 2xn-patterns, just shift the vacancy first (reducing the problem to 2x3), perform the necessary movements and shift the vacancy back.

Therefore, the last two rows can be fixed up to the order of the last 3 elements in the lower right corner.

The other rows can be solved first, using the same algorithm. The proof is left as an exercise for the reader.

Note that this proof can be used for any nxm puzzle, as long as n,m>1 (...).