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

>

>

>