Message #571

From: Melinda Green <melinda@superliminal.com>
Subject: A Hyperminx solution approach (was [MC4D] Thibaut Kirchner)
Date: Wed, 17 Sep 2008 19:42:59 -0700

Roice,

You already implemented the show-the-cubie-that-goes-here functionality,
right? In other words, the compliment to the
show-me-where-this-cubie-belongs feature. Without this, I suspect that a
great deal of a potential solver’s time would be spent searching. Even
still I expect it will take months but at least the bulk of the mindless
work can be eliminated.

-melinda

Roice Nelson wrote:
> 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
> <mailto:roice@gravitation3d.com>>
> Date: Jun 2, 2008 8:16 PM
> Subject: Re: One more suggestion
> To: Nelson Garcia <spel_werdz_rite@hotmail.com
> <mailto: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