Online since 2002. Over 3300 puzzles, 2600 worldwide members, and 270,000 messages.

TwistyPuzzles.com Forum

It is currently Sun Apr 20, 2014 12:50 am

All times are UTC - 5 hours



Post new topic Reply to topic  [ 30 posts ] 
Author Message
 Post subject: Fifteen puzzle "problem"
PostPosted: Fri May 10, 2013 2:45 pm 
Offline

Joined: Tue Oct 13, 2009 1:13 am
Location: Saint-Petersburg, Russia
There is well known "problem" of Fifteen puzzle where your
goal is to restore the order when 2 pieces are swapped
(see the first picture). You know this is impossible.

Playing with Fifteen puzzle I found that from the
"impossible" state I can reach other state where
all pieces are ... ordered, see the second picture.

It means that we can "solve" (put all pieces in the
order) from any state. Just interesting...


Attachments:
P5102085.JPG
P5102085.JPG [ 102.22 KiB | Viewed 2964 times ]
P5102089.JPG
P5102089.JPG [ 103.73 KiB | Viewed 2964 times ]


Last edited by iaroslavski on Fri May 10, 2013 4:44 pm, edited 2 times in total.
Top
 Profile  
 
 Post subject: Re: Fifteen puzzle "problem"
PostPosted: Fri May 10, 2013 4:05 pm 
Offline
User avatar

Joined: Mon Dec 05, 2011 3:38 pm
Location: Eindhoven, The Netherlands
GREAT!

As I kid I just loved to play with sliding puzzles.

_________________
Maybe I'm amazed... Mfave's puzzle shop | Burgh Lock trick-lock, Splinter's amazing Shapeways shop, my E-book, maze overview page (Dutch)


Top
 Profile  
 
 Post subject: Re: Fifteen puzzle "problem"
PostPosted: Fri May 10, 2013 4:14 pm 
Offline
User avatar

Joined: Mon Mar 30, 2009 5:13 pm
That *is* very interesting!

I hope some smart-ass will come up to me and bet that I can't solve it, could make a bit of money! :lol:

Now, what's the shortest algorithm to go from state 1 to state 2?

_________________
If you want something you’ve never had, you’ve got to do something you’ve never done - Thomas Jefferson


Last edited by KelvinS on Fri May 10, 2013 4:17 pm, edited 1 time in total.

Top
 Profile  
 
 Post subject: Re: Fifteen puzzle "problem"
PostPosted: Fri May 10, 2013 4:15 pm 
Offline
User avatar

Joined: Fri Feb 18, 2000 8:50 am
Location: chicago, IL area U.S.A
I never thought to do that, I'll have to give it a shot.

-d


Top
 Profile  
 
 Post subject: Re: Fifteen puzzle "problem"
PostPosted: Sun May 12, 2013 3:40 am 
Offline
User avatar

Joined: Tue Feb 08, 2011 3:17 am
Location: Australia
What an elegant solution to a longstanding problem, perfect! Congratulations, I'm so happy when someone ignores the rules and `sticks it to the man` in such a fundamental way. So many have lost sleep over this.. and there you go. Wonderful :D . I face-palmed myself so hard I literally fell off my chair.

