# Solve Rubik Cube Puzzle

, 11 Oct 2010 CPOL
 Rate this:
Brain teaser solve Rubik cube puzzle on system

## Introduction

### What It Is

The Rubik's Cube is a 3-D mechanical puzzle invented in 1974 by Hungarian sculptor and professor of architecture Erno Rubik. Originally called the "Magic Cube", Rubik cube won the German game of year special award for Best Puzzle that year.

In a classic Rubik's Cube, each of the six faces is covered by nine stickers, among six solid colors (traditionally darkblue, red, blue, orange, green, and yellow). A pivot mechanism enables each face to turn independently, thus mixing up the colours. For the puzzle to be solved, each face must be a solid colour.

### What It Does

Solve rubic cube puzzle on computer systems.The image below shows the computer version:

Use directions to turn the cube face independently. Play and win.

### How to Use It

Enjoy .

Note: The next six questions are very basic, one can skip them.

##### Q.What is the learning curve for fellow programmers ? What all technologies/algorithms are used?

One can learn how to cast 3D model on 2D surface (computer screen) accurately using only basic mathematics calculations. Code involves using perspective projection, hidden surface removal algorithms, linqs in .NET 3.5 framework, GDI+, lot of matrix computations.

##### Q.What is coordinate system ?

A method of representing points in a space of given dimensions by coordinates from origin.The image below shows 3 dimensional coordinate system,the axis X, Y, Z are perpendicular to each other. IMP: Z axis is perpendicular to screen.

##### Q.What is a point ?

A Point is a reference to position in 3D world, point is represented by x,y,z coordinate with respect to coordinate system.

##### Q. What are cubes ?

A three-dimensional shape with six square or rectangular sides formed by connecting 8 Points(each point connect to 3 other points) as shown below.

##### Q. What make up a Rubik cube ?

27 carefully placed cubes in 3D world make a larger cube called Rubik cube.

##### Q. What are the coordinates of a simple cube ?

As shown in the image below, the coordinates of a simple cube are in format POINTNUMBER(X,Y,Z)

1(0,1,1) ,2(1,1,1) ,3(1,0,1) ,4(0,0,1) ,5(0,1,0) ,6(1,1,0) ,7(1,0,0) ,8(0,0,0).

##### Q. How to rotate a point in 3d coordinate system around X,Y,Z axis ?

Rotation of a point around z axis, there are three basic steps:

1. Translate to center point around which to rotate, the code below translates point (x1,y1) to center point point.
```double tempy1 = y1 - point.y;

double tempx1 = x1 - point.x;```
2. Rotate around center point, the code below rotates translated point (tempy1,tempx1) around z-axis using angle which is expressed in radians.
```y = tempy1 * Math.Cos(rotationAngle.ZRadianAngle) -

x = tempx1 * Math.Cos(rotationAngle.ZRadianAngle) +
3. Translate back to original points, as done below:
```y1 = y1 + point.y;

x1 = x1 + point.x;```

x1,y1 are final coordinates as a result of rotation around z axis. Slightly modify the above formula to make rotation about x,y axis possible.

##### Q.How to rotate a cube face around Z axis by 90 degrees ?

A Cube face has 9 cubes, meaning 72 points in space. Calculate the center point of face, apply rotation logic on all 72 points.

##### Q What is Camera, Camera Angles, Camera position, Viewer position ?

A camera is eye watching a Rubik cube in 3d space, Camera position is position of camera with respect to coordinate system, camera angles are angles of camera how it is tilted. Viewer position is position of viewer with respect to computer screen. Actually I did another POC understanding all camera related stuff. Here is the link for more information. Camera position, camera angles, viewer position are set carefully to give best shot. The below code shows the camera parameters, be careful when playing around with camera parameters, it can result in distorted rubikcube.

```Point3D cameraPosition = new Point3D(-1, 90, 90, 140);

Angles angles = new Angles(0, 0, 0);

