Article View: rec.puzzles
Article #2754Re: Rubik's tour.
From: Androcles
Date: Sun, 23 Jan 2000 00:00
Date: Sun, 23 Jan 2000 00:00
468 lines
21593 bytes
21593 bytes
This is a multi-part message in MIME format. ------=_NextPart_000_0012_01BF6599.5A05E280 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Hana Bizek <hbizek@ameritech.net> wrote in message = news:388AF552.61B0@ameritech.net... > Androcles wrote: > >=20 > > Hana Bizek <hbizek@ameritech.net> wrote in message > > news:38884C17.50BD@ameritech.net... > > > Androcles wrote: > > > > > > > > Sorry Hana, no offense intended. I just had not heard you = mention it, > > > > that's all. :-) > > > > Androcles > > > > > > I am not offended. Amused is more like it. > > > > > > The reason I did not mention the fact is that I felt it to be too > > > obvious. Besides, the original purpose of my post was not to give = a > > > lecture, but to ask you if you know of someone, who creates > > > 3-dimensional designs from Rubik's cubes. But I devote a whole = chapter > > > in my book to thie fact that elements in a Rubik's cube form a > > > mathematical group. (The book has been published, so it is not a > > > manuscript any more. :-) ) If you can get a hold of it, you will = find > > > group information in Chapter 2. > > > > > > Permit me to disclose one tidbit about myself. I studied some = group > > > theory as part of my PhD dissertation in theoretical solid-state > > > physics. So I am not a mathematician, but simewhat close. :-) > > > Hana a kostky > > Okay, well, for amusement only: > > There is a well-known little puzzle known as the "Knight's Tour". > > The object of the puzzle is to have the (chess) knight visit all 64 = squares > > on the chessboard > > once and once only, according to his usual move, being 1 square in = x, two > > squares in y, or 1 square in y and two in x. > > First question: > > After the knight has completed the tour, what is the least number of = moves > > needed to return to the starting position? > > Second question: > > Can this result be modified by taking a different tour? > > Suppose we have Rubik's cube, and suggest a tour such that all = possible > > outcomes of the various configurations are presented. We begin with = the > > identity. > > Question three, analogous to the knight's tour. > > How many configurations are there, each to be visited once and once = only? > > Question four. > > Is this possible? > > Question five: > > How many moves does it take to return to the identity? > > Androcles >=20 > I am sorry to respond this late, Androcles, but I needed to think = things > over. I am not familiar with the Knight's tour puzzle. Indeed, I have > some hazy notion of how a knight moves, but your explanation of this > point is good and I understand it. > Please look ar these remarks as coming from a relative ignoramus, but = if > a tour is a continous parh across a chessboard, then you do not have > that in case of a Pubik's cube. One sequence may position a certain > cubie in ine place, anorther sequence may position it elsewhere on the > whole cube.It's an entirely different approachh, and one that is not > easily equated. > Hana a kostky Actually, Hana, the knight's tour is really quite simple. I was using it as an example. Beginning at the corner, 0, the operator = (2x1y) or (1x2y) places the knight at either of the squares marked 1 and = 63. Because the board is symmetric, these are actually equivalent (view with a fixed font) +---+---+---+---+---+---+---+---+ | 0 | | 2 | | | | | | +---+---+---+---+---+---+---+---+ | | | 63| 2 | | | | |=20 +---+---+---+---+---+---+---+---+ | | 1 | | | | | | |=20 +---+---+---+---+---+---+---+---+ | | | | 2 | | | | |=20 +---+---+---+---+---+---+---+---+ | 2 | | 2 | | | | | |=20 +---+---+---+---+---+---+---+---+ | | | | | | | | |=20 +---+---+---+---+---+---+---+---+ | | | | | | | | |=20 +---+---+---+---+---+---+---+---+ | | | | | | | | | +---+---+---+---+---+---+---+---+ From there, the choices are the squares marked 2 - a return to 0 isn't = permitted for a tour. The very last move must be from square 63 to 0. Now it seems to me that the rotation operators of Rubik's cube could be = laid out in a string. There are 8 corner (3-color) cubies and 8 edge = cubies (2-color) that can occupy any given face, and of course the = middle of the face doesn't ever change (we are not considering a = rotation of the entire cube in the view of the observer).=20 However, once a corner cubie has been selected for position on one face, = it inevitably determines the corner color on two other faces. Hence the = last face is predetermined by the color selection for 5 faces. In the simulator http://www.mud.ca/cube/cube.html John Bailey found, rotation of the center slice is actually a bit of a = cheat, since it is really two moves, one each for the outer slices and a = rotation of the entire cube in the view of the observer. In the tour, we = would consider this an invalid move. I do applaud the simulator, though = - it is a very nice piece of work.=20 So, keeping the orientation of the face centers constant with respect to = the viewer, the question becomes this. Can the six operations (UDLRFB) = be performed in such a sequence that all members of the group are found = once and once only, the last move returning to the identity? Your intuition here, it would seem, is that it cannot. My intuition is that it can, just like the knight's tour. Now can you (or any other mathematician here) prove such a sequence = exists? Assuming it can, then we have completely solved Rubik's cube for any = given random scramble, from identity through all possibilities and back = to identity, albeit by exhaustion. The question then becomes: Given that from any given scramble there is a path back to the identity = described by the tour and by the inverse operations that caused the = scramble to begin with, which of these two routes is the shorter path? = (In other words, did the scramble exceed a point halfway through the = tour?) The next question then becomes - is there a shortcut from any given = point on the tour that returns us to the identity with fewer moves than = the inverse operations or completion of the tour? I see the tour as a circle, and a shortcut would be a chord on that = circle.=20 My intuition tells me there are such chords, but I cannot prove it. Such = a chord would be the equivalent of finding the shortest route home (the = identity) from any square on the knight's tour, and they obviously = exist. Androcles ------=_NextPart_000_0012_01BF6599.5A05E280 Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"> <HTML><HEAD> <META content=3D"text/html; charset=3Diso-8859-1" = http-equiv=3DContent-Type> <META content=3D"MSHTML 5.00.2014.210" name=3DGENERATOR> <STYLE></STYLE> </HEAD> <BODY background=3D"" bgColor=3D#ffffff> <DIV><BR><FONT face=3D"Courier New" size=3D2>Hana Bizek = <hbizek@ameritech.net>=20 wrote in message news:388AF552.61B0@ameritech.net...<BR>> Androcles=20 wrote:<BR>> > <BR>> > Hana Bizek = <hbizek@ameritech.net> wrote=20 in message<BR>> > news:38884C17.50BD@ameritech.net...<BR>> > = >=20 Androcles wrote:<BR>> > > ><BR>> > > > Sorry = Hana, no=20 offense intended. I just had not heard you mention it,<BR>> = > >=20 > that's all. :-)<BR>> > > > Androcles<BR>> > = ><BR>>=20 > > I am not offended. Amused is more like it.<BR>> > = ><BR>>=20 > > The reason I did not mention the fact is that I felt it to be=20 too<BR>> > > obvious. Besides, the original purpose of my post = was not=20 to give a<BR>> > > lecture, but to ask you if you know of = someone, who=20 creates<BR>> > > 3-dimensional designs from Rubik's cubes. But = I devote=20 a whole chapter<BR>> > > in my book to thie fact that elements = in a=20 Rubik's cube form a<BR>> > > mathematical group. (The book has = been=20 published, so it is not a<BR>> > > manuscript any more. :-) ) = If you=20 can get a hold of it, you will find<BR>> > > group information = in=20 Chapter 2.<BR>> > ><BR>> > > Permit me to disclose one = tidbit=20 about myself. I studied some group<BR>> > > theory as part of = my PhD=20 dissertation in theoretical solid-state<BR>> > > physics. So I = am not a=20 mathematician, but simewhat close. :-)<BR>> > > Hana a = kostky<BR>>=20 > Okay, well, for amusement only:<BR>> > There is a well-known = little=20 puzzle known as the "Knight's Tour".<BR>> > The object of the = puzzle is to=20 have the (chess) knight visit all 64 squares<BR>> > on the=20 chessboard<BR>> > once and once only, according to his usual move, = being 1=20 square in x, two<BR>> > squares in y, or 1 square in y and two in=20 x.<BR>> > First question:<BR>> > After the knight has = completed the=20 tour, what is the least number of moves<BR>> > needed to return to = the=20 starting position?<BR>> > Second question:<BR>> > Can this = result be=20 modified by taking a different tour?<BR>> > Suppose we have = Rubik's cube,=20 and suggest a tour such that all possible<BR>> > outcomes of the = various=20 configurations are presented. We begin with the<BR>> > = identity.<BR>>=20 > Question three, analogous to the knight's tour.<BR>> > = How many=20 configurations are there, each to be visited once and once only?<BR>> = >=20 Question four.<BR>> > Is this possible?<BR>> > Question=20 five:<BR>> > How many moves does it take to return to the=20 identity?<BR>> > Androcles<BR>> <BR>> I am sorry to respond = this=20 late, Androcles, but I needed to think things<BR>> over. I am not = familiar=20 with the Knight's tour puzzle. Indeed, I have<BR>> some hazy notion = of how a=20 knight moves, but your explanation of this<BR>> point is good and I=20 understand it.<BR>> Please look ar these remarks as coming from a = relative=20 ignoramus, but if<BR>> a tour is a continous parh across a = chessboard, then=20 you do not have<BR>> that in case of a Pubik's cube. One sequence may = position a certain<BR>> cubie in ine place, anorther sequence may = position it=20 elsewhere on the<BR>> whole cube.It's an entirely different = approachh, and=20 one that is not<BR>> easily equated.<BR>> Hana a = kostky<BR>Actually, Hana,=20 the knight's tour is really quite simple.</FONT></DIV> <DIV><FONT face=3D"Courier New" size=3D2>I was using it as an example. = Beginning at=20 the corner, 0, the operator (2x1y) or (1x2y) places the knight at either = of the=20 squares marked 1 and 63. Because the board is symmetric, these are = actually=20 equivalent</FONT></DIV> <DIV><FONT face=3D"Courier New" size=3D2>(view with a fixed = font)</FONT></DIV> <DIV><FONT face=3D"Courier New" size=3D2> <DIV><FONT face=3D"Courier New" size=3D2><FONT face=3D"Courier New" = size=3D2> <DIV><FONT face=3D"Courier New" size=3D2>+---+<FONT face=3D"Courier New" = size=3D2>---+<FONT face=3D"Courier New" size=3D2>--<FONT face=3D"Courier = New"=20 size=3D2>-+---+<FONT face=3D"Courier New" size=3D2>---+<FONT = face=3D"Courier New"=20 size=3D2>---+<FONT face=3D"Courier New" size=3D2>--<FONT face=3D"Courier = New"=20 size=3D2>-+---+</FONT></FONT></FONT></FONT></FONT></FONT></FONT></FONT></= DIV> <DIV>| 0 | | 2 | | | =20 | | |</DIV> <DIV><FONT face=3D"Courier New" size=3D2> <DIV><FONT face=3D"Courier New" size=3D2><FONT face=3D"Courier New" = size=3D2><FONT=20 face=3D"Courier New" size=3D2>+---+<FONT face=3D"Courier New" = size=3D2>---+<FONT=20 face=3D"Courier New" size=3D2>--<FONT face=3D"Courier New" = size=3D2>-+---+<FONT=20 face=3D"Courier New" size=3D2>---+<FONT face=3D"Courier New" = size=3D2>---+<FONT=20 face=3D"Courier New" size=3D2>--<FONT face=3D"Courier New"=20 size=3D2>-+---+</FONT></FONT></FONT></FONT></FONT></FONT></FONT></FONT> <DIV>| | = | 63| 2 | =20 | | | |<FONT face=3D"Courier New" = size=3D2>=20 <DIV><FONT face=3D"Courier New" size=3D2>+---+<FONT face=3D"Courier New" = size=3D2>---+<FONT face=3D"Courier New" size=3D2>--<FONT face=3D"Courier = New"=20 size=3D2>-+---+<FONT face=3D"Courier New" size=3D2>---+<FONT = face=3D"Courier New"=20 size=3D2>---+<FONT face=3D"Courier New" size=3D2>--<FONT face=3D"Courier = New"=20 size=3D2>-+---+</FONT></FONT></FONT></FONT></FONT></FONT></FONT></FONT></= DIV> <DIV>| | 1 | | | = | =20 | | |<FONT face=3D"Courier New" size=3D2>=20 <DIV><FONT face=3D"Courier New" size=3D2>+---+<FONT face=3D"Courier New" = size=3D2>---+<FONT face=3D"Courier New" size=3D2>--<FONT face=3D"Courier = New"=20 size=3D2>-+---+<FONT face=3D"Courier New" size=3D2>---+<FONT = face=3D"Courier New"=20 size=3D2>---+<FONT face=3D"Courier New" size=3D2>--<FONT face=3D"Courier = New"=20 size=3D2>-+---+</FONT></FONT></FONT></FONT></FONT></FONT></FONT></FONT></= DIV> <DIV>| | | = | 2 | =20 | | | |<FONT face=3D"Courier New" = size=3D2>=20 <DIV><FONT face=3D"Courier New" size=3D2>+---+<FONT face=3D"Courier New" = size=3D2>---+<FONT face=3D"Courier New" size=3D2>--<FONT face=3D"Courier = New"=20 size=3D2>-+---+<FONT face=3D"Courier New" size=3D2>---+<FONT = face=3D"Courier New"=20 size=3D2>---+<FONT face=3D"Courier New" size=3D2>--<FONT face=3D"Courier = New"=20 size=3D2>-+---+</FONT></FONT></FONT></FONT></FONT></FONT></FONT></FONT></= DIV> <DIV>| 2 | | 2 = | | =20 | | | |<FONT face=3D"Courier New" = size=3D2>=20 <DIV><FONT face=3D"Courier New" size=3D2>+---+<FONT face=3D"Courier New" = size=3D2>---+<FONT face=3D"Courier New" size=3D2>--<FONT face=3D"Courier = New"=20 size=3D2>-+---+<FONT face=3D"Courier New" size=3D2>---+<FONT = face=3D"Courier New"=20 size=3D2>---+<FONT face=3D"Courier New" size=3D2>--<FONT face=3D"Courier = New"=20 size=3D2>-+---+</FONT></FONT></FONT></FONT></FONT></FONT></FONT></FONT></= DIV> <DIV>| | | =20 | | | | = | =20 |<FONT face=3D"Courier New" size=3D2>=20 <DIV><FONT face=3D"Courier New" size=3D2>+---+<FONT face=3D"Courier New" = size=3D2>---+<FONT face=3D"Courier New" size=3D2>--<FONT face=3D"Courier = New"=20 size=3D2>-+---+<FONT face=3D"Courier New" size=3D2>---+<FONT = face=3D"Courier New"=20 size=3D2>---+<FONT face=3D"Courier New" size=3D2>--<FONT face=3D"Courier = New"=20 size=3D2>-+---+</FONT></FONT></FONT></FONT></FONT></FONT></FONT></FONT></= DIV> <DIV>| | | =20 | | | | = | =20 |<FONT face=3D"Courier New" size=3D2>=20 <DIV><FONT face=3D"Courier New" size=3D2>+---+<FONT face=3D"Courier New" = size=3D2>---+<FONT face=3D"Courier New" size=3D2>--<FONT face=3D"Courier = New"=20 size=3D2>-+---+<FONT face=3D"Courier New" size=3D2>---+<FONT = face=3D"Courier New"=20 size=3D2>---+<FONT face=3D"Courier New" size=3D2>--<FONT face=3D"Courier = New"=20 size=3D2>-+---+</FONT></FONT></FONT></FONT></FONT></FONT></FONT></FONT></= DIV> <DIV>| | | =20 | | | | = | =20 |</DIV> <DIV> <DIV><FONT face=3D"Courier New" size=3D2>+---+<FONT face=3D"Courier New" = size=3D2>---+<FONT face=3D"Courier New" size=3D2>--<FONT face=3D"Courier = New"=20 size=3D2>-+---+<FONT face=3D"Courier New" size=3D2>---+<FONT = face=3D"Courier New"=20 size=3D2>---+<FONT face=3D"Courier New" size=3D2>--<FONT face=3D"Courier = New"=20 size=3D2>-+---+</FONT></FONT></FONT></FONT></FONT></FONT></FONT></FONT></= DIV></DIV></FONT></DIV></FONT></DIV></FONT></DIV></FONT></DIV></FONT></DI= V></FONT></DIV></FONT></FONT></DIV></FONT></DIV></FONT></FONT></DIV> <DIV> </DIV> <DIV>From there, the choices are the squares marked 2 - a return to 0 = isn't=20 permitted for a tour. The very last move must be from square 63 to = 0.</DIV> <DIV>Now it seems to me that the rotation operators of Rubik's cube = could be=20 laid out in a string. There are 8 corner (3-color) cubies and 8 edge = cubies=20 (2-color) that can occupy any given face, and of course the middle of = the face=20 doesn't ever change (we are not considering a rotation of the entire = cube in the=20 view of the observer). </DIV> <DIV>However, once a corner cubie has been selected for position on one = face,=20 it inevitably determines the corner color on two other faces. Hence = the=20 last face is predetermined by the color selection for 5 faces.</DIV> <DIV>In the simulator</DIV> <DIV><A=20 href=3D"http://www.mud.ca/cube/cube.html">http://www.mud.ca/cube/cube.htm= l</A><BR>John=20 Bailey found, rotation of the center slice is actually a bit of a cheat, = since=20 it is really two moves, one each for the outer slices and a rotation of = the=20 entire cube in the view of the observer. In the tour, we would consider = this an=20 invalid move. I do applaud the simulator, though - it is a = very nice=20 piece of work. </DIV> <DIV>So, keeping the orientation of the face centers constant with = respect to=20 the viewer, the question becomes this. Can the six operations (UDLRFB) = be=20 performed in such a sequence that all members of the group are found = once and=20 once only, the last move returning to the identity?</DIV> <DIV>Your intuition here, it would seem, is that it cannot.</DIV> <DIV>My intuition is that it can, just like the knight's tour.</DIV> <DIV>Now can you (or any other mathematician here) prove such a = sequence=20 exists?</DIV> <DIV>Assuming it can, then we have completely solved Rubik's cube for = any given=20 random scramble, from identity through all possibilities and back to = identity,=20 albeit by exhaustion.</DIV> <DIV>The question then becomes:</DIV> <DIV>Given that from any given scramble there is a path back to the = identity=20 described by the tour and by the inverse operations that caused the = scramble to=20 begin with, which of these two routes is the shorter path? (In other = words, did=20 the scramble exceed a point halfway through the tour?)</DIV> <DIV>The next question then becomes - is there a shortcut from any given = point=20 on the tour that returns us to the identity with fewer moves than the = inverse=20 operations or completion of the tour?</DIV> <DIV>I see the tour as a circle, and a shortcut would be a chord on that = circle.=20 </DIV> <DIV>My intuition tells me there are such chords, but I cannot = prove it.=20 Such a chord would be the equivalent of finding the shortest route = home=20 (the identity) from any square on the knight's tour, and they obviously=20 exist.</DIV> <DIV>Androcles</DIV> <DIV> </DIV> <DIV> </DIV> <DIV> </DIV> <DIV> </DIV> <DIV> </DIV> <DIV> </DIV> <DIV> </DIV></FONT></DIV></BODY></HTML> ------=_NextPart_000_0012_01BF6599.5A05E280--
Technical Details
Message-ID:
<4pGi4.5458$j63.656468@news1.rdc2.pa.home.com>Path:
arc1-ca.pugleaf.net!unknown!not-for-mailReferences:
<387DD6C1.24CC@ameritech.net> <xuMh4.3648$j63.455581@news1.rdc2.pa.home.com> <3887BFD4.116B@ameritech.net> <NMSh4.3936$j63.485453@news1.rdc2.pa.home.com> <38884C17.50BD@ameritech.net> <M66i4.4432$j63.528634@news1.rdc2.pa.home.com> <388AF552.61B0@ameritech.net>Show Full Headers
Complete Article Headers
X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: fa70b,cb2f33b9a8d8dd55 X-Google-Attributes: gidfa70b,public X-Google-Thread: 10b299,cb2f33b9a8d8dd55 X-Google-Attributes: gid10b299,public X-Google-Thread: fee76,cb2f33b9a8d8dd55 X-Google-Attributes: gidfee76,public X-Google-Thread: 102524,cb2f33b9a8d8dd55 X-Google-Attributes: gid102524,public X-Google-Thread: 1130d6,cb2f33b9a8d8dd55 X-Google-Attributes: gid1130d6,public X-Google-Thread: 109d8a,cb2f33b9a8d8dd55 X-Google-Attributes: gid109d8a,public X-Google-Thread: fc333,cb2f33b9a8d8dd55 X-Google-Attributes: gidfc333,public From: "Androcles" <androcles@home.com> Subject: Re: Rubik's tour. Date: 2000/01/23 Message-ID: <4pGi4.5458$j63.656468@news1.rdc2.pa.home.com> X-Deja-AN: 576551386 References: <387DD6C1.24CC@ameritech.net> <xuMh4.3648$j63.455581@news1.rdc2.pa.home.com> <3887BFD4.116B@ameritech.net> <NMSh4.3936$j63.485453@news1.rdc2.pa.home.com> <38884C17.50BD@ameritech.net> <M66i4.4432$j63.528634@news1.rdc2.pa.home.com> <388AF552.61B0@ameritech.net> X-Priority: 3 Content-Type: multipart/alternative; boundary="----=_NextPart_000_0012_01BF6599.5A05E280" X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2014.211 X-Complaints-To: abuse@home.net X-Trace: news1.rdc2.pa.home.com 948646592 24.1.46.246 (Sun, 23 Jan 2000 08:56:32 PST) Organization: @Home Network X-MSMail-Priority: Normal MIME-Version: 1.0 Reply-To: "Androcles" <androcles@home.com> NNTP-Posting-Date: Sun, 23 Jan 2000 08:56:32 PST Newsgroups: rec.puzzles,alt.math,sci.math,alt.math.recreational,alt.brain.teasers,misc.writing,cz.soc.mensa