Discussions on the mathematics of the cube

Future URL recommendation for the forum

Submitted by cubex on Tue, 05/08/2018 - 14:21.
Hello everybody :)

In the future I think it would be a good idea if we all used URLs of the form:

http://forum.cubeman.org/?q=node/view/563#comment

rather than

http://cubezzz.dyndns.org/?q=node/view/563#comment

dyndns.org has raised their prices every year and I'm considering
dropping their service. Unfortunately if we do that a lot of old URLs will stop
working, so I'm open to any clever ideas on what is the best way to deal with
this problem. I'm committed to keeping the maxhost.org and
cubeman.org domain names working for the long term, but
I'm very unhappy with dyndns.
» login or register to post comments | read more

Three Million Positions in Four Metrics

Submitted by rokicki on Mon, 04/23/2018 - 10:52.
I optimally solved three million positions in four distinct metrics.
These positions are distinct from the three million positions I ran
some years back. Random numbers were generated with the Mersenne
Twister algorithm. The four metrics I ran were quarter-turn metric,
half-turn metric, slice-turn metric, and axial-turn metric (equivalent
to the robot-turn or simultaneous-turn metric on the 3x3 cube).

The generators for each metric are strict super- or sub-sets of the
generators for the other metrics. The quarter-turn metric has 12
generators, the half-turn metric has 18 generators, the slice-turn
» 7 comments | read more

Presentation for the Mathieu Group M24 from dedge superflip

Submitted by Paul Timmons on Fri, 04/20/2018 - 20:58.
Following on from a highly symmetric presentation I supplied for the miniature Rubiks cube group Presentation for the 2x2x2 Rubiks cube group I investigated whether the Mathieu Group M24 could be similarily presented taking full advantage of the plentiful symmetry inherent in the Rubiks Revenge cube (4x4x4). The answer was indeed yes - here is the presentation I found - again on three involutions:

< a,b,c | a2 = b2 = c2 = 1,

   (ab)6 = [(bc)6] = [(ca)6] = 1,

   bacabacacabacababacabac = 1,

   (ababacbc)3 = 1,

   bababcbcbcbabab = cacabacacabacac >

» 4 comments

Gear cube extreme can be solved in 25 moves

Submitted by Ben Whitmore on Thu, 02/15/2018 - 23:07.
Write the puzzle as the group <R,F,U,D> where R and F are 180 degree moves. We use a two-phase algorithm to first reduce the state of the puzzle to the subgroup <R3,F3,U,D>, and then finish the solve in the second phase. The subgroup <R3,F3,U,D> is the group of all positions where all of the gears are oriented, because R3 is the same as R' except the gear orientation remains unchanged.

The first phase is easy to compute. There are only 3^8 = 6561 positions because each gear has only 3 different orientations, despite having 6 teeth.

Phase 1 distribution: 
Depth	New	Total
0	1	1
1	4	5
2	8	13
3	78	91
4	102	193
5	1064	1257
6	920	2177
7	3576	5753
8	592	6345
9	216	6561
10	0	6561
The second phase is harder. The number of positions is 24*8!^2/2 = 19,508,428,800, since it turns out that the permutation of the 3 unfixed edges on the E slice is completely determined by the permutation of the centres. This phase was solved with a BFS and took around 7 and a half hours to complete.
» login or register to post comments | read more

Kilominx can be solved in 34 moves

Submitted by Ben Whitmore on Sun, 02/11/2018 - 12:58.
Last night, I found this thread on the speedsolving forums which proves an upper bound of 46 moves. First, the puzzle is separated into two halves, which takes at most 6 moves. Each half is then solved in at most 20 moves (= 7 moves for orientation + 13 moves for permutation, after orientation is solved), for a total of 6+2*(7+13) = 46. xyzzy writes 
The ⟨U,R,F⟩ subgroup, while much smaller than G_0, is still pretty large, having 36 billion states. It's small enough that a
full breadth-first search can be done if symmetry+antisymmetry reduction is used, but I will leave this for another time.
» 3 comments | read more

5x5 sliding puzzle can be solved in 205 moves

Submitted by Ben Whitmore on Fri, 01/26/2018 - 17:46.
Consider a 5x5 sliding puzzle with the solved state 
 1  2  3  4  5
 6  7  8  9 10
11 12 13 14 15
16 17 18 19 20
21 22 23 24
We can solve the puzzle in three steps. First solve 1,2,3,4,5,6,7, then solve 8,9,10,11,12,16,17,21,22, and finally solve the 8 puzzle in the bottom right corner. Step 1 requires 91 moves: 
depth   new             total
0       18              18
1       6               24
2       13              37
3       27              64
4       54              118
5       117             235
6       231             466
7       443             909
» 1 comment | read more

God's algorithm for the <2R, U> subset of the 4x4 cube

Submitted by Ben Whitmore on Wed, 01/24/2018 - 22:00.
Here I'm using sign notation, so 2R is the inner slice only. There are 10 edges, 10 centres in sets of 2, 2, 2 and 4, and 4 permutations of the corner pieces for a total of 4*10!*10!/(2!2!2!4!) = 274,337,280,000 positions. From July 4th 2017 to July 6th 2017, I ran a complete breadth first search of this puzzle in around 60 hours. God's number is 28. 
Depth   New            Total
0       1              1
1       6              7
2       18             25
3       54             79
4       162            241
5       486            727
6       1457           2184
7       4360           6544
» login or register to post comments | read more

Do we have a 3x3x3 optimal solver for stm metric?

Submitted by cubex on Thu, 08/10/2017 - 06:46.
I thought it might be interesting to run an optimal solver using the slice turn metric (including face turns) on some pretty patterns. I don't remember anyone releasing an optimal solver that uses stm but maybe there is one by now?

Also is it true we don't know if using slice turns plus face turns could reduce God's Number from 20 to less than 20?
» 3 comments

More details about my new program

Submitted by Jerry Bryan on Thu, 06/08/2017 - 14:55.

Introduction

On 02/23/2016, I posted a message about a new program I had developed that had succeeded in enumerating the complete search space for the edges only group. It was not a new result because Tom Rokicki had solved the same problem back in 2004, but it was important to me because the problem served as a testbed for some new ideas I was developing to attack the problem of the full cube. I am now in the process of adapting the new program to include both edges and corners. In this message, I will include some additional detail about my new program that was not included in the first message.

» 4 comments | read more

Pattern databases for the 5x5 sliding puzzle

Submitted by stannic on Sun, 04/02/2017 - 11:37.

In 2002, Korf and Felner [1] used pattern databases to solve optimally 50 random instances of the 5x5 sliding puzzle. They used a static 6+6+6+6 partition of tiles (described below), along with its reflection in the main diagonal. In a 2004 paper by Felner, Korf and Hanan [2], the authors describe in a footnote the way they handled the empty tile as 'not trivial'; the empty tile was taken into account when precomputing the database, but then the tables were compressed by discarding the information about the empty location. The authors do not provide the distribution of values from the pattern databases, but do provide maximum values and the number of nodes generated when solving random instances of the 5x5 sliding puzzle.

» 3 comments | read more