RMP-02: Generalized approach for finding out all the possible combinations of NxN dimensional cubes + some rubik's cube graph theory

Date: 9-26-2017

Original Question: By how many different ways a rubik’s cube can be arranged?

Solution: A rubik’s cube has 8 corners, which can be arranged in 8! different positions,and have 3 possible orientations,which gives 3^8 possibilities.But only ⅓  of them have the correct corner orientation as the original rubik’s cube.

12 edges give you 12! Different positions and 2 possible orientations give you 2^12 possibilities.

½  of them have the correct edge orientation of the rubik’s cube,and only ½ of the possible combinations is achievable because no two pieces can be moved by isolation,so to sum up,

Follow up question,is there any generalized approach for finding out all the possible combinations of NxN dimensional cubes?

Trying to solve this problem analytically I met a lot of hurdles,as the possible different combinations for the cubes of even dimensions were different than the ones of odd dimensions,because of orientational parity of even dimensioned cubes.

And also,adding another layer to the cube increased the subcategories among the pieces.

So I went to more numerical approach and tried to see the pattern of the number of possible permutations increasing as the layers or n increased. (  I didn’t include step-by-step approach of 5x5 or 7x7 cubes but the idea is the same,but there are just increased number of intermediate and outer edges,which always comes in a set of 24)

(I wrote this expressions in google docs,took a screenshot,and then added them to the blog post because it was easier to do so.)

And here I noticed an amazing behaviour,the only changes occur in the exponents of 24!24.

Assuming the exponent of numerator 24! As j and the exponent of the denominator 24 as k, We can make a table from here,

When n=3	J = 0	K =0
5	3	12
7	8	36

The relationship between n and j and n and k can be modeled through this equation below that I got from quadratic regression,

J = 0.25n^2-0.5n-0.75

K = 1.5n^2-6n+4.5

So,a general formula for figuring out all the possible permutations nxn cubes where n is odd would be,

Another Question: If we model a rubik’s cube through graph theory,what kind of graph is it going to be? How many vertices will be there? How many edges would be there? How many degrees would each vertices have?

If we model a rubik’s cube through graph theory, I think the vertices would be all the possible permutations of a rubik’s cube,and the edges between them would be dependent on whether you can get from one configuration to another just through one 90 degree rotation of one face. For example.{  , },if we considered these two as vertices,one 90 degree rotation or a move would determine the edges between them.

The amount of degree of each vertices would be the same,in this case which is 12.

It would be 12 because only 12 moves are allowed in a rubiks cube,which are just clockwise or counter-clockwise 90 degree rotation of  Right,Front,Left,Up,Back,Down Faces.

So the amount of edges in this graph would be (sum of degrees / 2) which is 64.32521019

Summary: I learned that analytical ways to solve a problem might fail sometimes and that’s where simple numeric analysis can make a problem a lot easier. I also had a lot of questions while trying to figure out all the possible permutations which led me to disassemble my 5x5 cube ,and looking at the subcategories of all the edges. This is where the graphical approach to solve a problem came in too. And I am also wondering if cubes can be interpreted in terms of cellular automata,where all the possible combinations in a cube can be modeled using ‘neighborhoods’.  I also learned a bit about dijkstra's algorithm,which can be used to go through all the possible permutations of a cube to determine the shortest path from one vertice to another,which in this case,from scrambled state of the cube to solved state.

Saikanam Siam
Junior
Broooklyn Technical High School