Author |
Topic: 15-14 Slide Puzzle (Read 3435 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
15-14 Slide Puzzle
« on: Oct 20th, 2002, 12:15am » |
 Quote  Modify
|
Many of us have had experience with slide puzzles, in which there are tiles numbered from 1 through 15, and you have to slide the tiles such that the numbers are in increasing sequence when read from left to right, top row to bottom. Other variants have fragments of a picture printed on the tiles.
Can you solve the following slide puzzles? If so, list a sequence of moves that produce a solution; if not, explain rigorously. We want the first puzzle to read "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15", and we want the second puzzle to read "Rate Your Mind Pal."
|
| « Last Edit: Oct 20th, 2002, 12:15am by william wu » |
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: 15-14 Slide Puzzle
« Reply #1 on: Oct 20th, 2002, 12:42am » |
Quote Modify
|
That takes me back. When I was a kid, I read about 15 puzzles, probably in a Martin Gardner book, and my dad and I made a RATE YOUR MIND PAL puzzle by modifying a regular 15 puzzle -- we sanded off the numbers and stuck on Rotex (similar to Dymo) labels with the letters.
The puzzles actually go back at least to Sam Loyd.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
Pietro K.C.
Full Member
 
Gender:
Posts: 213
|
|
Re: 15-14 Slide Puzzle
« Reply #2 on: Oct 20th, 2002, 8:27am » |
Quote Modify
|
I have a hunch that, in the solution to the second, we might read "Rate your mind pal", but, if we do, the color of the A's will not match the color of their respective surroundings...
Really strong hint for #1:
It cannot be solved. Consider the correct position of the numbers, i.e. the final answer you are trying to get to. Clearly, you can solve the puzzle IFF you can get from the final answer to the given configuration (with 14 & 15 exchanged). Now find an invariant of the puzzle, one that will hold for every configuration starting with the correct one, but does not hold for the given one.
|
|
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
Jonathan_the_Red
Junior Member
Gender:
Posts: 102
|
|
Re: 15-14 Slide Puzzle
« Reply #3 on: Oct 20th, 2002, 9:18am » |
Quote Modify
|
Actually, you can solve RATEYOURMINDPLA without switching the color of the A's. Really.
|
|
IP Logged |
My arcade cabinet
|
|
|
Pietro K.C.
Full Member
Gender:
Posts: 213
|
|
Re: 15-14 Slide Puzzle
« Reply #4 on: Oct 20th, 2002, 4:36pm » |
Quote Modify
|
Right!!! 
I completely missed the other possibility. I haven't solved it, but, if you say it is possible, it must also be possible without switching the A's. However, if the leftmost eight squares were dark blue, and the 7 rightmost were light blue, we would have a letter not matching its surroundings.
This must be really confusing for people who did not read the hint. 
|
|
IP Logged |
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
|
|
|
GRAND_ADMRL_THUORN
Newbie
THE DARK TOWER IS NEAR!
  
Gender:
Posts: 10
|
|
Re: 15-14 Slide Puzzle
« Reply #5 on: Oct 30th, 2002, 4:20pm » |
Quote Modify
|
The 15-14 variation of the slide puzzle is impossible to solve. A slide puzzle with square pieces can only be solved when the number of exchanges necessary to solve the puzzle is even. But the "rate you mind pal" is solvable if you disregard the color of the "A"s, if the question mandates the the colors stay the same on a given line then it becomes the same as the 15-14 variation and only has 1 exchange making it unsolvable.
And thats your answer! 
|
|
IP Logged |
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: 15-14 Slide Puzzle
« Reply #6 on: Oct 30th, 2002, 6:41pm » |
Quote Modify
|
on Oct 30th, 2002, 4:20pm, GRAND_ADMRL_THUORN wrote:| The 15-14 variation of the slide puzzle is impossible to solve. A slide puzzle with square pieces can only be solved when the number of exchanges necessary to solve the puzzle is even. |
|
This is true, but it's not an solution to the puzzle without a proof.
Quote:| But the "rate you mind pal" is solvable if you disregard the color of the "A"s, if the question mandates the the colors stay the same on a given line then it becomes the same as the 15-14 variation and only has 1 exchange making it unsolvable. |
|
Check you speling and lok again, pal.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
GRAND_ADMRL_THUORN
Newbie
THE DARK TOWER IS NEAR!
Gender:
Posts: 10
|
|
Re: 15-14 Slide Puzzle
« Reply #7 on: Oct 30th, 2002, 6:51pm » |
Quote Modify
|
c'mon timmann, you're going to knock me on my spelling?
this is a riddle site not a grammer site, i would rather have people reading this forum think;"hey that thuorn guy makes some interesting comments", instead of;"wow that thuorn guy sure do spelly good". 
and i know i didnt show proof, ill leave that to one of the super intelligent and math inclined members of this forum.
|
|
IP Logged |
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: 15-14 Slide Puzzle
« Reply #8 on: Oct 30th, 2002, 8:19pm » |
Quote Modify
|
on Oct 30th, 2002, 6:51pm, GRAND_ADMRL_THUORN wrote:| c'mon timmann, you're going to knock me on my spelling? |
|
I wasn't; I was trying to give a subtle hint about why RATE YOUR MIND PLA can be turned into RATE YOUR MIND PAL without messing up the colors. Sorry to have offended you.
Here's the reason:
You missed that there are two Rs, and those are the same color. In your message, you wrote "rate you mind pal", leaving out one of the Rs, making it harder to see that there are really two. Notice I left letters out of my reply as part of the attempt at a hint.
|
| « Last Edit: Oct 30th, 2002, 8:21pm by TimMann » |
IP Logged |
http://tim-mann.org/
|
|
|
GRAND_ADMRL_THUORN
Newbie
THE DARK TOWER IS NEAR!
Gender:
Posts: 10
|
|
Re: 15-14 Slide Puzzle
« Reply #9 on: Oct 31st, 2002, 1:44pm » |
Quote Modify
|
hmm, i see, i didnt realize you were so sneaky timmann, bery bery sneaky sir 
|
|
IP Logged |
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: 15-14 Slide Puzzle
« Reply #10 on: Nov 1st, 2002, 6:33pm » |
Quote Modify
|
Here's my proof of the Admiral's statement.
Consider the empty square as another tile, so we're now concerned with permuting 16 tiles. A permutation of the 15 "real" tiles is simply a permutation of the 16 tiles that leaves the empty square in the same location it was before.
The only moves we can make involve swapping the empty square tile with an adjacent tile -- everything else we can do is simply a sequence of such moves.
Imagine coloring the inside back of the puzzle in a checkerboard pattern. Then every move you can make switches the color showing through the empty square between red and black. Any sequence of moves you can make that brings the empty square back to where it was before returns its color to what it was before, and therefore involves an even number of moves, so it's an even permutation of the 16 tiles. Thus it's also an even permutation of the 15 tiles.
So there is no way to produce an odd permutation of the 15 tiles.
This of course doesn't show that every even permutation of the 15 tiles is attainable. Anyone care to step up and do that?
|
|
IP Logged |
http://tim-mann.org/
|
|
|
rmsgrey
Uberpuzzler
 
Gender:
Posts: 2873
|
|
Re: 15-14 Slide Puzzle
« Reply #11 on: Apr 15th, 2003, 11:49am » |
Quote Modify
|
The first puzzle can be solved. Can't get hide to work properly, so I'll just give a hint: the proof it won't makes one large assumption.
And I would post move sequences, really I would, but I'm too tired right now to work them out and keep track of 15 pieces in my head... OK, I've googled up a Java version... bear with me:
First problem solution (using hexadecimal notation do indicate which piece to move into the space at each step):
efd9abcefd9abcefd9ce9ce9fdce9fecdefba9cdefba9cdefba9cdefb784321568432156 847a986546541237654
The second problem's solution relies on swapping the 'R's transparently
|
| « Last Edit: Apr 15th, 2003, 12:04pm by rmsgrey » |
IP Logged |
|
|
|
cho
Guest
|
rms, your solution doesn't work. When you get to the first 7, the 7 is not next to the open space, and even assuming a missed step or two, the remaining steps cannot solve the problem.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: 15-14 Slide Puzzle
« Reply #13 on: Apr 22nd, 2003, 9:52am » |
Quote Modify
|
You're right - working through again, this should be correct (alterations in bold):
efd9abcefd9abcefd9ce9ce9fdce9fecdefba9cdefba9cdefba9cdefba784321568432 156847abfedc86546541237654
|
| « Last Edit: Apr 22nd, 2003, 9:53am by rmsgrey » |
IP Logged |
|
|
|
mistysakura
Junior Member
Gender: 
Posts: 121
|
|
Re: 15-14 Slide Puzzle
« Reply #14 on: Apr 23rd, 2003, 1:23am » |
Quote Modify
|
but if the first puzzle is solvable, then the second puzzle should also be solvable using the same method, since the relative places of the tiles are the same.
|
|
IP Logged |
|
|
|
redPEPPER
Full Member
Posts: 160
|
|
Re: 15-14 Slide Puzzle
« Reply #15 on: Apr 23rd, 2003, 5:45am » |
Quote Modify
|
I verified rmsgrey's method and it works. I even re-read the original riddle to see if it was an acceptable answer (because of the trick used) and it perfectly answers the problem. This method cannot be applied to problem #2 because the trick used can't be applied to the second problem. However, the second problem can also be solved, using a trick that can't be applied to the first problem, as presented earlier in this thread.
This is what's great about this puzzle: they look the same but there's no common way to solve them. Each needs its own solution based on its special properties.
I found several ways to solve the first one in less moves, using the same trick. Maybe it's not as elegant, though:
ebcebfd9acebfdca9cdea (might not be optimal)
|
| « Last Edit: Apr 23rd, 2003, 5:50am by redPEPPER » |
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2873
|
|
Re: 15-14 Slide Puzzle
« Reply #16 on: Apr 23rd, 2003, 1:20pm » |
Quote Modify
|
Actually, I'm not convinced redPEPPER's alternate solution is entirely valid -
The original statement requires the puzzle to read "1 2 3 4 5 6 7 8 9 10 11 12 13 14 15" but makes no mention of the blank. Either prepending or appending the blank to the solution string seems more natural than inserting it in the middle somewhere...
Apart from that minor quibble, I agree that the sequence given (assuming it does what I expect it does) is a much shorter solution though the end result is less aesthetically pleasing.
|
|
IP Logged |
|
|
|
TimMann
Senior Riddler
Gender:
Posts: 330
|
|
Re: 15-14 Slide Puzzle
« Reply #17 on: May 12th, 2003, 10:33pm » |
Quote Modify
|
Heh, rmsgrey's solution is cute. I didn't read the problem carefully enough to see that it was open to being interpreted differently from the original 14-15 puzzle. My proof of course assumes that you have to end up with the empty square back in the lower right hand corner.
|
|
IP Logged |
http://tim-mann.org/
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove