2011 VIRTUAL SCIENCE FAIR ENTRY
The project “Cube It!” consisted of a 3D Rubik’s Cube application. The application has functions that will scramble and solve the cube. Along with that, it has the ability to have the user view the moves and change the speed of the moves from anywhere between two hundred moves per second and half a move per second. It also allows the user to input their own position onto a 2D net of the Rubik’s Cube and the computer will generate a set of algorithms needed to solve the puzzle. The application has been programmed in C++ using Microsoft’s Visual Studio IDE. Along with that it uses OpenGL for the 3D graphic creation. It is a win32 application; this means that it can’t natively run on UNIX based operating systems. Future additions to this project include ports to UNIX based systems, a more optimized solution, a physical robot that is able to scan and solve the cube, and the ability to input your position directly onto the 3D cube.
All in all, this project was very successful and was able to solve the 3x3x3 Rubik’s cube. The least amount of moves the application needed to run was thirty-nine; however, at the other end of the spectrum, it took one hundred and nine moves return the cube to its solved position. On average, it took about eighty-one moves to solve.
Difficulty of the Project
Hard – Requires programming experience
No safety issues
Time Taken to Complete the Project
- Programming: 150 Hours
- Board: 2 Hours
- Written Report 5 Hours
The purpose of this project was to create a 3D Rubik’s Cube simulator in C++ and OpenGL. The program should be able to scramble the cube and allow the user to place a valid position and have the computer generate a moves list needed to solve it.
Computer, Windows OS, Microsoft Visual Studio 2010, C++, OpenGL Materials were readily available. The software was purchased from a computer store.
The Rubik’s Cube, invented by the Hungarian inventor Erno Rubik in 1974, is now one of the world’s greatest puzzles. His father was an aircraft engineer, and his mother was a poet, Rubik studied sculpture originally, but then went back to school to study architecture. After his graduation he stayed at his college, the Academy of Applied Arts and Design, to teach interior design. During his years of teaching, he came up with a challenge in which he tried to have cubes be able to move without falling apart. In a first attempt to have the 26 cubes make up the big cube using elastic bands turned out to not allow the cubes to move. He then thought of a way to have the cubes hold themselves. The way he did that is by having a six-axis core that had screws under each of the centers allowing the face to turn. The edges are small cubes with a small extruding rectangular piece that fit between the core and 2 centers. The corners have a cubic piece at the bottom corner that fits between two edge pieces. This design keeps the puzzle able to be maneuvered. Once Rubik built the cube, he added stickers of different colors on each of the sides. As he did several moves he said:
“It was wonderful, to see how, after only a few turns, the colors became mixed, apparently in random fashion. It was tremendously satisfying to watch this color parade. Like after a nice walk when you have seen many lovely sights you decide to go home, after a while I decided it was time to go home, let us put the cubes back in order. And it was at that moment that I came face to face with the Big Challenge: What is the way home?" - Erno Rubik
After spending countless hours with the puzzle, he came up with several algorithms that would move only certain pieces. Within a month’s time, he was able to solve the cube.
In 1975, he applied for a Hungarian patent on the puzzle; by 1977 his patent was approved. During the same time, 2 other people tried filing a patent for a similar puzzle. One of these designs was based off of being held together by magnets. This mechanism was very widely rejected by many companies including Ideal Toy Corporation. Ideal later bought the patents for Erno Rubik’s Cube.
After the Rubik’s Cube came along, many people picked one up and came up with ways how to solve it. Now people compete in many different competitions, such as speed, one handed, blindfolded, etc. Soon companies started creating puzzles that used different mechanisms and pieces, they did this to create a cube that turns better and cut corners better, which in turn makes for a smoother cube with less lock ups. This feature helps speed cubers have lower times and a more comfortable feel in their hands. One of the most famous companies that designed a major 3x3 is V-Cubes. The mechanism they use has the corner pieces extending deep into the core allowing for a smoother turn and better corner cutting. After people surpassed the 3x3 they wanted a more difficult challenge, people started designing cubes that turned on different axes of rotation, for example, the standard 3x3 turns on its face while a cube like the Dino cube, which turns on its corners. Others then designed different shaped puzzles such as octahedral and dodecahedral puzzles. Each puzzle posed a different challenge, people would then spend time coming up with algorithms that would move certain pieces. With a countless amount of twisty puzzles people always have a challenge allowing them to think more logically and come up with solutions the problems.
Algorithms are a specific set of moves needed to do a certain task. When solving any type of twisty puzzle, one uses algorithms. Algorithms are also very useful in programming, and in robotics. When programming one uses multiple algorithms to accomplish a specific task. Also in robotics, one must have the robot do certain things to accomplish a task. Algorithms are also used in day to day thinking when using logic.
The Computer was an amazing invention. Though the first computers were bigger than houses it soon evolved into the small laptops we have today. The first computers have used punch cards to identify the button you pressed. The computers did not have LCD or LED screens they would use other things like bad resolution screens that would use pixels to show what you wrote or did. As computers evolved they started to change to electronically powered computers and they grew to having LCD screens and other high resolution screens. In the nineteen hundreds the first computer was called the Zuse Z3 and was built in Germany. This computer was the first to use the binary number system. As computers grew they started using microprocessors which are Minatare devices that are filled with vacuum tubes. The main advance in computer technology was the graphics and the memory. As the technology advanced the computers were able to hold more memory in less space and the hard drive could have more space to hold files. Soon many companies like NVIDIA started making super high quality graphic chips, they began to sell the chips to companies like Apple and Microsoft. As the computers technology increased so did its price. Though the price was high many programmers and avid gamers felt that it was worth the price. This helped many gamers play to the extreme and programmers to make amazing applications, games, and many other things. As the computers evolved so did the space engineering’s and space craft’s. When the Internet was established this kept many people to do research and to publish their discoveries wirelessly.
As different companies came out with different computers, it needed an Operating System to run. An operating system is a piece of software that manages the computer hardware resources. When a user runs an application, it goes from the user, to the operating system, to the hardware, and then up the other way around. For functions dealing with hardware memory allocations, the operating system acts as an interdisciplinary application that works with the computer hardware for the user. The three most used operating systems nowadays are Windows, Mac OS X, and Linux.
In the early 1950’s a computer would only be able to execute one program at a time. For example, to execute a simple calculator, one would have to place a card with holes, which contained the data of the application. It would then keep running until the application crashed, or finished its task.
Soon after, operating systems such as MS-DOS came out and allowed users to do basic functions. Microsoft Windows came out afterwards and allowed for a more advanced version of MS-DOS. It allowed multitasking and the ability to run on both x86 and amd64 architecture. All newer versions of Windows, starting with Windows XP use the Windows NT kernel.
Other alternatives to Windows included systems that ran on a UNIX based system. Linux and Mac are the most commonly UNIX based operating systems. Linux is the generic name for a UNIX-like operating system that can be used on a wide range of devices from supercomputers to wristwatches. The Linux kernel is released under an open source license, so anyone can read and modify its code. It has been modified to run on a large variety of electronics. Although estimates suggest it is used on only 0.5- 2% of all personal computers, it has been widely adopted for use in servers and embedded systems. Linux has superseded Unix in most places, and is used on the 10 most powerful supercomputers in the world. The GNU project is a mass collaboration of programmers who seek to create a completely free and open operating system that was similar to Unix, but with completely original code. Linux is often called GNU/Linux. Thousands of pieces of software for virtually every operating system are licensed under the GNU General Public License. Programmers from GNU took notice, and members of both projects worked to integrate the finished GNU parts into the Linux kernel in order to create a full-fledged operating system.
Mac OS X is also like LINUX, based on UNIX. It allowed for people to use all the UNIX functions with a much different interface. Mac OS X is a line of partially proprietary graphical operating systems developed, marketed, and sold by Apple Inc, the latest of which is pre-loaded on all currently shipping Macintosh computers. Mac OS X is the successor to the original Mac OS, which had been Apple's primary operating system since 1984.
Once programming languages have been introduced to the world, many companies and people started using it to program robots. The most common programming language is Java. The language evolved from C++, it was created by James Gosling who won a contest by Sun Microsystems. The contest was to make a programming language that does not have to be recompiled on each computer. It was named “Java” from a pick of random words. Gosling tried to make it as similar to C++ and C# because it would be easier for C++ and C# programmers to learn Java.
The Java programming language uses a Virtual Machine which was like previous programming languages. The Java language has many different versions including the Java Standard Edition and the Java Runtime Environment unlike C++ and other programming languages.
Using the Java Programming language you can make a variety of things; you can make Applications which are run on a computer and cannot be put on an Internet website and you can create Applets which are programmed differently and can be posted on a HTML document. Many programmers use the Java Virtual Machine (JVM) and compile and execute their program inside it while others use notepad and save the file as a *.java file. They then open command prompt and compile the program and run it there.
The main difference between C++, C#, C, and Java is that with languages prior to Java you would have to recompile the program on every computer to use it; this was a big problem resulting in fewer applications everywhere. Once Java came it improved many things including more applets on websites and helping people create websites and put games on the website. Programming has started many years ago, during the 1700’s some software’s were coded by turning on and off switches. Later, in the 1800’s the Jacquard Loom was created, it worked by using punch cards to generate automatic designs. After 1940 computers that would be recognized today were created, they were electrically powered and were able to run compiled codes. During this time computer programming languages were created. The first programming language was “Plankalkul” this language was very error prone and was not implemented till 1950. Soon after many other programming languages followed, these included BASIC and BCPL, the forerunner to C.
After a few years, C was created and it could be widely used. C shook the computer world; its impact was so great that it changed the way people thought about programming and the thought about it. Dennis Ritchie and Ken Thompson created C to meet the need for a structured, efficient, high-level language that could replace assembly code when creating system programs. Some of the problems that they faced were ease of use versus power, safety versus efficiency, and rigidity versus extensibility. Prior to C, programmers had to choose between languages that optimized coding and ones that were more powerful. For example FORTRAN could be used to code fairly efficient codes, but on the other hand was not very good for system code. This was the same for many other languages such as BASIC. Once C came along it successfully synthesized the conflicting attributes that prior languages included. In 1989 C was officially adopted by the American National Standards Institute (ANSI), this marked the beginning of modern programming. C quickly was adopted by many programmers and very rapidly updated to be used for a multiple amount of targets through different compilers. All in all, C was a language by programmers for programmers.
The next step in the computer software world was C++. This need for a new and improved programming language was derived from the fact that it was very complicated to manage the codes once they reached a certain length. C++ brought in a fairly new idea to an already well-developed language; this idea was Object-Oriented- Programming (OOP). OOP is when you have object instances that can hold data. This helps manage the codes because the data and the methods are all in one place.
C++ is an object oriented programming language. C++ is a statically typed, free form, multi-paradigm, compiled, general-purpose programming language. C++ is neither a high level nor low level programming language, due to the fact that it incorporates parts of each. Bjarne Stoustrup developed it in 1979 at Bell Labs in AT&T. It started off as an enhancement to C, called C with Classes. Later in 1983 it was renamed to C++.
C++ is one of the most commonly used programming languages in the nowadays world. It is used in application domains include systems software, application software, device drivers, embedded software, high-performance server and client applications, and entertainment software such as video games.
C++ was needed in the 1970’s and 1980’s to help manage more complex code. In C it was very difficult due to the fact that there wasn’t any objects and more complex functions. C++ rose to the occasion of being the highest-level language at the time. For example, when computers first came out it would be manually programmed with binary switches, and then came assembler, which allowed for more complex applications. As the languages became more higher-up, they allow for more advanced applications due to the newly expanded tools that come with the language. After assemble came along, it soon became difficult to use to make certain applications. A new approach came along called structured programming. This method of programming allowed people to write fairly complex code very easily. Once programmers saw what they could do, they pushed the limits of structured programming languages. To overcome this barrier and continue to expand the limits of code, a new approach had to come out. This approach was Object Oriented Programming (OOP). Object Oriented programming in summary is a methodology that helps organize code through use of inheritance, encapsulation, and polymorphism.
Although C is a very powerful language, it too has its limits. C++ is now one of the super languages. It allows programmers to push the threshold of their limits even farther. The main key to C++’s success was the fact that it included all of the functions of C and with added features. This allowed C programmers to make the easy switch to C++.
When one works with code and 3D graphics, it can be a pain to generate and manipulate them. OpenGL is an open source alternative to Microsoft’s DirectX. It is available to all platforms and has over two hundred and fifty functions to create complex 3D figures. Silicon Graphics Inc developed OpenGL in 1992. After it was released it has been mainly used for CAD software’s and many consumer games and applications. It is also nowadays used in virtual reality, medical virtualizations, and flight simulations. It allows the programmer to have full control over the 2D or 3D graphic that needs to be rendered. OpenGL is a very low level language in which the user has to define everything for every shape. For example for a square one must first generate a space with the amount of axes needed, for example a square is only in 2 dimensions. Then a matrix must be created allowing the shape to be edited then the user must specify each of the vertices of the square and connect all of them together.
Terms and Concepts for Background Research
- Rubik’s Cube
- God’s Algorithm for the Rubik’s Cube
- Least amount of algorithms needed to solve the Rubik’s Cube
- Fastest Method to solve the Rubik’s Cube
- Install Microsoft Visual Studio 2010
- Create a win32 project solution
- Create all header files needed
- Create all resource files needed
- Create all source code class files needed
1). Have one of the classes initialize each of the small cubelets that make up the whole cube.
- Call the OpenGL functions that set the vertices for the sides and corners
- Create function that will round off the edges and fill the gap between the squares that make up the pieces
- Create a function that will fill the gap between the 3 squares that make up the corner piece
- Create a function that will set the side colors
2) Have one of the classes implement color control to be able to change the colors and input your own position
- Create a function that will create a square on the screen with a color
- Create a function that will handle selecting the color
- Create a function that selects the color when the left mouse is pressed
3). Have one of the classes deal with the 2D net and 3D cube interface
- Create a function that will handle creation of each flat side
- Create a function that will draw the flat cube
- Create a function that will put a square under each tile
- Create a function that will the 3D Cube
4). Have one of the classes that will handle Side initialization
- Create a function that will clear the side colors
- Create a function that will set the side colors
- Create a function that will return the side color
5). Have a class that will create the 3D Cube
- Create a function that will render each cubelet
- Create functions that will allow rotation along the X, Y, and Z axis
- Create a function that will set the color of each face
6). Have one of the classes handle the dialog window and the interface
- Create a function that will do data exchange
- Create a function that will initialize window
- Create a function for each of the buttons and what they do
- Create a function that will allow the user to change the moves per second via a slide bar
- Create a method that allows you to navigate through the move list
7). Have one of the classes generate the moves needed to solve the cube
- Define the edges and corners
- Define how rotations move
- Create a function that will scramble the cube
- Create a function that will find an edge with a given two color sides
- Create a function that will find a corner with a given three color sides
- Create a function that will solve the top edges
- Create a function that will solve the top corners
- Create a function that will solve the middle edges
- Create a function check to see how many bottom edges are oriented and permuted correctly
- Create a function to check how many bottom corners are oriented and permuted correctly
- Create a function that will orient the last layer
- Create a function that will permute the last layer Number of Moves Needed
- Create a function that will return the moves list
After the project was completed, many runs were taken. These runs helped show truly how the application should be rated. The hypothesis was proved incorrect, for the computer took on average about eighty moves. The application programmed was able to do many functions. These included the ability to solve and scramble a Rubik’s Cube. One hundred thousand runs were executed to see how many moves on average it would take to solve the cube. On average, it was able to solve it in about eighty-one moves. The minimum number of moves was thirty-nine, and the maximum was one hundred and six moves. The application was very successful and was able to accomplish its task.
Media of Application Running:
This application has been working flawlessly 100% of the time. The application was able to have the user input their position and the program will solve it. In addition the application can scramble and solve it on its own. The user can also view the cube in 3D or as a 2D net. If the user is viewing it in a 2D map they will have the option to edit the position of the cube. After the application solves the puzzle it displays the moves needed to solve it. From this project I learned more in depth OpenGL programming and better and more efficient programming tecniques.
Questions for Further Research
Though this project has many features, there is always room for improvement. Some of these improvements include:
- Allowing the user to be able to scramble the Rubik’s Cube
- Having a more optimized solution
- Having a physical robot solve it
- Use artificial learning to figure out the algorithms If I were to redo this project, I would rewrite a more optimized solution for the cube. I might try to develop an algorithm that will result moves around God’s Number.
- "C++ for Java Programmers (9780139194245): Mark A. Weiss: Books." Web. 06 Feb. 2011.
- Dawson, Mike. Beginning C Game Programming. Boston, MA: Thomson Course Technology, 2004. Print. • OpenGL - The Industry Standard for High Performance Graphics. Web. 06 Feb. 2011.
- "Rubik's Cube History." '80s Actual. Web. 06 Feb. 2011.