1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Challenge VI: 15 Puzzle solved by Boorglar and mfb

  1. Aug 7, 2013 #1

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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: Aug 8, 2013
  2. jcsd
  3. Aug 7, 2013 #2
    Here's a hint: odd and even permutations.
     
  4. Aug 7, 2013 #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: Aug 8, 2013
  5. Aug 7, 2013 #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: Aug 8, 2013
  6. Aug 8, 2013 #5

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    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.
     
  7. Aug 8, 2013 #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.
     

    Attached Files:

    Last edited: Aug 8, 2013
  8. Aug 8, 2013 #7

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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.
     
  9. Aug 8, 2013 #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: Aug 8, 2013
  10. Aug 8, 2013 #9

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

  11. Aug 8, 2013 #10

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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: Aug 8, 2013
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Challenge VI: 15 Puzzle solved by Boorglar and mfb
Loading...