Discussions on the mathematics of the cube

Sliding tile puzzle suboptimal solver

Submitted by stannic on Mon, 09/24/2012 - 08:07.
Hello all.
I wrote a program capable to solve (MxN-1) sliding tile puzzles, such as the Fifteen puzzle. The program can solve puzzles from 2x2 to 11x11.
The main thread is on Speedsolving.com:
http://www.speedsolving.com/forum/showthread.php?38689-kumi-na-tano-3-00-sliding-tile-puzzle-suboptimal-solver
- Bulat
» login or register to post comments

Policy Change for New Accounts

Submitted by cubex on Fri, 06/29/2012 - 03:50.
Due to the constant spamming I have changed the access rules for new accounts. From now on new users must email cubexyz at gmail dot com and explain why they want an account here. A short note on your specific interests on Rubik's Cube and math should be sufficient.

Also the ban on gmail has been lifted. Sorry for the trouble, but deleting spam entries got tiresome.

Mark
» cubex's blog | login or register to post comments

Megaminx needs at least 45 moves

Submitted by Herbert Kociemba on Tue, 02/28/2012 - 17:56.
Surprisingly, nobody seems to have done anything else as a rough analysis of the number of moves to solve the Megaminx puzzle, especially no analysis which includes the commutativity of some moves.
» 3 comments | read more

A Hamiltonian circuit for Rubik's Cube!

Submitted by Bruce Norskog on Mon, 02/20/2012 - 21:30.

I have found a Hamiltonian circuit for the quarter-turn metric Cayley graph of Rubik's Cube! In fact, it only uses turns of five of the six outer layers of the cube.

In more basic terms, this is a sequence of quarter moves that would (in theory) put a Rubik's cube through all of its 43,252,003,274,489,856,000 positions without repeating any of them, and then one more move restores the cube to the starting position. Note that if we have any legally scrambled Rubik's Cube position as the starting point, then applying the sequence would result in the cube being solved at some point within the sequence.

» 5 comments | read more

Regularities in maximum WD values

Submitted by stannic on Sat, 01/14/2012 - 15:26.
Regularities in maximum WD values

This post is about any mathematical laws inside the Walking Distance heuristic. It seems like WD is not just puzzle to be computed. Maybe the whole WD heuristic is some math structure.

» 6 comments | read more

A Hamiltonian Circuit for the 2x2x2

Submitted by Bruce Norskog on Mon, 12/26/2011 - 13:33.

I have found a Hamiltonian circuit for the 2x2x2 cube group (3674160 elements). I have posted the solution on the speedsolving.com forum. Link: http://www.speedsolving.com/forum/showthread.php?34318

» 1 comment

Number of canonical move sequences for nxnxn Rubik's cube in q-w metric

Submitted by kociemba on Mon, 12/26/2011 - 12:22.
Quarter turn metric is more difficult to handle than h-w metric, because the 180 degree turn has to be counted as two moves, which gives some issues with an recursive approach. I did not believe it was possible to get a simple formula here. I was very surprised, that the result was a simple generating function for the number of canonical sequences in q-w-metric. It is

gfq[n_,x_]:=3/(6-4(x+1)^(2(n-1)))-1/2

and looks very similar to the generating function in h-w metric which is

gfh[n_,x_]:= 3/(6-4(3x+1)^(n-1))-1/2

» 3 comments | read more

Number of canonical move sequences for nxnxn Rubik's cube in h-w metric

Submitted by kociemba on Sun, 11/20/2011 - 17:22.
In h-w metric, a move of the nxnxn cube is a 90 or 180 degree turn of a face together with 0..n-2 adjacent slices. When counting the canonical move sequences the commutativity of the moves on one axis has to be taken into account. The number of canonical move sequences can be computed quite elegantly using matrices

» 6 comments | read more

Interchanging two faces

Submitted by brac37 on Fri, 11/11/2011 - 12:24.
Hello all,

Just a question for fun. Suppose you have a Rubiks cube and you want to interchange two faces? How many stickers need to be moved?

Distinguish between opposite and adjacent faces and between using a screwdriver (for disassembling) or not, so you get four answers.

Next, do not read any further before adding those four answers to obtain a single answer.

» 1 comment | read more

Some 3-color cube results

Submitted by Bruce Norskog on Wed, 11/02/2011 - 22:57.

The Rubik's Cube can be simplified by using only 3 colors instead of the usual six colors. Generally, opposite faces would share the same color, and that is the convention I assume here in talking about a 3-color cube.

Kunkle/Cooperman showed that a scrambled cube can always be brought to a position within the squares group within 16 moves. This puts an upper bound for God's number for the 3-color cube at 16. It is also well-known that the cube can be put into the <U,D,L2,R2,F2,B2> group in 12 moves. That puts a lower bound on God's number for the 3-color cube at 12. The superflip equivalent for the 3-color cube requires 14 moves according to an optimal 3-color cube solver program I have written. (From solving a million random positions, it appears that about 1.4% of positions of the 3-color cube require 14 moves to solve.) This raises the lower bound for the 3-color cube to 14.

» 17 comments | read more