Sam Loyd Puzzle Solvability

Source: 15 Puzzle

Problem: The 15-puzzle (also called Gem Puzzle, Boss Puzzle, Game of Fifteen, Mystic Square and many others) is a sliding puzzle that consists of a frame of numbered square tiles in random order with one tile missing. The object of the puzzle is to place the tiles in order (from figure at left to figure at right) by making sliding moves that use the empty space. Prove that the 15 puzzle in the configuration as shown on the left is not solvable.


File:15-puzzle-loyd.svgFile:15-puzzle.svg



Related Links:
I made this fb game yesterday night - 9 Puzzle over Movie Posters - Movie Sliding Puzzle
Sam Loyd published some great puzzles in his time. One book that gets recommended a lot is "Sam Loyd's Cyclopedia of 5000 Puzzles tricks and Conundrums" (Amazon , Flipkart)

Update: (24/12/2012)
Solution provided by Raghuram Kowdeed (IIT Kanpur) in comments!

Update: (24/12/2012)
Same solution posted by Sai Teja Pratap (IIT Bombay CSE Final Year Student) and Eeshaan Malhotra (IIT Bombay) on Quora Board.

Update: (20/12/2014)
I have taken the facebook game down.

Comments

  1. Unknown9:02 AM, November 19, 2012

    here is solution.
    write the numbers horizontally so that it represents permutation of numbers 1-15(ignore the blank box).there are two different kind of slides possible.
    1.horizontal slide
    2.vertical slide
    horizontal slide does not change the permutation
    effect of vertical slide is change the position of a particular element by 3 units .for example in the figure 1 shown if 12 and the blank spot are swapped ,in the permutation position of 12 is 15,and position of 13,15,14 decreases by 1 and rest unchanged.now let us consider the parity of of number of inversions in a permutation.initial permutation has odd number of inversions.final one has even number of permutations.
    only vertical slide toggles the parity.
    since the blank occupies same row in both configuration,number of vertical slides are even. that is parity of initial and final permutations can not be different.
    so not possible

    ReplyDelete
  2. Pratik Poddar8:28 AM, December 24, 2012

    Correct solution raghuram. Thanks a ton.

    ReplyDelete

Post a Comment

Popular posts from this blog

Buying Dimsums

Source: Alok Goyal (Stellaris VP, Ex-Helion VC) puzzle blog Problem: A fast food restaurant sells dimsums in boxes of 7 and 3. What’s the greatest number of dimsums a person cannot buy. Generalize it for p and q where p and q are relatively prime. I loved the puzzle. Hope you enjoy it too.
Read more

Fraction Brainteaser

Source: Sent to me by Gaurav Sinha Problem: Siddhant writes a Maths test and correctly answers 5 out of 6 Arithmetic questions and 20 out of 28 Geometry questions.  In total, Siddhant scores 25 out of 34.  Vaibhav writes another Maths test and correctly answers 20 out of 25 Arithmetic questions and 6 out of 9 Geometry questions. in total, Vaibhav scores 26 out of 34. Note that a) Vaibhav scores more than Siddhant b) Siddhant score better than Vaibhav in both individual topics -  5/6 > 20/25 and 20/28 > 6/9 How is it possible? 
Read more

Consecutive Heads

Let's say A keep tossing a fair coin, until he get 2 consecutive heads, define X to be the number of tosses for this process; B keep tossing another fair coin, until he get 3 consecutive heads, define Y to be the number of the tosses for this process. 1) Calculate P{X>Y} 2) What's the expected value of X 3) What's the expected value of Y This is probably the hardest puzzle I have ever put on my blog. Hence, I will post its solution in the post directly rather than on comment. Solution: 1) (Solved by me finally after 13 months :)) Make a state diagram. Let the state be (a,b) where a is the number of consecutive heads streak "A" is on currently and b is the number of consecutive heads streak "B" is on currently. So, (0,3) (1,3) are final accepted states and (2,0) (2,1) (2,2) (2,3) are failure states. If you get tails, your contribution to the state reaches to "0" f(State) = P(X>Y | "State" configuration initially) ...
Read more