Loading ...
Sorry, an error occurred while loading the content.
 

Re: devil's algorithm

Expand Messages
  • Stefan Pochmann
    Ok, thanks a lot. Very very nice! Actually I ve once done something quite similar a while ago, so I should ve had that idea, too :-) Damn. .. You ve built it
    Message 1 of 46 , Jan 5, 2005
      Ok, thanks a lot. Very very nice! Actually I've once done something
      quite similar a while ago, so I should've had that idea, too :-) Damn.
      ..

      You've built it bottom-up... I think it's also a nice idea to look at
      it top-down. The algorithm first "chooses" a certain corner to place
      at some spot by cycling all corners through that spot. For each choice
      made, it chooses the next corner to place at the next spot. And so on.
      Same with edges (for each choice of all corners, choose all edges).
      And then deeper inside (or "later") "choose" the orientations of all
      pieces, one by one.

      Hmm, do you remember that the cube group can be generated by just two
      different algorithms? I.e. two algorithms that you combine a lot to
      get to any state you want. I'm not sure I have an idea for a much
      shorter Devil's algorithm than yours, but maybe for one that can be
      described shorter. Based on those two algs.

      I don't remember the exact two algs, but I think the idea was this: Do
      you know these sushi restaurants where lots of plates with some sushi
      run around in a long chain and people pick out what they want? Now
      imagine you're the only one sitting next to that cycle of plates and
      you already hold one in your hand. The plates are running around all
      the time and from time to time you pick one out and replace it with
      the one in your hand. This way you can easily create any order you
      want, it just may take a while. The two algs work just like that, but
      you have one cycle on your left with seven corners and one cycle on
      your right with eleven edges. And you hold one corner in your left
      hand and one edge in your right hand. Both cycles cycle with the same
      speed, and whenever you want, you replace both the corner and the edge
      currently next to you in the cycles with those in your hands. One of
      the two algs does the cycles (i.e. cycles seven corners and eleven
      edges). The other alg does the swaps, i.e. swaps the left out corner
      with a certain corner position in the cycle and same for edges. For
      example, this second alg could just be the T-permutation swapping (UL,
      UR) and (URF,UBR) and the first alg could cycle all corners but URF
      and all edges but UR.

      Why should this work? Let's talk about permutation only. It should be
      clear from the sushi example that you can get any order when you're
      just dealing with one cycle. But with the two cycles we can "simulate"
      that they move independently, even though they're not. Consider
      cycling both by one position, but do it 22 times. That will not change
      the edges (just cycle them completely two times) but it will cycle the
      corners completely three times and one more position. To cycle the
      edges one position forwards, move both cycles 56 forwards. Why does it
      work, why can we move them independently? Because 7 and 11 are
      relatively prime.

      How about orientation? This is actually not covered yet. We need to
      modify the above construction. The algorithm that moves the cycles one
      step forward must also do some orientation. For the edges, imagine
      that they don't cycle on a "normal" strip, but on a Moebius strip
      (http://mathworld.wolfram.com/MoebiusStrip.html). That is, the cycle
      is not a normal 11-cycle, but at some point it twists 180 degrees. So
      after 11 iterations, the edges are in the original position but all
      flipped. After 22 iterations they're the same. For this to work we
      also need to flip the edge in your hand, though, i.e. the one at UR.
      For corners, we do the same, but we "open" the cycle somewhere to
      include a clockwise twist and twist the corner in our hand (i.e. at
      URF) counterclockwise.

      The claim is that everything can be done independently:
      1) Move edge cycle one forward without flipping edges, and leave
      corners completely intact.
      2) Move corner cycle one forward.
      3) Flip all edges.
      4) Twist all corners.

      This is how that's done:
      3) Apply the alg 11*7*3 = 231 times. Thanks to factor 11, the edges
      will stay at their place. Thanks to 7, corners will stay. Thanks to 3,
      corners won't be twisted. Since 231 is odd, edges will be flipped.
      4) Apply it 11*7*2 = 154 times.
      1) Apply it 7*3*10 = 210 times. Thanks to 7*3, corners won't be
      changed. Since 210 is even, edges won't be flipped. Since 210=19*11+1,
      the edges will make 19 complete cycles plus one more step forwards.
      2) Apply it 11*2*15 = 330 times. Since 330=47*7+1, corners will make
      47 complete cycles plus one more step.

      And why does it work? Why is it all independent? Because 11, 7, 2 and
      3 are all relatively prime.

      Ok, I think I'd better stop for a moment and continue with the
      original idea of using this for the Devil's algorithm in another post.
      ..

      Cheers!
      Stefan


      --- In speedsolvingrubikscube@yahoogroups.com, "Eivind Fonn"
      <htkra1d@h...> wrote:
      >
      > *Sigh*, always the assumptions ruin my hour of triumph! :)
      >
      > CO stands for Corner Orientation. COC1 twists UFR clockwise and UBR
      > counterclockwise. COC2 does the same, but with UFL instead of UFR.
      The
      > idea is the same with COCs 2 to 7. They all twist one corner
      clockwise
      > and UBR counterclockwise. By applying COC1 three times (which is
      > COT1), we can iterate through the three possible orientations for
      the
      > first corner. By applying COC2 three times, with COT1 inbetween each
      > time, we iterate through all possible orientations for the first two
      > corners. And so on... up to seven. The last corner we can ignore
      since
      > its orientation is decided by the others. So, COT7, which I have
      > called CO, will cycle through all possible orientations of all the
      > corners.
      >
      > The idea is similar with the EO algorithms, except that in EOT1, CO
      is
      > called. This means that EOT11 (which by now is getting freakishly
      > long, and I have called simply "O") cycles through all possible
      > orientations of all the pieces. So now, we only need to cycle
      through
      > all permutations, and apply O once for each of them.
      >
      > The EP algorithms does that with the edges. EP (EPT12) is a 12 cycle
      > of edges (EPC12) done 12 times with EPT11 done once inbetween each.
      > EPT11 is an 11-cycle (EPC11) done 11 times with EPT10 done once
      > inbetween each... and so on. At the lowest level (EPT2), O is
      invoked.
      > For each even cycle, two corners are also swapped, but they're the
      > same two corners all the time. The edge that is left untouched by
      the
      > 11-cycle is also left untouched by all the others, etc. (This is
      > important, I reckon.)
      >
      > Now, EP is then an algorithm which, given a cube with correct corner
      > permutation, will eventually produce the solved cube. The CP
      > algorithms work excactly the same as the EP ones. At the lowest CP
      > level (CPT2), EP is invoked.
      >
      > So.. there you go. I think it should work.
      >
      > --- In speedsolvingrubikscube@yahoogroups.com, h_howee <no_reply@y..
      .>
      > wrote:
      > >
      > > how about god's algorithms?
      > > is there a site where i can find them?
      >
      > Honor and glory is up for grabs for whoever can find God's algorithm
      > first, mate!
    • Tyson Mao
      Nice! It s been a while. Nice to see some entertainment again. ... [Non-text portions of this message have been removed]
      Message 46 of 46 , Sep 20, 2011
        Nice! It's been a while. Nice to see some entertainment again.

        On Tue, Sep 20, 2011 at 2:59 AM, Alien <rubiks99ca@...> wrote:

        > **
        >
        >
        > Happy fun cube
        >
        > http://www.youtube.com/watch?v=Zh5miheTXjQ
        >
        > The cuber
        >
        > devil's algorithm
        > does anyone know the devil's algorithm?... h_howee
        > Jan 5, 2005
        > 3:38 am
        > Re: devil's algorithm
        > ... You mean the shortest way to scramble a cube? Or what is it?... Stefan
        > Pochmann
        > stefan_pochmann
        > Jan 5, 2005
        > 5:55 pm
        > Re: devil's algorithm
        > More like the worst way to solve it. Devil's algorithm is an imagined
        > algorithm that, by being applied over and over again, sorts through every
        > single possible... Eivind Fonn
        > betrayedfiber
        > Jan 5, 2005
        > 7:15 pm
        > Re: devil's algorithm
        > How about a devil's algorithm that cycles through every LL situation while
        > leaving the F2L intact. That would most likely be easier to find and
        > possibly... Chris Sz...
        > dishwashersa...
        > Jan 5, 2005
        > 8:50 pm
        > Re: devil's algorithm
        > If you find it, please don't post it here. Assuming it looks random, it'd
        > take a lot of memory: M = 12!*2^12*8!*3^8/12/1260 = 3.43*10^16 That's the
        > minimum... Stefan Pochmann
        > stefan_pochmann
        > Jan 5, 2005
        > 9:35 pm
        > Re: devil's algorithm
        > Oh, before I forget it: 4325 - The number of years to download it with a
        > 1MBit/sec internet connection. So yeah, please don't fucking post it here
        > ;-) Stefan ... Stefan Pochmann
        > stefan_pochmann
        > Jan 5, 2005
        > 9:46 pm
        > Re: devil's algorithm
        > What if I am smart instead? http://www.stud.ntnu.no/~eivindfo/devalg.txtIt's 3,847,762,288,469,010,006,992 moves long, but only 3 KiB large. I bet a
        > 1MBit/sec... Eivind Fonn
        > betrayedfiber
        > Jan 5, 2005
        > 10:58 pm
        > Re: devil's algorithm
        > Yaeh yaeh... ok... remember I was assuming it's random ;-) And hey, where's
        > your proof? Ok, not necessary to prove it perfectly formally, but could
        > you... Stefan Pochmann
        > stefan_pochmann
        > Jan 6, 2005
        > 12:09 am
        > Re: devil's algorithm
        > how about god's algorithms? is there a site where i can find them?...
        > h_howee
        > Jan 6, 2005
        > 12:12 am
        > Re: devil's algorithm
        > *Sigh*, always the assumptions ruin my hour of triumph! :) CO stands for
        > Corner Orientation. COC1 twists UFR clockwise and UBR counterclockwise. COC2
        > does the... Eivind Fonn
        > betrayedfiber
        > Jan 6, 2005
        > 12:30 am
        > Re: devil's algorithm
        > Ok, thanks a lot. Very very nice! Actually I've once done something quite
        > similar a while ago, so I should've had that idea, too :-) Damn. .. You've
        > built it... Stefan Pochmann
        > stefan_pochmann
        > Jan 6, 2005
        > 5:05 am
        > Re: devil's algorithm
        > ... post. ... Ok, I'm too tired for it tonight, but the point is that these
        > two algorithms, cleverly combined over and over again, will be powerful
        > enough to... Stefan Pochmann
        > stefan_pochmann
        > Jan 6, 2005
        > 5:10 am
        > Re: devil's algorithm
        > Ok here's an attempt: Let AC be the cycling alg and AS the swapping alg. My
        > Devil's alg does 3*AC, then AS, then 1*AC, then AS, then 4*AC, then AS, and
        > so on.... Stefan Pochmann
        > stefan_pochmann
        > Jan 6, 2005
        > 5:47 am
        > Re: devil's algorithm
        > I would have thought that the "devil's algorithm" would be the shortest way
        > to cycle through all N positions of the cube, i.e. a move sequence N-1 moves
        > long... _jaap
        > Jan 6, 2005
        > 7:40 am
        > Re: devil's algorithm
        > I wasn't aware that it would have to be the shortest one. That makes the
        > problem a bit more delicate. :P Stefan: Nice... your's a bit more elegant
        > :). The Pi... Eivind Fonn
        > betrayedfiber
        > Jan 6, 2005
        > 10:29 am
        > Re: devil's algorithm
        > ... I really like the idea of an explicit algorithm for this; the problem
        > is distinct from finding a Hamiltonian circuit, though obviously that would
        > solve the... mike_go_uk
        > Jan 6, 2005
        > 12:33 pm
        > Re: devil's algorithm
        > Your depth-first algorithm is this long (worst case scenario):
        > 11,081,777,224,076,574,027,294,514,344,648,207,681,624 moves So I gather
        > mine is _slightly_ more... Eivind Fonn
        > betrayedfiber
        > Jan 6, 2005
        > 12:57 pm
        > Re: devil's algorithm
        > ... True, indeed. Let's not neglect the practicalities ;) Mike...
        > mike_go_uk
        > Jan 6, 2005
        > 1:20 pm
        > Re: devil's algorithm
        > Excactly. :) I wrote a little script for those who really have time on
        > their hands: http://www.stud.ntnu.no/~eivindfo/devalg.php It serves up the
        > moves in... Eivind Fonn
        > betrayedfiber
        > Jan 6, 2005
        > 2:48 pm
        > Re: devil's algorithm
        > ... hands: Thank you! This should be a wonderful resource for anyone new to
        > speedsolving. Please, make sure that it is available for the next 120
        > trillion... mike_go_uk
        > Jan 6, 2005
        > 3:11 pm
        > Re: devil's algorithm
        > Woow! A good candidate for next weeks's FMC ;-) "What is it good for?
        > Absolutely nothing! Say it again ..." -Frankie goes to Hollywood (1984)
        > </Per> ... into ... Per Kristen Fredlund
        > aspiring_to_...
        > Jan 6, 2005
        > 5:39 pm
        > Re: devil's algorithm
        > I love it :-) Though I think in the recursion steps you should do all 18
        > possibilities, not only six. It gave me the idea of using this with my two
        > algs: Let...
        >
        > --- In speedsolvingrubikscube@yahoogroups.com, h_howee <no_reply@...>
        > wrote:
        > >
        > >
        > > does anyone know the devil's algorithm?
        > >
        >
        >
        >


        [Non-text portions of this message have been removed]
      Your message has been successfully submitted and would be delivered to recipients shortly.