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

TwistyPuzzles.com Forum
 It is currently Fri Jul 25, 2014 11:33 am

 All times are UTC - 5 hours

 Page 1 of 1 [ 30 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: Fifteen puzzle "problem"Posted: Fri May 10, 2013 2:45 pm

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 [ 102.22 KiB | Viewed 3836 times ] P5102089.JPG [ 103.73 KiB | Viewed 3836 times ]

Last edited by iaroslavski on Fri May 10, 2013 4:44 pm, edited 2 times in total.
Top

 Post subject: Re: Fifteen puzzle "problem"Posted: Fri May 10, 2013 4:05 pm

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

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

_________________

Top

 Post subject: Re: Fifteen puzzle "problem"Posted: Fri May 10, 2013 4:14 pm

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!

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

 Post subject: Re: Fifteen puzzle "problem"Posted: Fri May 10, 2013 4:15 pm

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

 Post subject: Re: Fifteen puzzle "problem"Posted: Sun May 12, 2013 3:40 am

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 . 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

 Post subject: Re: Fifteen puzzle "problem"Posted: Sun May 12, 2013 4:49 am

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

_________________
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

 Post subject: Fifteen puzzle "problem"Posted: Sun May 12, 2013 4:52 am

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

Top

 Post subject: Re: Fifteen puzzle "problem"Posted: Sun May 12, 2013 5:04 am

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

 Post subject: Re: Fifteen puzzle "problem"Posted: Sun May 12, 2013 9:24 pm

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

 Post subject: Re: Fifteen puzzle "problem"Posted: Sun May 12, 2013 11:01 pm

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

 Post subject: Re: Fifteen puzzle "problem"Posted: Sun May 12, 2013 11:06 pm

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

 Post subject: Re: Fifteen puzzle "problem"Posted: Wed May 15, 2013 12:11 pm

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

 Post subject: Re: Fifteen puzzle "problem"Posted: Thu May 16, 2013 4:28 am

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

 Post subject: Re: Fifteen puzzle "problem"Posted: Thu May 16, 2013 5:40 am

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!

Top

 Post subject: Re: Fifteen puzzle "problem"Posted: Thu May 16, 2013 7:46 am

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.

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

Top

 Post subject: Re: Fifteen puzzle "problem"Posted: Thu May 16, 2013 10:53 am

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

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

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

Top

 Post subject: Re: Fifteen puzzle "problem"Posted: Thu May 16, 2013 11:11 am

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.

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

Pantazis

Top

 Post subject: Re: Fifteen puzzle "problem"Posted: Thu May 16, 2013 2:08 pm

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

 Post subject: Re: Fifteen puzzle "problem"Posted: Thu May 16, 2013 2:18 pm

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

 Post subject: Re: Fifteen puzzle "problem"Posted: Thu May 16, 2013 2:52 pm

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

 Post subject: Re: Fifteen puzzle "problem"Posted: Thu May 16, 2013 3:03 pm

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

 Post subject: Re: Fifteen puzzle "problem"Posted: Thu May 16, 2013 4:18 pm

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

 Post subject: Re: Fifteen puzzle "problem"Posted: Fri May 17, 2013 12:17 pm

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

 Post subject: Re: Fifteen puzzle "problem"Posted: Fri May 17, 2013 3:09 pm

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

 Post subject: Re: Fifteen puzzle "problem"Posted: Fri May 17, 2013 3:59 pm

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

 Post subject: Re: Fifteen puzzle "problem"Posted: Fri May 17, 2013 4:16 pm

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

 Post subject: Re: Fifteen puzzle "problem"Posted: Fri May 17, 2013 6:35 pm

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!

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

Top

 Post subject: Re: Fifteen puzzle "problem"Posted: Sat May 18, 2013 10:04 am

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

 Post subject: Re: Fifteen puzzle "problem"Posted: Sat May 18, 2013 10:19 am

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

 Post subject: Re: Fifteen puzzle "problem"Posted: Sat May 18, 2013 1:03 pm

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

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 30 posts ]

 All times are UTC - 5 hours

#### Who is online

Users browsing this forum: No registered users and 7 guests

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

Search for:
 Jump to:  Select a forum ------------------ Announcements General Puzzle Topics New Puzzles Puzzle Building and Modding Puzzle Collecting Solving Puzzles Marketplace Non-Twisty Puzzles Site Comments, Suggestions & Questions Content Moderators Off Topic