Point3D viewer = new Point3D(-1, 0, 0, 500);
rubikCube.draw(e.Graphics, cameraPosition, angles, viewer);```

## Q. What is the Role of Point3D Class ?

`Point3D `class represents points of coordinate system, store coordinates in x,y,z variables, index in `Point3D `constructor is reference to position in cube (for calculation purpose). See Image 1:

`public Point3D(int index, double Xcoor, double Ycoor, double Zcoor);`

Note: Variable x,y,z in `Point3D `class are initialized and are never changed in any operations, only used as reference for calculations.

##### Q.What operation are performed by Point3d class ?
1. Calculate final location of `Point3D `in 3d space when viewed from camera position, camera angles, store the final coordinates in `Point3D `x1,y1,z1. The image below shows matrix computations.
`public void FullFinalTransformation(Point3D Camera, Angles Angle); `
2. Apply sequence of rotation to `POINT3D `coordinate as a result of user actions, rotate the point around the center point (passed as parameter this is RUBIK CUBE CENTER POINT).
```public void XYXRotation(Angles rotationAngleS, Point3D point, DIRECTION direction,
List<Angles> listRotationangles) ;```
3. This is the most important part "perspective projection". It's all about how a point in 3D space is projected on 2d screen so that there is no deviation from real look and feel. Viewer is position of viewer with respect to screen, calculate the final x,y and return it.

Note: All graphics functions take only X,Y coor as parameter.

`public PointF PerspetiveProjection(Point3D Viewer);`

## Q What is the Role of Cube Class ?

This is where the complexity starts. We know that cube is formed by connecting (carefully placed) 8 points in space, cube stores collection of eight points and is responsible for its drawing, in order to fill something computer graphics need a enclosed region, in case of cube we have 6 enclosed regions called faces. Cube stores collection of points which form a cube face.

• (1,2,3,4) represents face 1,
• (2,6,7,3) represents face 2,
• (5,6,7,8) represents face 3,
• (1,8,6,5) represents face 4,
• (1,5,8,4) represents face 5,
• (8,7,3,4) represents face 6,

Each face has a color associated with it. Cube remembers the sequence of rotations applied on to it as shown in the code below:

```switch (direction)
{
case DIRECTION.XAXIS:
break;
case DIRECTION.YAXIS:
break;
case DIRECTION.ZAXIS:
break;
}```
##### Q What sequence of operation Cube follow while drawing ?
1. Apply `FullFinalTransformation `on 8 points.
2. Apply sequence of rotations(previously stored) and current one(this arises from user action) on 8 points. Add the current rotation in `listRotationangles`.
3. Apply `PerspectiveProjection `on 8 points to project on computer screen.
4. As a result of all previous actions, we have all points in 2d space ready to be drawn on computer screen.
5. Choosing which cube face to draw is most tricky. The most important point to be kept in mind is that at any point while viewing a cube only 3 faces are visible.

Here, the hidden surface removal algorithm fits in.

1. I have to choose three faces.
2. Store 3 top most points whose Z coor in max in world space in collection `lsttop`.
```var sortedDict = (from entry in POINTS
orderby entry.Final.z descending
select entry);
lsttop = new List<int>();
lstbottom = new List<int>();
int i = 0;
foreach (Point3D key in sortedDict)
{
if (i <= 3)
{
}
else
{
}
i++;
}```
3. Find the face which consists of all points in `lsttop`, draw the face.
```var sortedDict1 = (from entry in listpoint
where entry.Value.All(find)
select entry.Key);
foreach (int key in sortedDict1)
{
FinalRegion.Union(new Region(collectionGp[key]));
graphic.FillRegion(new SolidBrush(Colors[key]), FinalRegion);
graphic.DrawPath(new Pen(Colors[key]), collectionGp[key]);```
4. Find the face adjacent to drawn face, which does not intersect with already drawing face, draw them.
```var sortedDict2 = (from entry in listpoint
where entry.Value.Any(findone)
select entry.Key);
Region cloneregion = FinalRegion.Clone();
foreach (int key1 in sortedDict2)
{
FinalRegion = cloneregion.Clone();
Region region = new Region(collectionGp[key1]);
FinalRegion.Intersect(region);
if (FinalRegion.IsEmpty(graphic) == true)
{
graphic.FillRegion(new SolidBrush(Colors[key1]), region);
graphic.DrawPath(new Pen(Colors[key1]), collectionGp[key1]);
}
}```

done with drawing a cube.

## Q What is the Role of Rubik Cube Class?

Rubik cube is responsible for placing 27 cubes in world coordinate system as shown below:

The code below shows how to place 27 cubes in 3d space.

```for (int j = 0; j < 3; j++)
{
for (int k = 0; k < 3; k++)
{
for (int i = 0; i < 3; i++)
{
cubes[i + k * 3 + j * 3 * 3] = new cube(i + k * 3 + j * 3 * 3);
CubesAtposition.Add(i + k * 3 + j * 3 * 3, i + k * 3 + j * 3 * 3);
xplus = 11;
yplus = 11;
zplus = 11;
cubes[i + k * 3 + j * 3 * 3].POINTS[0] = new Point3D(1, offset + i * xplus + i *
xspace, yplus + j * yplus + j * yspace, zplus + k * zplus + k * zspace);
cubes[i + k * 3 + j * 3 * 3].POINTS[1] = new Point3D(2, xplus + i * xplus + i *
xspace, yplus + j * yplus + j * yspace, zplus + k * zplus + k * zspace);
cubes[i + k * 3 + j * 3 * 3].POINTS[2] = new Point3D(3, xplus + i * xplus + i *
xspace, offset + j * yplus + j * yspace, zplus + k * zplus + k * zspace);
cubes[i + k * 3 + j * 3 * 3].POINTS[3] = new Point3D(4, offset + i * xplus + i *
xspace, offset + j * yplus + j * yspace, zplus + k * zplus + k * zspace);
cubes[i + k * 3 + j * 3 * 3].POINTS[4] = new Point3D(5, offset + i * xplus + i *
xspace, yplus + j * yplus + j * yspace, offset + k * zplus + k * zspace);
cubes[i + k * 3 + j * 3 * 3].POINTS[5] = new Point3D(6, xplus + i * xplus + i *
xspace, yplus + j * yplus + j * yspace, offset + k * zplus + k * zspace);
cubes[i + k * 3 + j * 3 * 3].POINTS[6] = new Point3D(7, xplus + i * xplus + i *
xspace, offset + j * yplus + j * yspace, offset + k * zplus + k * zspace);
cubes[i + k * 3 + j * 3 * 3].POINTS[7] = new Point3D(8, offset + i * xplus + i *
xspace, offset + j * yplus + j * yspace, offset + k * zplus + k * zspace);
cubes[i + k * 3 + j * 3 * 3].Colors[0] = Color.Red;
cubes[i + k * 3 + j * 3 * 3].Colors[1] = Color.Blue;
cubes[i + k * 3 + j * 3 * 3].Colors[2] = Color.Yellow;
cubes[i + k * 3 + j * 3 * 3].Colors[3] = Color.Green;
cubes[i + k * 3 + j * 3 * 3].Colors[4] = Color.DarkTurquoise;
cubes[i + k * 3 + j * 3 * 3].Colors[5] = Color.DarkOrange;
}
}
}```

Rubik cube is responsible for rotating cube faces, every face can be rotated, even whole Rubic cube can be rotated on X,Y,Z axis, Rubik cube maintains a mapping between cubeposition and cubenumber, every cube in rubik cube has a cube number associated with it, when a face is rotated, the cubenumber at cubeposition is changed in mapping.

`Dictionary<int, int> CubesAtposition = new Dictionary<int, int>(); `

The most important challenge Rubik cube face is in what order cubes must be drawn so that a perfect picture is possible (no overlapping no distortion). Cubes which are farthest from the camera position are drawn first.

```for (int index = 0; index <= 26; index = index + 1)
{
double distance = 0;
collectionPoint3d[index] = cubes[index].CalculateCentrePointAfterRotate(cameraPosition,
angles, cubes[index].CuberRotationAngles, point3d, cubes[index].dir);
distance = Math.Sqrt((cameraPosition.x - collectionPoint3d[index].x) *
(cameraPosition.x - collectionPoint3d[index].x)
+ (cameraPosition.y - collectionPoint3d[index].y) *
(cameraPosition.y - collectionPoint3d[index].y)
+ (cameraPosition.z - collectionPoint3d[index].z) *
(cameraPosition.z - collectionPoint3d[index].z));
listdistance[index] = distance;
}
var sortedDict2 = (from entry in listdistance
orderby entry.Value descending
select entry.Key);
foreach (int key in sortedDict2)
{
cubes[key].Draw(g, cameraPosition, angles, viewer,
cubes[key].CuberRotationAngles, point3d, cubes[key].dir);
}```

The little piece of code check for game completeness.

```public bool Check()
{
bool bCheck = true;

for (int iPos = 0; iPos < 27; iPos++)
{
if (CubesAtposition[iPos] != iPos)
{
bCheck = false;
break;
}
}
return bCheck;
}```

I am done with the article. Do write to me at Atulloona4@gmail.com for any queries and please do vote.

Thanks!

## Share

India
"It's impossible," said pride. "It's risky," said experience . "It's pointless," said reason "Give it a try." whispered the heart

Another piece of work here are links.

1) http://monk.parseapp.com/index.htm

2) http://picassa.parseapp.com/index.htm

3) http://circles.parseapp.com/

 First Prev Next
 My vote of 5 Prasad Khandekar 20-May-13 22:14
 My vote of 5 kulbhushan18 9-Jan-13 1:51
 My vote of 5 zvweiss 11-Apr-12 15:37
 Good Work... VIPUL2686 22-Oct-10 8:58
 Proud of you...
 My vote of 5 lishaowen 13-Oct-10 18:08
 My vote of 5 Bigdeak 12-Oct-10 23:28
 Re: My vote of 5 ATUL_LOONA 12-Oct-10 23:39
 My vote of 5 Abhinav S 7-Oct-10 8:47
 Re: My vote of 5 ATUL_LOONA 7-Oct-10 9:07
 VOW giridhar 3 5-Oct-10 8:35
 Re: VOW ATUL_LOONA 5-Oct-10 8:45
 Good job! Shane Story 5-Oct-10 4:16
 Re: Good job! ATUL_LOONA 5-Oct-10 5:01
 My vote of 5 Pierfabio 4-Oct-10 23:17
 Re: My vote of 5 ATUL_LOONA 6-Oct-10 2:10
 My Vote of 5 Kelvin Armstrong 4-Oct-10 6:17
 Re: My Vote of 5 ATUL_LOONA 6-Oct-10 2:10
 My vote of 5 aagga6 3-Oct-10 23:24
 My vote of 5 puneet.jain 27-Sep-10 22:19
 My vote of 5 Member 1446517 27-Sep-10 22:01
 Good job now you can try 4x4x4, 5x5x5, 6x6x6 vasil_ek 27-Sep-10 21:50
 Re: Good job now you can try 4x4x4, 5x5x5, 6x6x6 ATUL_LOONA 27-Sep-10 21:54
 My vote of 5 vasil_ek 27-Sep-10 21:46
 My vote of 5 sabijogar 26-Sep-10 23:35
 My vote of 5 atverma 26-Sep-10 21:44
 My vote of 5 santoshjoshi2003 26-Sep-10 21:30
 My vote of 5 rohitkandhal 26-Sep-10 21:11
 My vote of 4 Henry Minute 24-Sep-10 2:20
 Re: My vote of 4 ATUL_LOONA 24-Sep-10 9:53
 Much, much better! Henry Minute 24-Sep-10 2:04
 Cool little app shteff 23-Sep-10 16:24
 [My vote of 2] Not an article Luc Pattyn 18-Sep-10 15:00
 Re: [My vote of 2] Not an article ATUL_LOONA 21-Sep-10 5:59
 Re: [My vote of 2] Not an article Luc Pattyn 22-Sep-10 17:41
 Android Luc Pattyn 22-Sep-10 18:40
 Re: Android Khaniya 23-Sep-10 3:39
 Broken... Dave Kreskowiak 18-Sep-10 3:40
 Re: Broken... ATUL_LOONA 22-Sep-10 18:03
 Re: Broken... Dave Kreskowiak 23-Sep-10 2:52
 Formatting... Sandeep Mewara 18-Sep-10 1:24
 Re: Formatting... ATUL_LOONA 23-Sep-10 21:12
 Re: Formatting... Sandeep Mewara 23-Sep-10 21:20
 Last Visit: 31-Dec-99 19:00     Last Update: 1-Apr-15 13:41 Refresh 1