Message #570

From: Roice Nelson <roice3@gmail.com>
Subject: A Hyperminx solution approach (was [MC4D] Thibaut Kirchner)
Date: Wed, 17 Sep 2008 21:03:53 -0500

Hi Thibaut,

Welcome! There are a lot of topics floating around (thanks for the parity
writeup by the way), but here I’m only replying about your desire to tame
Magic120Cell, which we’ve also been calling Hyperminx. I just uploaded a
single line code change to the Hyperminx program which I think could greatly
help anyone attempting a full solution. The change is that when you switch
puzzle types, e.g. from a 2-color puzzle to a 12-color puzzle, the internal
state of the puzzle won’t reset. I am copying an email below that I sent to
Nelson a few months ago describing the motivation for this. I still haven’t
quantified the benefit I perceive would come from this approach, but it
hopefully might turn a "taking years" solution into a "taking months" one…

All the best,
Roice

———- Forwarded message ———-
From: Roice Nelson <roice@gravitation3d.com>
Date: Jun 2, 2008 8:16 PM
Subject: Re: One more suggestion
To: Nelson Garcia <spel_werdz_rite@hotmail.com>

Hey Nelson,

So in short, my thought was to take advantage of solving one of the simpler
puzzles first as a path towards solving the full puzzle. This would have 2
big advantages. The first is that for the majority of the solution, one
would work with a smaller number of colors. The second (less obvious but
possibly more dramatic) is that the number of moves to do a full solution
would decrease, and here is a little more explanation on that…

In computer science, a classic problem is sorting an array of numbers, and
there are slower and faster ways to do it. If you have 8 items in a list,
it doesn’t matter so much how you sort because the cost difference, although
there, won’t balloon to extreme proportions. But when you have 15x as many
items in the list (120), the way you sort becomes more important (often the
slowness of an approach doesn’t scale linearly, so instead of being 15x
slower, it might be 225x slower). There is something called "quick sort",
which (roughly speaking) doesn’t sort items in a list one by one, but first
moves items into the general area they will ultimately go, and later makes
further passes to complete the sorting in the smaller areas. What I’m
describing as a suggested approach isn’t really a quicksort, but is loosely
based on the idea of moving pieces to an area, then working on the smaller
areas later.

I should point out I don’t think it would be necessary to fully solve the
smaller puzzle. It could be a waste of time to worry about orientations at
that stage, and so maybe better to focus only on positions since the pieces
will have to be moved around again later. On the other hand, orienting them
early on could make later work easier. I’m not sure what I would do on that
yet.

I think the rings or 4-cube cells puzzles might be best suited as the puzzle
to solve first, because unlike the layers puzzle, the different sets are
more similar. The tori puzzle might be a bad choice because it is only
breaking the world up into 2 big areas, but maybe the gains would still be
as big - I’m not sure. The antipodal puzzle is truly a bad choice though
because the sets of similarly colored cells are not connected.

You could also choose to do it in 3 steps. You could do the tori puzzle,
then switch to the rings or 4-cube cells puzzle, then finally switch to the
full puzzle. Note that after the first step of moving pieces into the
correct areas of the tori puzzle, you have only really actively moved half
of the puzzle pieces, yet the other half are in their area now as well. In
effect, you have obtained a lot of work for free!

Now, when you switch puzzles in the program, it currently resets the puzzle
(maybe this should change), so you can’t do what I’m describing with the
UI. But you can edit the integer representing the puzzle type in the log
file at any point and it would work. Even on the simpler puzzles, the
internal state representation still contains the full 120 colors on all the
cells. I intentionally made that the case, knowing this meant log files
that have solved one of the easier puzzles still won’t look very pristine.

That’s it. I could analyze the benefits further (actually try to estimate
what the differences in moves required might be), but these are my loose
thoughts on it so far, and I have the feeling that the benefits in
time-complexity of solution are definitely worth it.

Roice

On 9/16/08, thibaut.kirchner <thibaut.kirchner@yahoo.fr> wrote:
>
> Hello to all of you.
> I’m Thibaut Kirchner, nearly 21 years old, and live near Paris, France.
> I’m student in maths and computer science (fifth year after in
> superior). Since a few days, I’m the 84th person having solved a 3^4
> hypercube (actually, I’ve solved two of them).
>
> I’m interested in solving puzzles which look like the traditional 3^3
> cube since March, when a friend of mine taught me to solve the 3^3 and
> the Pyraminx (at the French Open 2008).
> Then I found how to solve the Megaminx, and then the 4^3 and 5^3 cubes
> (parity errors were the more difficult).
> I’ve been to some WCA competitions, but, if I like solving faster and
> faster the same puzzles, what I really enjoy is to find methods and
> algorithms to solve new puzzles. When I discovered Gelatinbrain
> (http://users.skynet.be/gelatinbrain/Applets/Magic%20Polyhedra/) and
> rediscovered the 3^4 hypercube (another friend of mine, Ilia Smilga,
> solved it a few years ago, and I had heard of it), I decided to solve
> as much puzzles from there as possible.
>
> Now, I’m working at solving the 4^4 Hypercube and the Magic 120-Cell.
> I believe I have a complete method to do them, the only thing I need
> to complete the solution is some time, since it takes me a few minutes
> to find some piece in this maelstrom of colors.
> I expect to come with a full solution of the 4^4 in a few months, and
> as for the Magic 120-Cell… It won’t be sooner than in a few years,
> since it is really an enormous puzzle.
>
> I’m looking forward to speaking about methods to solve the 3^4
> hypercube, but before, I have some questions:
> - I read that we don’t have a complete proof for the number of states
> of the Magic 120-Cell (would you mind if I call it Hyper-megaminx?
> Sounds better to me), because we don’t have enough formulas to orient
> all the pieces as we conjecture we can. Is it still true today? What
> cases remain to be treated? To solve the 3^4 hypercube, I found (or
> rather adapted from the 3^3 cube) and used a few formulas to orient
> different pieces, and I’m almost sure (and absolutely sure for the
> 4-stickered and 3-stickered pieces) they can be adapted for the
> Hyper-megaminx.
> - Can someone do a program to manipulate a Hyper-pyraminx (based on
> the 4D-simplex as the Pyraminx is based on the 3D-simplex), or
> Super-hypercubes (as hypercubes but center pieces are somehow oriented)?
>
> Thibaut.
>
> PS: Thank you for your invitation here.
>
>
>