Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Sliding tile puzzle question

  1. Jul 14, 2011 #1
    Given any two random tile arrangements in a sliding tile puzzle, is it always possible to find a way to go from one to the other? It's trivial to prove that this isn't true for 2x2 puzzles, but I don't know how to approach the problem for bigger sizes, short of brute forcing it with a computer. Can you help me find a more elegant solution?
     
  2. jcsd
  3. Jul 14, 2011 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    No, you cannot go from one arrangement to any other.
    The basic idea is that, if you write a given position as a permutation of the original position- that is, number the tiles 1, 2, 3, ..., up to the number of tiles starting from the upper left and going by rows- show that any "reachable" position must be an even permutation of the original position.

    Historically, the original version of the "15" puzzle, instead of having 15 numbers, set in a 4 by 4 grid with a single empty position, had the letters "rate your mind bud ". You could show the original position to a friend, mix up the letters and challenge him to put them back into the original position. The "trick" was to move the "r" in "your" to the first position. People would almost automatically leave that "r" alone since the original form has an "r" there. But switching the two "r"s is an odd permutation. You can't get all the other letters in the original position with the two "r"s reversed.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Sliding tile puzzle question
  1. A puzzle (Replies: 3)

  2. A puzzle (Replies: 7)

Loading...