Challenge VI: 15 Puzzle solved by Boorglar and mfb

In summary, the challenge proposed was to solve a 15-puzzle, where the goal is to rearrange the pieces from an unsolved position to a solved position. The challenge also asked to devise a criterion for determining if a puzzle is solvable or not. Boorglar and mfb were able to prove that any odd permutation is unsolvable, while any even permutation can be solved using a specific algorithm. Additional proofs using graph theory were also presented. Overall, the challenge was successfully solved by Boorglar and mfb.
  • #1
micromass
Staff Emeritus
Science Advisor
Homework Helper
Insights Author
22,183
3,321
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:

477px-15-puzzle-02.jpg


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

md-200911-15puzzle.jpg


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:

15-Puzzle.jpg


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.
 
Last edited by a moderator:
Mathematics news on Phys.org
  • #2
Here's a hint: odd and even permutations.
 
  • #3
Well I think this one is a simple solution (finally a problem I can solve) :P

my solution for the first part:
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:
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 [itex]A_{15}[/itex] with the empty cell in the lower right corner. So the group of solvable permutations is a subgroup of [itex]A_{15}[/itex]. 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 [itex]A_n[/itex].
 
Last edited:
  • #4
Additional thoughts:

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 :blushing:
 
Last edited:
  • #5
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.
 
  • #6
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 [itex]A_n[/itex] this would prove that every even permutation is solvable.
 

Attachments

  • Screen Shot 2013-08-08 at 1.56.23 AM.jpg
    Screen Shot 2013-08-08 at 1.56.23 AM.jpg
    22.8 KB · Views: 619
Last edited:
  • #7
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.
 
  • #8
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.
 
Last edited:
  • #9
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
 
  • #10
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 (...).
 
Last edited:

What is Challenge VI: 15 Puzzle solved by Boorglar and mfb?

Challenge VI: 15 Puzzle solved by Boorglar and mfb is a scientific experiment that aimed to solve the 15 Puzzle, a popular sliding puzzle game, using algorithms and computer programming.

Who are Boorglar and mfb?

Boorglar and mfb are two scientists who participated in the Challenge VI: 15 Puzzle experiment. They are experts in algorithms and computer programming, and their skills were crucial in solving the puzzle.

How did Boorglar and mfb solve the 15 Puzzle?

Boorglar and mfb used a combination of different algorithms to solve the 15 Puzzle. They first created a heuristic function to evaluate the possible moves, and then used an A* search algorithm to find the optimal solution.

What was the significance of Challenge VI: 15 Puzzle solved by Boorglar and mfb?

The significance of this experiment is that it demonstrated the power and efficiency of algorithms and computer programming in solving complex puzzles. It also showed the potential for using these tools in various real-world applications, such as logistics and scheduling problems.

Can the algorithm used by Boorglar and mfb be applied to other puzzles?

Yes, the algorithm used by Boorglar and mfb can be applied to other similar puzzles. However, it may need to be modified and adapted depending on the specific rules and constraints of the puzzle.

Similar threads

Replies
66
Views
4K
Replies
2
Views
7K
  • Math Proof Training and Practice
3
Replies
93
Views
10K
  • Math Proof Training and Practice
2
Replies
42
Views
6K
  • Math Proof Training and Practice
3
Replies
93
Views
6K
  • Math Proof Training and Practice
3
Replies
86
Views
9K
  • Math Proof Training and Practice
3
Replies
102
Views
7K
  • Math Proof Training and Practice
2
Replies
51
Views
7K
  • Math Proof Training and Practice
2
Replies
67
Views
7K
  • General Math
4
Replies
125
Views
16K
Back
Top