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.

It will replicate a real Rubik’s cube of any dimension up to 200x200x200
The simulator will scramble the cube
The simulator will run multiple algorithms and provide a timer
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 =)

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.

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 &lt;&lt; "The address of integer c is : " &lt;&lt; &amp;c &lt;&lt; "\n";
//declare the integer pointer e and assign the address of c to it
int * e = &amp;c;
//print the value that is held by integer pointer e
cout &lt;&lt; "The value held by integer pointer e is : " &lt;&lt; e &lt;&lt; "\n";
//print the value that the pointer is pointing to
cout &lt;&lt; "The value pointed to by integer pointer e is : " &lt;&lt; *e &lt;&lt; "\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.

Memory

What is memory?

When we discuss memory in terms of computers, we are usually referring to a storage device such as a hard drive, RAM, USB stick, CD, SD card, etc. These devices are capable of storing data on them for a certain period of time. Storage devices hold a series of electric charges to represent bits. The electrical charge can be held using a variety of techniques like ferromagnetic strips in cassettes, ferromagnetic disks in hard drives, or transistors in RAM.

Image 1 below shows how data is stored on ferromagnetic disks. This technique uses a writing head which applies a magnetic field to flip the polarity of the ferromagnetic material. The polarity of the bit determines it’s value, either a 0 or a 1.

Image 1 : A diagram showing the internal writing element of a hard disk

Image 2 below shows a schematic diagram of DRAM. It is composed of an array of transistors paired with a capacitor to hold the electrical charge. Each transistor capacitor pair is used to represent a bit. If it contains a charge, the bit value is 1 and 0 otherwise.

Image 2 : DRAM schematic diagram (source : wikipedia commons)

Volatile vs Non Volatile

Memory can be classified as volatile or non volatile depending on how the charge is stored. Volatile memory loses all the information stored on it when the power is turned off. RAM is an example of volatile memory. Non volatile memory is capable of holding the data after power is removed from it. USB drives and CDs are examples of non volatile memory.

Pointers and memory are the most fundamental cornerstones of computer science but they can also be very confusing. If not coded carefully, pointers can overwrite sections of memory and lead to unpredictable results.

Accessing Memory

So we now understand the basic concept of memory, now we will try to understand how we can read and write to memory. Since hard drives and RAM are the two most important storage devices on a computer, we will discuss the reading and writing of data for those two items.

All storage devices have an organizational structure to help find information quickly. Hard drives are divide up into sectors and into concentric circles called tracks using a pattern of zeros and ones. These markers help determine the location of the reader head in relation to the data on the disk’s surface. A group of sectors is called a cluster/block which is the minimum unit the operating system will use to store information. Files can be stored in a series of blocks. The size of a block may vary depending on the size of the disk or the operating system. Hard drives also have a special file located in sector 0 of the disk. This file is used to specify how the disk is formatted. Some formatting examples are NTFS, FAT32, and exFAT. As technological advances have lead to increases in hard drive storage capacity, new formats have been developed to support the growing address space.

Image 3 : Basic illustration of the divisions of a hard disk (Source : May, J., & Lee, D. (2009, May). [Hard drive internals schematic]. Retrieved September, 2017, from https://technet.microsoft.com/en-us/library/dd758814)

RAM operates differently than hard drives since it does not have moving parts like a spinning disk. This is why accessing RAM memory is much faster than reading from a hard drive. The organizational structure of RAM is like a grid pattern with each cell having its own memory address. When we want to read the data in a cell, the memory address is sent to a decoder which selects the data lines that intersect the cell. The data is then read from the cell. The same method is applied when writing to a cell. Image 4 below shows a simplified example of how RAM works. If the value 000000 is put into the input address line, the value of the top left cell is returned. Note** There is a latch on the data select lines which is not shown in the image for simplicity. The purpose of the latch is to control reading and writing to the cells.

Image 4 : Simplified example of RAM

CPU Caches and Registers

Finally, I would like to mention that there is another piece of memory we did not talk about but is crucial to making a fast computer – the cache and the registers.

The cache is a series of smaller blocks of memory which are located inside the CPU. Why does the CPU need a cache? These caches help save time for the CPU to get data from main memory since it is a time consuming process to retrieve data from main memory. Most CPUs have three or more types of caches which include an instruction cache, data cache, and a translation lookaside buffer (TLB).

Instruction cache

The instruction cache is used to store commonly used instructions like adding two values or moving to a specific memory address.

Data cache

The data cache is a hierarchy of multiple caches (L1, L2, L3, etc). The L1 cache contains variables that are most frequently used in an application. The L2 cache contains variables that are not as frequently used but still referenced often. Higher level caches are usually shared between multiple cores of a processor.

Caches have different replacement policies to keep recently used data in the cache. One popular method is the least recently used policy. Using this method, the cache operates similar to a queue where the most recent items are kept. When the CPU is looking for a memory location and it is found in the cache, a cache hit has occurred and the item is moved up the queue to the most recently used position. When the CPU does not find the memory location it is looking for, a cache miss has occurred and the CPU looks into the next higher tier of cache until it finally searches in main memory (RAM). When the memory location is found, the value is moved to the front of the L1 cache queue and the least recently used item is removed.

Translation lookaside buffer and virtual memory

Programs running on an operating system are given a virtual address space which is much larger than what is physically available in memory. This helps to simplify the writing of computer programs where the complexities of mapping physical addresses are handled by the memory management unit (MMU). That is where the translation lookaside buffer (TLB) comes in to help find recently accessed mappings of virtual to physical memory. If the mapping is not found in the TLB, the system will look in the page tables. The page tables are a chunk of physical memory mapped to virtual memory. If the mapping is not found in the page tables, a new page will have to be read in from the disk. Image 5 below shows the process of looking up memory mappings.

Image 5: Virtual to physical address translation (source : wikipedia commons)

Registers

So what is a register? A register is a small block of memory that the CPU directly operates on by reading and writing values. Have you ever heard of someone saying that they have a 32, or 64 bit computer? That term is used to describe the size of the register that a CPU is using. Registers can be of any size, but the most common register sizes are 8, 16, 32, and 64 bit. You can find 8 and 16 bit registers on smaller processors used in embedded systems.

Here is an analogy to help you understand the whole memory hierarchy: The CPU is a carpenter and the registers are his tools that he has directly on hand. If he needs a material or tool, he can look on the nearby workbench (cache) for things that he is frequently working on. If he cannot find what he is looking for, he can go to the workshop (RAM) across the street to look for things that are less frequently used. Finally, if the item is not found in the workshop (RAM), he can go across town to search at the warehouse (Disk).

Conclusion

So far we have covered different memory technologies that are used to store data, detailed descriptions of how hard drives and RAM work internally, and CPU caches and registers. Of course there are much more complexities to understanding how memory works in modern systems but this is the foundation that we need to understand how a computer program uses memory and how to write efficient code. My next post will cover pointers and arrays.