_________________
1st 3x3 solve Oct 2010 (Even though I lived through the 80s).
PB 3x3 55sec Jan 2011 (When I was a kid 1:30 was speedcubing so I'm stoked).
1st 3x3 Earth (nemesis) solve Jan 2011 My You Tube (Now has ALLCrazy 3X3 Planets with Reduction)


Top
 Profile  
 
 Post subject: Re: Fifteen puzzle "problem"
PostPosted: Sun May 12, 2013 4:49 am 
Offline
User avatar

Joined: Mon Mar 30, 2009 5:13 pm
I'm thinking you should add this solution to Wikipedia - check the History section. :wink:

_________________
If you want something you’ve never had, you’ve got to do something you’ve never done - Thomas Jefferson


Last edited by KelvinS on Sun May 12, 2013 4:59 am, edited 1 time in total.

Top
 Profile  
 
 Post subject: Fifteen puzzle "problem"
PostPosted: Sun May 12, 2013 4:52 am 
Offline
User avatar

Joined: Tue Mar 24, 2009 12:52 pm
Look here. :D


Top
 Profile  
 
 Post subject: Re: Fifteen puzzle "problem"
PostPosted: Sun May 12, 2013 5:04 am 
Offline
User avatar

Joined: Tue Feb 08, 2011 3:17 am
Location: Australia
The 90* solution is well known, but it's not as elegant as this.. this is the forest for the trees IMO.

_________________
1st 3x3 solve Oct 2010 (Even though I lived through the 80s).
PB 3x3 55sec Jan 2011 (When I was a kid 1:30 was speedcubing so I'm stoked).
1st 3x3 Earth (nemesis) solve Jan 2011 My You Tube (Now has ALLCrazy 3X3 Planets with Reduction)


Top
 Profile  
 
 Post subject: Re: Fifteen puzzle "problem"
PostPosted: Sun May 12, 2013 9:24 pm 
Offline
User avatar

Joined: Fri Feb 18, 2000 8:50 am
Location: chicago, IL area U.S.A
http://migo.sixbit.org/puzzles/fifteen/
The page above makes light of this elegant solution. If you click "pseudo solve" it puts the pieces in the solution with 123 on top. Then they offer $5000 if you can solve it the regular way :)

-d


Top
 Profile  
 
 Post subject: Re: Fifteen puzzle "problem"
PostPosted: Sun May 12, 2013 11:01 pm 
Offline

Joined: Sun Nov 23, 2008 2:18 am
As I cannot see the images, would anyone mind posting a text representation of the the depicted positions?

I know the standard solved state is:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 _

And the classic impossible flip is:

1 2 3 4
5 6 7 8
9 10 11 12
13 15 14 _

with '_' representing the empty slot, but otherwise, I am not following.

_________________
Just so you know, I am blind.

I pledge allegiance to the whole of humanity, and to the world in which we live: one people under the heavens, indivisible, with Liberty and Equality for all.

My Shapeways Shop


Top
 Profile  
 
 Post subject: Re: Fifteen puzzle "problem"
PostPosted: Sun May 12, 2013 11:06 pm 
Offline
User avatar

Joined: Thu Oct 16, 2008 9:46 pm
Location: Littleton CO
Jeffery Mewtamer wrote:
As I cannot see the images, would anyone mind posting a text representation of the the depicted positions?

I know the standard solved state is:
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 _

And the classic impossible flip is:

1 2 3 4
5 6 7 8
9 10 11 12
13 15 14 _

with '_' representing the empty slot, but otherwise, I am not following.

_ 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15


Top
 Profile  
 
 Post subject: Re: Fifteen puzzle "problem"
PostPosted: Wed May 15, 2013 12:11 pm 
Offline
User avatar

Joined: Thu Jun 03, 2010 2:25 pm
Location: Farmington, NM
I'm pretty sure that the optimal solution is 44 moves.

_________________
Autism Speaks can go away. I have Autism. I can speak for myself.

"You say tomater, I zader matermorts." - Coach Z


Top
 Profile  
 
 Post subject: Re: Fifteen puzzle "problem"
PostPosted: Thu May 16, 2013 4:28 am 
Offline
User avatar

Joined: Mon Mar 30, 2009 5:13 pm
Jorbs3210 wrote:
I'm pretty sure that the optimal solution is 44 moves.

Interesting that this is much greater than God's number for a 3x3.

_________________
If you want something you’ve never had, you’ve got to do something you’ve never done - Thomas Jefferson


Top
 Profile  
 
 Post subject: Re: Fifteen puzzle "problem"
PostPosted: Thu May 16, 2013 5:40 am 
Offline
User avatar

Joined: Fri Nov 04, 2005 12:31 am
Location: Greece, Australia, Thailand, India, Singapore.
KelvinS wrote:
Jorbs3210 wrote:
I'm pretty sure that the optimal solution is 44 moves.

Interesting that this is much greater than God's number for a 3x3.



Assuming that you assumed(!) that God's number is related to the difficulty of a puzzle,
(correct me if this is wrong), we can hardly regard this as a criterion for the difficulty of a puzzle.
Because for example, a 1x1x50 twisty puzzle using 50-polygons (i.e. creating 50 sides) instead
of squares (with four sides), would need even more moves than 44, despite being a trivial puzzle.



Pantazis


PS. The solution above as shown in the first post, is so simple yet so elegant. Bravo!

_________________

Educational R&D, Gravity, 4D Symmetry, Puzzle Ninja, Matrix Mech, Alien Technology.


Top
 Profile  
 
 Post subject: Re: Fifteen puzzle "problem"
PostPosted: Thu May 16, 2013 7:46 am 
Offline
User avatar

Joined: Mon Mar 30, 2009 5:13 pm
I just said "interesting", though I'm not sure why, perhaps because there are fewer parts than a 3x3 (15 vs 26), implying that the "global" movements of a 3x3 are more efficient than individual moves of the 15-puzzle, despite the effective bandaging/constraints. :wink:

_________________
If you want something you’ve never had, you’ve got to do something you’ve never done - Thomas Jefferson


Top
 Profile  
 
 Post subject: Re: Fifteen puzzle "problem"
PostPosted: Thu May 16, 2013 10:53 am 
Offline
User avatar

Joined: Thu Jun 03, 2010 2:25 pm
Location: Farmington, NM
Yes, the optimal solution is 44 moves.

14, 11, 12, 8, 7, 6, 10, 12, 8, 7, 4, 3, 6, 4, 7, 8, 4, 10, 5, 9, 12, 4, 8, 14, 11, 15, 13, 12, 4, 8, 14, 11, 15, 14, 10, 5, 9, 4, 8, 9, 5, 6, 2, 1

That wasn't so bad.

_________________
Autism Speaks can go away. I have Autism. I can speak for myself.

"You say tomater, I zader matermorts." - Coach Z


Top
 Profile  
 
 Post subject: Re: Fifteen puzzle "problem"
PostPosted: Thu May 16, 2013 11:11 am 
Offline
User avatar

Joined: Fri Nov 04, 2005 12:31 am
Location: Greece, Australia, Thailand, India, Singapore.
KelvinS wrote:
I just said "interesting", though I'm not sure why, perhaps because there are fewer parts than a 3x3 (15 vs 26), implying that the "global" movements of a 3x3 are more efficient than individual moves of the 15-puzzle, despite the effective bandaging/constraints. :wink:


Indeed, I hadn't thought of that. If we take into account the parts, it is interesting!

8-)


