Rubik’s cube algorithms

How did I get here?

So I will admit that I occasionally procrastinate when I get bored of doing a task and one of my favorite things to do is watch youtube videos. Thats when I recently stumbled upon a few videos of Rubik’s cubes. I have had a Rubik’s cube as a child and it was a really fun toy but I eventually solved the 3x3x3 cube and then proceeded to destroy it. I was definitely a very destructive child. Now a series of videos have appeared showing other extremely large cubes and polyhedrons which sparked some interest in understanding how to make an algorithm to solve these puzzles.

Here is a video of a 13x13x13 Rubik’s cube being solved.

What’s next?

Well, it would be awesome if I could buy several large Rubik’s cubes and try out different methods but that would be too expensive and time consuming. There also comes a point where it becomes too difficult to make a higher order cube due to physical and manufacturing limitations; I would say that a 22x22x22 cube is the largest I have seen but it was barely holding itself together on each turn. So lets just make a Rubik’s cube simulator!

The Specs

Okay, so we are going to make a Rubik’s cube simulator… so where do we begin? Lets just list out all of the requirements for the simulator.

  1.  It will replicate a real Rubik’s cube of any dimension up to 200x200x200
  2. The simulator will scramble the cube
  3. The simulator will run multiple algorithms and provide a timer
  4. The cube can be seen from a 3d perspective

After searching on github, I had found many Rubik’s cube simulators written in different programming languages. Since my main focus of this project is to test out a few algorithms, I will take an existing github project and expand it to support my requirements. I ended up finding a project that was built in unity with C# and the 3d look of the cube was very appealing. This is the link to the project : RSolver. This will save me a lot of time looking for materials and assets.

Post is still in progress… check in later for updates =)

Advertisement

Pointers and Arrays

What are pointers?

Pointers are variables that hold the memory address of another variable. Please see my previous post on memory, if you need a refresher on how memory works. When you use a pointer, you are able to access the variable that it points to, and you are also able to change the pointer so it points to another variable. This process of accessing variables through pointers is called indirect addressing.

Note** Pointers are not available to be used in every programming language. Some languages like Java abstract out the usage of pointers but they are actually used under the hood. C++ is a powerful programming language that supports pointers and all of the examples in this post will be done in C++.

How are they useful?

So why do we need a pointer instead of just directly using a variable? Sometimes we need to do operations on a memory address; For example, if we have a group of variables next to each other in memory, it is easier to send to a function one pointer to the beginning address of the group than sending the whole list of variables.

Examples

Image 1 below shows an example of some integers, characters, and pointers in memory. I have shown the values of the data in hexadecimal notation and I have also provided a conversion into the matching data type. So for the integer A, the hex value is 0042 and when it is converted to base 10 it becomes 66. For the character D, the hex value is 0048 and converting it to ASCII notation gives us the letter H.

Screen Shot 2017-09-09 at 2.30.18 AM

Image 1 : Example of integers, characters, and pointers in 16 bit memory

Now we will look at the integer pointer E which is located at memory address 0x9020. The value that E contains is the address of integer C.

Okay, so we see how this looks in memory, but how is it done in code?

In C++ this can be done with the following code.

//declare the variable c and assign a value to it
int c = 88;
//print the address of integer c
cout << "The address of integer c is : " << &c << "\n";
//declare the integer pointer e and assign the address of c to it
int * e = &c;
//print the value that is held by integer pointer e
cout << "The value held by integer pointer e is : " << e << "\n";
//print the value that the pointer is pointing to
cout << "The value pointed to by integer pointer e is : " << *e << "\n";
    • On line 2 in the code snippet above, we declare the integer c and assign the value 88 to it.

 

    • On line 4, you will notice that I have printed out the memory address of the integer c that was declared by using the ampersand sign (&). In C++, this is called the address-of operator and it is used to return the address of any variable that follows it.

 

    • On line 6, to the left of the equal sign we declare the integer pointer e. Pointers are declared in C++ by using an asterisk following the type declaration – TYPE * NAME.

      For example :
      char * character;
      int * number;
      float * decimal;character, number, and decimal are all pointers which take the same amount of space in memory but they point to different data types. The data types to which they point may not take up the same space in memory. Although they are pointers, character, number, and decimal are not considered the same type. A character pointer (char *) is not the same as an integer pointer (int *).

 

    • On line 6, to the right of the equal sign, we are assigning the address of the integer c to the integer pointer e.

 

  • On line 10, we get the value that the pointer e is pointing to. This is called dereferencing a pointer and it is done by using an asterisk in front of the pointer name (*pointer_name). Do not confuse this with a pointer declaration like what is shown on line 6 – they may have the same symbol but the usage is very different. The dereference operator first looks up the type of pointer that is being dereferenced. Then it jumps to the memory location that the pointer is pointing to and finally converts the data at that location based on the pointer type. So if the data was being pointed at by an integer pointer, then the dereference operator would convert that data to an integer.