Message #411

From: Mark Oram <>
Subject: Re: [MC4D] Further musings
Date: Mon, 20 Aug 2007 21:30:06 +0100


Thank-you for your (as always) thought-provoking
comments. To be honest don’t feel I have any handle on
God’s algorithm in 3 (or more) dimensions (I actually
do have for the 2-D ‘cube’, but is this too trivial to
be useful or meaningful?) to answer your first

It is a good way I think to visualise each cubie as
being a certain distance from Start, in a space with
as many dimensions as needed, and then conceive of
moving each piece home by the shortest and most
efficient route. Your analogy with a jig-saw puzzle
makes sense in this light. The key difference seems to
be that moving one jig-saw puzzle piece home along the
shortest route would not in general affect the routes
of any other piece: the intriguing (and infernally
frustrating!) difference with Rubik’s paradigm is that
moving one piece NECESSARILY drags other cubies along
with it - perhaps moving some even further from Start.

So every move of a cubie in a cube (regardless of
which dimensional version) alters the landscape for at
least some of the other cubies, in a (is it fair to
say?) non-deterministic way. If so, it is not possible
then to devise an algorithm to find a given set of
moves that is the most efficient route home for all
the pieces affected. I had fallen into a probably
classic trap by imagining a computer program having
the ability to do just that.

As you pointed out, however, we humans still need to
write the algorithm in the first place. Writing one
with the ability to find, up front, the shortest route
for any given position seems tantamount to finding the
route oneself - so why write the progam at all?
(except, as you allude to, for practical reasons of
speed, infallibility, time saved etc etc) I also
wonder if parrallel computing approaches such as
quantum computing, DNA computing or others might have
some milage here? Any thoughts I have on such matters
are still very nebulous, but I’ll happily discuss them

— Melinda Green <> wrote:

> Mark,
> Do you have a feeling for how god’s algorithm works
> for even the 3D
> cube? I’m not sure that is possible even for the
> 2^3. That’s because I
> view god’s algorithm as a high dimensional problem
> where each cubie
> represents a single dimension that is at some
> distance from where it
> needs to be. I can visualize the shortest path
> between two points in 3
> dimensions but that’s my limit. I don’t think that I
> can even "feel" my
> way to a 3D cube solution. Maybe some of the best
> speed solvers can do
> that. To me that would not mean that they approach
> god’s algorithm but
> that they would abandon any step by step approach
> and place one or two
> cubies at a time based on how quickly each one can
> be moved into place,
> somewhat similar to how people solve jigsaw puzzles.
> Computer solutions really are mostly just human
> solutions and are
> usually much simpler than the sorts of things people
> do. Computers just
> do them quickly and flawlessly. They are definitely
> not constrained by
> our 3-dimensional visualization limitations however.
> Computers are only
> limited by algorithmic complexity. Creating the
> algorithms is the real
> creative part regardless of whether they’re
> performed by humans or
> machines. In my mind Don’s N-dimensional computer
> solution proves that
> he’s solved the N-dimensional cube even if he never
> solves a puzzle by
> hand. An existence proof is still a proof. In other
> words, with enough
> patience, he could follow his own instructions
> without a computer. In
> principal you could do the same thing by creating a
> sufficiently large
> pyramid of macros on top of macros until you could
> take a fully
> scrambled cube, find and click on each cubie in
> order, and sit back and
> let the computer do all the work. I would consider
> your master macro to
> be a solution even though I probably wouldn’t hold a
> speed-solving
> contest that includes macro and non-macro solvers.
> -Melinda
> Mark Oram wrote:
> > I can readily believe that possible interfaces for
> 6
> > (and upward) dimensional simulations would be
> > workable, based on the 4-D paradigm along with the
> > ability to selectively hide different layers/faces
> > etc. Also, I think there is plenty of fun to be
> had
> > with a step by step algorithm; with (in the case
> of
> > the cubes at least) enough intermediate milestones
> > such as one face complete, two faces complete etc
> etc,
> > to provide sufficient motivation (and
> satisfaction!)
> > to keep moving forward.
> >
> > My main fear would be that this step by step
> > ‘orthogonal’ approach (I don’t know how else to
> > describe it) misses a lot of the subtleties and
> > ‘richness’ that the extra dimensions provide. Nor
> does
> > it, I firmly believe, give any real insight into
> how
> > God’s algorithm for each cube might look. Perhaps
> this
> > is where software designed to solve the higher
> > dimensional cubes will have a clear advantage over
> > human visualisation and imagination, in that it is
> not
> > constrained by the 3 dimensions we are familiar
> with.
> >

  &#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95;&#95; <br> Want ideas for reducing your carbon footprint? Visit Yahoo! For Good  http&#58;//