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!

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


    User Avatar
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Similar Threads for Sliding tile puzzle
Challenge Math Trick Puzzle
Challenge Origami Puzzle Challenge
B Great Magic Triangle Math Puzzle