Pantazis

_________________

Educational R&D, Gravity, 4D Symmetry, Puzzle Ninja, Matrix Mech, Alien Technology.


Top
 Profile  
 
 Post subject: Re: Fifteen puzzle "problem"
PostPosted: Thu May 16, 2013 2:08 pm 
Offline

Joined: Mon Aug 18, 2008 10:16 pm
Location: Somewhere Else
Well, the 44 moves is sort of like using the 2D equivalent of "quarter turn metric", isn't it? Not moving multiple tiles in one move?

God's Number for the cube is in half-turn metric. Not sure what it would be in QTM.


Top
 Profile  
 
 Post subject: Re: Fifteen puzzle "problem"
PostPosted: Thu May 16, 2013 2:18 pm 
Offline
User avatar

Joined: Thu Jun 03, 2010 2:25 pm
Location: Farmington, NM
Jared wrote:
Well, the 44 moves is sort of like using the 2D equivalent of "quarter turn metric", isn't it? Not moving multiple tiles in one move?

God's Number for the cube is in half-turn metric. Not sure what it would be in QTM.


It's 22 moves in QTM.

_________________
Autism Speaks can go away. I have Autism. I can speak for myself.

"You say tomater, I zader matermorts." - Coach Z


Top
 Profile  
 
 Post subject: Re: Fifteen puzzle "problem"
