13,657,852 moves to solve a cube?!

[IAssemble]

You may have already seen the LEGO MultiCuber robots solving physical cubes from 2x2x2 thru 7x7x7.

However, the algorithm developed for this series of robots was designed to be able solve arbitrary size cube limited only by memory and time.

The algorithm generates solutions consisting of turns of blocks of consecutive layers inwards from one of the faces (rather than, for example, single layer slices) to match the mechanical capabilities of the MultiCuber robots.

Here is a video of the program written to develop and test the algorithm showing a scramble and solve of a 1001 x 1001 x 1001 virtual cube in 13,657,852 turns, averaging a little over 2 turns per piece.

I'll leave you to calculate the effective tps for the graphical rendering (which is somewhat "less than optimal")

Enjoy

P.S. anyone care to try a reconstruction if I provide the scramble? LOL

 

[Kirjava]

saw this yesterday

I like how the solution is pre determined before solving, the visualisation takes way longer than finding it.

Same method as multicuber?

 

[ryanj92]

~16 hours 5 minutes execution time. xD
13,657,852 turns in 57900 seconds = 235.9tps??

EDIT: I love how as you watch it, the unsolved centres slowly change colour as certain centre colours are removed from them

 

[IAssemble]

~16 hours 5 minutes execution time. xD
13,657,852 turns in 57900 seconds = 235.9tps??

EDIT: I love how as you watch it, the unsolved centres slowly change colour as certain centre colours are removed from them

Yes, that's probably about the average tps for the entire solve but only some of the turns are actually rendered to save time... can you work out from the clock in the background during the rendering roughly what the tps is for the rendered sections?

EDIT: yes, I agree that it is interesting to see the unsolved centres change color

 

[IAssemble]

saw this yesterday

I like how the solution is pre determined before solving, the visualisation takes way longer than finding it.

Same method as multicuber?

Thanks.

Yes, it is the method I use now on the MultiCuber robots.

However, it is slightly different from the algorithm I originally developed which is shown in the videos. The original version solved each face in concentric square rings in the same way, but the overall face order was D, F, R, L, U+B and the edges and corners were interleaved between some of the faces rather than being done at the end.

Both algorithms are O(N^2) but this later version averages about 20% fewer moves.

 

[ryanj92]

Yes, that's probably about the average tps for the entire solve but only some of the turns are actually rendered to save time... can you work out from the clock in the background during the rendering roughly what the tps is for the rendered sections?

EDIT: yes, I agree that it is interesting to see the unsolved centres change color

From the first section, ~0.2 tps... xD (from 11:38-11:50, just over 150 turns...)

 

[IAssemble]

From the first section, ~0.2 tps... xD (from 11:38-11:50, just over 150 turns...)

That sounds about right! I wrote a very crude display routine using OpenGL that draws each square tile as two triangles. Since there about 6 million squares, the CPU time a limiting factor.

It renders five frames for each turn at a rate of about one frame per second. As I said above, somewhat "less than optimal" xD

The screen was recorded in time-lapse at a rate of about one frame every four seconds.

 

[qqwref]

EDIT: I love how as you watch it, the unsolved centres slowly change colour as certain centre colours are removed from them

Yup, this is always cool to see. It actually happens with human bigcube solves too, although the pieces are bigger so it's not quite as obvious.

IAssemble: it's interesting that you chose to solve it in concentric squares. I have tried something similar with real cubes and I still find solving in rows both easier and faster. Do you think a computer would also be able to save time/moves this way or are you confident that the concentric squares method results in fewer moves?

 

[IAssemble]

Yup, this is always cool to see. It actually happens with human bigcube solves too, although the pieces are bigger so it's not quite as obvious.

IAssemble: it's interesting that you chose to solve it in concentric squares. I have tried something similar with real cubes and I still find solving in rows both easier and faster. Do you think a computer would also be able to save time/moves this way or are you confident that the concentric squares method results in fewer moves?

Thanks for an interesting question.

I chose to solve in concentric squares as this seemed to be an obvious way to describe an iterative solution for any size cube where pieces are solved directly into place (while using the block turn moves that MultiCuber mechanism can perform efficiently). The "solved directly into place" rather than a two-stage approach of building a row and the putting the row into place makes it straightforward to express with a direct table look-up based algorithm.