PostPosted: Thu May 16, 2013 2:52 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
The 15-puzzle "equivalent" in twisty puzzles is an extremely shallow-cut, big puzzle. It isn't "fair" to compare god's number for the 15-puzzle to a typical twisty puzzle.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Fifteen puzzle "problem"
PostPosted: Thu May 16, 2013 3:03 pm 
Offline
User avatar

Joined: Wed Mar 15, 2000 9:11 pm
Location: Delft, the Netherlands
Jorbs3210 wrote:
Jared wrote:
Well, the 44 moves is sort of like using the 2D equivalent of "quarter turn metric", isn't it? Not moving multiple tiles in one move?

God's Number for the cube is in half-turn metric. Not sure what it would be in QTM.


It's 22 moves in QTM.

No. The position that is a combination of the superflip and the four-spot patterns takes 26q optimally. It is known that 29q moves suffice so God's algorithm in qtm lies between 26 and 29 inclusive.

_________________
Jaap

Jaap's Puzzle Page:
http://www.jaapsch.net/puzzles/


Top
 Profile  
 
 Post subject: Re: Fifteen puzzle "problem"
PostPosted: Thu May 16, 2013 4:18 pm 
Offline
User avatar

Joined: Mon Mar 30, 2009 5:13 pm
bmenrigh wrote:
The 15-puzzle "equivalent" in twisty puzzles is an extremely shallow-cut, big puzzle. It isn't "fair" to compare god's number for the 15-puzzle to a typical twisty puzzle.

Maybe it would be better to compare with a 3D sliding puzzle like Peter's Black Hole. What's God's number for that?

_________________
If you want something you’ve never had, you’ve got to do something you’ve never done - Thomas Jefferson


Top
 Profile  
 
 Post subject: Re: Fifteen puzzle "problem"
PostPosted: Fri May 17, 2013 12:17 pm 
Offline
User avatar

Joined: Fri Oct 26, 2007 6:46 pm
Location: Nacogdoches, Texas
Would a "snaking" pattern be a possible solution? Or, is alternating the direction of the numbers not allowed?

Snaking Solution

1__2__3__4
8__7__6__5
9_10_11_12
__15_14_13


I believe it's only possible to get this solution if two of the numbers are swapped. At least, I couldn't on the normal puzzle, but I didn't try very hard.

_________________
Zachary David Wisniewski


Top
 Profile  
 
 Post subject: Re: Fifteen puzzle "problem"
PostPosted: Fri May 17, 2013 3:09 pm 
Offline
User avatar

Joined: Wed Jan 28, 2009 7:55 pm
Location: Montana
I enjoy the fact that this number scheme starts at 0.

_________________
Andreas Nortmann wrote:
Things like this are illegal.
If not I will pass an appropriate law.


Top
 Profile  
 
 Post subject: Re: Fifteen puzzle "problem"
PostPosted: Fri May 17, 2013 3:59 pm 
Offline
User avatar

Joined: Mon Mar 30, 2009 5:13 pm
Rae wrote:
Would a "snaking" pattern be a possible solution? Or, is alternating the direction of the numbers not allowed?

Snaking Solution

1__2__3__4
8__7__6__5
9_10_11_12
__15_14_13


I believe it's only possible to get this solution if two of the numbers are swapped. At least, I couldn't on the normal puzzle, but I didn't try very hard.

That would not be a correct solution. And if it can't be reached, then this one - which is also not a correct solution - can:

___1__2__3
7__6__5__4
8__9_10_11
15_14_13_12

_________________
If you want something you’ve never had, you’ve got to do something you’ve never done - Thomas Jefferson