I also personally solve the larger cubes in rows. I believe that this method can be done largely "intuitively" which probably makes it relatively efficient without the need to memorize a large number of sequences. And as a human, I can perform slice turns fairly efficiently.

The algorithm averages just over 2 moves per piece for larger cubes which is significantly better than when I solve cubes of the same size. However, I do not claim to be very efficient and I suspect that most of you can solve them in far fewer moves than me

I am not sure whether a good software implementation of a row-based approach would be fewer moves than the concentric ring approach. My gut feel is that a simple implementation that added a piece at a time to a row would be less efficient in block turn metrics but using slice turns might be better. Also, I can imagine a method that could be implemented as a software algorithm which builds multiple rows at a time or adds multiple pieces at a time to a single row that could be more efficient.

I'll add it to my list of "fun things to do" and maybe experiment one day... xD

 

[Ickathu]

Whoa. It was cool watching it solve because of what ryan said - the colors just change ever so slightly as pieces are filtered out

 

[Christopher Mowla]

Only 1000 times as many moves as what god's number probably is for the 1001^3. We gotta start somewhere.

But seriously, this is very interesting. Great job!

 

[MWilson]

Wow a 1001speedBLD? Robots are crazyyy

 

[IAssemble]

Only 1000 times as many moves as what god's number probably is for the 1001^3. We gotta start somewhere.

But seriously, this is very interesting. Great job!

So God's number for 3x3x3 is known to be 20. For 4x4x4 I recall reading about a lower bound of something like 40 and an upper bound of about 57? Is there any research that suggests what it might be for the larger cubes? I guess 13M is *far* higher than the number for the 1001^3 but I would be surprised if it was as low as 13,000

But seriously, thanks.

 

[IAssemble]

So God's number for 3x3x3 is known to be 20. For 4x4x4 I recall reading about a lower bound of something like 40 and an upper bound of about 57? Is there any research that suggests what it might be for the larger cubes? I guess 13M is *far* higher than the number for the 1001^3 but I would be surprised if it was as low as 13,000

But seriously, thanks.

In case anyone is interested, I have just done a quick analysis of this algorithm...

The worst case combination of sequence lengths in the look-up tables used for a 1001 x 1001 x 1001 cube for the following groups of pieces is:

1) a group of 24 centre pieces is 77 moves and there are 5,988,000 centre pieces. This is 19,211,500 moves worst case
2) the group of 12 middle edge pieces is 40 moves
3) a group of 24 edge pieces is 95 moves and there are 11,976 of these (non-middle) edge pieces. This is 47,405 moves worst case
4) the group of 8 corner pieces is 39 (actually this is the worst case in these tables for an even-sized cube which can include corner parity error so this is pessimistic). This is 39 moves worst case

This gives a (probably very weak) upper bound for God's number for a 1001 x 1001 x 1001 cube of 19,211,500 + 40 + 47,405 + 39 = 19,258,984 turns (in "half face block turn"? metrics)

Anyone care to work out a lower bound?

 

[qqwref]

Here's a very weak lower bound:
- 1001x1001x1001 has 10^(3881996.03199904256783330607599619769343079132027152484787...) positions
- With IAssemble's multislice turns there are 3000 different turns (not counting rotations or turns that do nothing) with 3 possible amounts each
- Let's assume that a move sequence can consist of any sequence of these 3000 turns which doesn't use the same one twice in a row, and that any turn can have any possible amount. So the number of possible n-move sequences is 10^(log(9000) + (n-1)log(8997)).
- n=981766 is the first value for which there are at least as many n-move sequences as positions on the cube. So God's number for the 1001x1001x1001 cube must be at least 981766.

 

[IAssemble]

Here's a very weak lower bound:
- 1001x1001x1001 has 10^(3881996.03199904256783330607599619769343079132027152484787...) positions
- With IAssemble's multislice turns there are 3000 different turns (not counting rotations or turns that do nothing) with 3 possible amounts each
- Let's assume that a move sequence can consist of any sequence of these 3000 turns which doesn't use the same one twice in a row, and that any turn can have any possible amount. So the number of possible n-move sequences is 10^(log(9000) + (n-1)log(8997)).
- n=981766 is the first value for which there are at least as many n-move sequences as positions on the cube. So God's number for the 1001x1001x1001 cube must be at least 981766.

Great!

So 13,000 was much too low as I suspected

Thanks.