Top
 Profile  
 
 Post subject: Re: Fifteen puzzle "problem"
PostPosted: Fri May 17, 2013 4:16 pm 
Offline
User avatar

Joined: Wed Mar 15, 2000 9:11 pm
Location: Delft, the Netherlands
KelvinS wrote:
Rae wrote:
Would a "snaking" pattern be a possible solution? Or, is alternating the direction of the numbers not allowed?

Snaking Solution

1__2__3__4
8__7__6__5
9_10_11_12
__15_14_13


I believe it's only possible to get this solution if two of the numbers are swapped. At least, I couldn't on the normal puzzle, but I didn't try very hard.

That would not be a correct solution. And if it can't be reached, then this one - which is also not a correct solution - can:

___1__2__3
7__6__5__4
8__9_10_11
15_14_13_12

Both of these patterns are reachable from the 14-15 swapped position, and not from the normal solved position. To get from the Kelvin's snake pattern to Rae's just move all the tiles once, in numerical order.

_________________
Jaap

Jaap's Puzzle Page:
http://www.jaapsch.net/puzzles/


Top
 Profile  
 
 Post subject: Re: Fifteen puzzle "problem"
PostPosted: Fri May 17, 2013 6:35 pm 
Offline
User avatar

Joined: Mon Mar 30, 2009 5:13 pm
jaap wrote:
To get from the Kelvin's snake pattern to Rae's just move all the tiles once, in numerical order.

DOH! Big face palm! Yes, I should have realized that a "snake" pattern could move just like a snake! :roll: :lol:

_________________
If you want something you’ve never had, you’ve got to do something you’ve never done - Thomas Jefferson


Top
 Profile  
 
 Post subject: Re: Fifteen puzzle "problem"
PostPosted: Sat May 18, 2013 10:04 am 
Offline

Joined: Sun Nov 23, 2008 2:18 am
is a spiral pattern possible?

For that matter, how many of the 16! permutations are reachable under legal moves and how many orbits they they fall into. Are there any positions not reachable from either the "normal" solve or the "swapped pair" position?

How does questions like the ones in this thread generalize to grids other than 4*4? For example, is swapping a single pair possible on the 5*5 variant of this puzzle?

_________________
Just so you know, I am blind.

I pledge allegiance to the whole of humanity, and to the world in which we live: one people under the heavens, indivisible, with Liberty and Equality for all.

My Shapeways Shop


Top
 Profile  
 
 Post subject: Re: Fifteen puzzle "problem"
PostPosted: Sat May 18, 2013 10:19 am 
Offline
User avatar

Joined: Thu Jun 03, 2010 2:25 pm
Location: Farmington, NM
Jeffery Mewtamer wrote:
For that matter, how many of the 16! permutations are reachable under legal moves and how many orbits they they fall into. Are there any positions not reachable from either the "normal" solve or the "swapped pair" position?


There are 16!/2 legal positions, so any position can be solved into either the normal solve or the "swapped pair" position. That also means that there are only two global orbits for the puzzle.

_________________
Autism Speaks can go away. I have Autism. I can speak for myself.

"You say tomater, I zader matermorts." - Coach Z


Top
 Profile  
 
 Post subject: Re: Fifteen puzzle "problem"
PostPosted: Sat May 18, 2013 1:03 pm 
Offline
User avatar

Joined: Fri Oct 26, 2007 6:46 pm
Location: Nacogdoches, Texas
Jeffery Mewtamer wrote:
is a spiral pattern possible?


For the normal 15 puzzle, I was able to get this pattern
_1__2__3__4
12_13_14__5
11____15__6
10__9__8__7


For the swapped, though, I could only manage this.
_1__2__3__4
12_13_____5
11_14_15__6
10__9__8__7

So, not exactly a complete spiral.

_________________
Zachary David Wisniewski


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 30 posts ] 

All times are UTC - 5 hours


Who is online

Users browsing this forum: No registered users and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  

Forum powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group