Solving Rubiks Cube Using Open CV

Abstract

The Rubik’s cube is 3D combinatorial and mechanical puzzle invented in 1974. It challenged users to solve colourful puzzle in record time. We use OPEN CV to solve this Rubik’s Cube. We will recognize the scrambled state of the cube. Then will implement an algorithm that takes input as scrambled state of the cube and outputs a sequence of moves that solves the cube. In order to recognize colours on each faces of the cube and then applying various algorithms on it in order to solve the Rubik’s Cube.

Introduction

I. INTRODUCTION

1. The most vital a part of solving a Rubik's Cube is knowing how it works Rubik's cube is one in every of the foremost challenging and most famous puzzles of all time.
2. It continues to stay within the top among the puzzle games thanks to the look of the puzzle i.e. one correct solution out of the 43 quintillion other possibilities ?
3. Only 5.8% of world population can solve the Rubik's cube efficiently. But Al& ML concept is ready to try and do with minimum number of moves. ?
4. There are three major parts to solve any Rubik'sCube First is identifying the positions of various colours at different positions.
5. Second is to develop a series of steps which may be wont to solve the cube and third is to implement these steps on the cube to induce the ultimate result

II. LITERATURE SURVEY

Authors in this Vasile Dan, Gabriel Harja, Ioan Na?cu [1] paper say that The process of solving the Rubik’s cube begins with the acquisition of data from 4 webcams. They are positioned in four different corners of the cube at 200 mm. Two of the webcams have been positioned at the top and the other two at the bottom, thus all the pieces are visible. The colors on each side of the cube are identified and the two implemented methods, Kociemba’s algorithm and blindfolded method, are applied. The generated solutions are sent to Arduino Due via the serial interface. Six stepper motors will rotate the faces of the cube, according to the chosen method. The 4 digits of the 7-segments display will show the solving time.

Color Recognition: A. Converting the color space of the image: from BGR (Blue, Green, Red) to HSV (Hue, Saturation, Value). The other two parameters are used for variating shadow and shine. B. Image filtering: using openCV library, Smooth Median filter, for reducing the salt and pepper noise. C. Selecting the regions of interest from the four images. These regions consist of one pixel on piece of the cube, due to the previously applied filter. D. Color identification, based on the 3 values of the pixel

 This Harshad Sawhney, Sakshi Sinha, Anurag Lohia, Prashant Jalan, Priyanka Harlalka. [2] paper proposes

Mechanical design: One of the most important parts of the robot was its mechanical design. On each of the four side walls of the cuboid, One stepper motor is mounted with utmost precision so that motors at opposite faces has their shafts coaxial. On each of these motors a gripper has been mounted which is driven by servo motors . Electronics: The electronic part basically contains a microcontroller which is the brain of the robot. The microcontroller used is “Arduino Mega” and the motors are connected to the pins of the microcontroller which gives commands to motors based on a code stored inside the chip or Atmega of the microcontroller. Image processing: Image processing is a technique to store the colours of any object in a format that can be processed through codes and programs Software Architecture: Image is being processed by the code of Dev C++. We are taking the images of all the faces of the cube. The sequence in which the image is taken is determined by the kociemba algorithm. Binary Conversion Of Image: A 3-channel RGB image is captured by the camera. Each color has its own three values (hue, saturation and value) which distinguish it from other colors. Using this property, a binary image can be generated for all the six colors of the cube. Centroid Detection & Filtration: Blob detection is applied on the binary image of each color. CV Blob library is provided by OpenCV which is used for detecting the blobs. Koceimba’s algorithm: After finding the matrix that stores the colors of the individual blocks of the six faces of the cube, an algorithm are required which provides the steps that can solve the cube. Arduino coding.The Arduino is coded in Arduino interface and it provides rotation to each face of the cube. The code ensures that the grippers do not collide with each other at any point of time while unscrambling the cube.

This Ms. Ekta S. Toshniwal, Mr. Yogesh Golhar [3] paper has Thistlethwaite’s algorithm: The Thistlewaite Algorithm was the least effective method of solving the Rubik’s cube requiring an average of 42 moves and 3 mins and 48 seconds. This method was found to be not too much effective and useful. Kociemba’s Algorithm: Kociemba’s Algorithm was an improvement on Thistlethwaite’s algorithm. The Kociemba’s algorithm proved to be the 2nd most effective algorithm, requiring an average of 28 moves and 2 mins and 32 seconds.d

III. EXISTING SYSTEM

A. Existing System

Rubik’s Cube could be a widely popular mechanical puzzle that has attracted attention round the world due to its unique characteristics. As a classic brain-training toy well-known to the general public, Rubik’s Cube was used for research project and technology development by many scholars.

The Rubik’s cube could be a single-player game and a sequence of random moves, irrespective of how long, is unlikely to finish within the goal state. Developing machine learning algorithms to cater to this property of the Rubik’s cube might provide insights into learning to unravel planning problems with large state spaces. Although machine learning methods have previously been applied to the Rubik’s cube, these methods have either did not reliably solve the cube1–4 or have had to depend upon specific domain knowledge5,6 .

Outside of machine learning methods, methods supported pattern databases are effective at solving puzzles like the Rubik’s cube, the 15 puzzle and also the 24 puzzle7,8 , but these methods are often memory-intensive and puzzle-specific. More broadly, a significant goal in AI is to make algorithms that are able to learn the way to master various environments without wishing on domain-specific human knowledge. The classical 3×3×3 Rubik’s cube is barely one representative of a bigger family of possible environments that broadly share the characteristics described above. because the size and dimensions are increased, the complexity of the underlying combinatorial problems rapidly increases. for instance, while finding an optimal solution to the 15 puzzle takes but a second on a modern-day desktop, finding an optimal solution to the 24 puzzle can take days, and finding an optimal solution to the 35 puzzle is mostly intractable9 . Not only are the aforementioned puzzles relevant as mathematical games, but they will even be wont to test planning algorithms 10 and to assess how well a machine learning approach may generalize to different environments. Furthermore, because the operation of the Rubik’s cube and other combinatorial puzzles are deeply rooted in pure mathematics, these puzzles also raise broader questions about the applying of machine learning methods to complex symbolic systems, including mathematics.

IV. PROPOSED SYSTEM

1. In order to beat the prevailing problems, we propose the way to solve “Rubiks Cube Using Open CV”. ?
2. Aim of this project is to solve a unsolved Rubik's Cube. ?
3. The program contains OpenCV libraries and that we are solving the cube using Kociemba algorithm. ?
4. We decided to use Kociemba’s algorithm rather than the optimal solution because it gives us a “reasonable” solution during a short amount of computing time.Kociemba’s algorithm guarantees an answer with under 30 moves. ?
5. Kociemba’s algorithm creates a two-phase approach that permits it to go looking for an answer faster the primary phase is to induce the cube to “state 1.” State 1 is any subset of the cube which will be achieved by running the moves: Up clockwise, Down clockwise, Right 180, Left 180, Front 180 and Back 180 from a solved cube. ?
6. Kociemba’s algorithm uses an intensive set of pruning tables to formulate the foremost efficient “moveset” to rework a scrambled cube to state 1. ?
7. Then, it uses the identical moves given above to remodel the cube from state 1 to a “solved state.” ?
8. When a unsolved Rubik's cube is shown before of a camera, and therefore the computer vision algorithm detects the position of the face within the webcam picture and identifies the facelet stickers along with their colors.            
9. The two-phase-algorithm is used to solve the Rubik’s Cube. 
10. When these moves are followed we get the tip product of a solved Rubik's Cube within 30 moves.

A. Algorithm

Kociemba’s algorithm performs much more better than  Thistlethwaite’s as it reduces the quantity of phase transitions to only 2 rather than 4 this implies that transition must be applied between 3 groups:

                                G0 = hU, D, R, L, F, Bi.

                                G1 = hU, D, R2, L2, F2, B2i

G2 = {C}

Group G0

G0 is that the group of all states reachable using moves L,R,F,B,U,D. Notice how this is often just all reachable states using any of the legal moves defined in section 2.1.3 since we are able to perform any L2,R2,F2, etc moves by changing L * L , R * R, F * F. Similarly we are able to perform any L3, R3, F3, by changing moves L * L * L, R * R * R, F * F * F. Our aim is to maneuver from G0 → G1 → G2 → G3 → G4. Where G4 contains only the solved cube state.

Group G1 

G1 is the group of these moves L,R,F,B,U2,D2 to reach all the states .G1 is different to group G0 as all smaller states are reachable. G1 contains only ‘good’ edges. to work out why this can be so, allow us to recall to our edge flip lemma in section 2.2.1.2. to clarify why there are always an excellent number of flips, we proved that using only moves U, R, D and L, it's out of the question to flip any edges. rather than moves U, R, D and L, allow us to prove the identical result's possible using moves L, R, F, B, U2 and D2.

Group G2

The group G2 is simply the solved state. Using only moves in G1 the state is changed directly from G1 → G2.

B. Architecture

C. Project Description

1. Face Notation: Usually one labels the faces of a Rubik’s cube using the color of its faces. E.g, For the official international colour scheme: Red, Blue, Yellow, etc. However, it's more useful to possess a notation that's independent of face colour. this is often because colour schemes vary from cube to cube. Instead we are able to label the cube using the direction that the face faces. Assume we've the official Rubik’s cube with international color scheme in an exceedingly position specified the blue face faces upwards and therefore the white face faces towards ourselves, we will label the faces as follows: F (Front), R (Right), L (Left), B (Back), U (Up) and D (Down).

2. Move Notation: Now that we’ve seen a notation that we are able to view to faces, we are able to now define a notation that defines moves that we are able to perform on the cube. we want two pieces of knowledge to define a move: the face and therefore the number of 90 degree turns clockwise. For example: R1 could be a 90 degree clockwise turn of the correct face, L2 may be a 180 degree turn of the left face and B3 could be a 270 degree clockwise turn (or a 90 degree anticlockwise turn) of the rear face.

3. Rotation Notation: So far, we've got only defined which faces we are able to move. we are able to also express cube rotations that rotate the full cube. we will define the way to rotate the whole cube by defining the axis of rotations X, Y and Z. If we draw a line through the R face to the L face as per figure, we define the gyration X as following the clockwise direction turn of the move R. Similarly, the Y dextrorotation would follow the rotation of U in and Z revolution would follow the rotation of F.

This diagram shows how to solve rubik’s cube .

   D. System Requirements

1. Hardware Requirements

Processors : More than intel i3

RAM         : 4 GB

Storage      : 5 GB

Standard Devices : Keyboard, monitor, mouse and camera

2. Software Requirements

Platform : Windows XP/ 7/10/11 /Vista

Language : Python

Simulator : OpenCV

Cloud : Google Colab

IDE/tool : anaconda

V. RESULT ANALYSIS

Conclusion

1) The image processing on appropriate estimations can correctly work out the blobs of the cube and hence completely gives the initial state of the cube. Finally the use of Koceimba’s algorithm gives the solution of the Rubik’s cube which can be finally used to instruct the users to solve the cube accordingly. 2) A system design for control system is expected to solve Rubik\'s cube. Using algorithm, open CV and image processing. It helps the user to solve the scrambled Rubik\'s cube. The user can effectively solve a Rubik\'s cube in least number of steps. Rubik\'s cube can be solved Without the use of any machine and user solver it with his own hands.

References

[1] D. Zeng, M. Li, J. Wang, Y. Hou, W. Lu and Z. Huang, \"Overview of Rubik’s Cube and Reflections on Its Application in Mechanism,\" Chinese Journal of Mechanical Engineering, vol. 31, 2018. [2] E. D. Demaine, M. L. Demaine, S. C. Eisenstat, A. Lubiw and A. Winslow, \"Algorithms for Solving Rubik’s Cubes,\" Algorithms – ESA 2011, vol. 6942, pp. 689-700, 2011. [3] El-Souranil, N. &. Hauke, S. &. Borschbach and Markus, \"An Evolutionary Approach for Solving the Rubik’s CubeIncorporating Exact Methods,\" Lecture Notes in Computer Science, vol. 6024, pp. 80- 89, 2010. [4] S. Saeidi, \"Solving the Rubik’s Cube Using Simulated Annealing and Genetic Algorithm,\" International Journal of Education and Management Engineering, vol. 8, 2018. [5] S. P. Rohith, A. M. Sharif, S. Jayasankar and M. Harikrishnan, \"Autonomous Rubik’s Cube Solver Bot,\" International Journal of Scientific Research and Engineering Development, vol. 2, no. 3,pp. 146-151, 2019. [6] D. Gilday, \"MindCuber,\" [Online]. Available: http://mindcuber.com. [Accessed 20 November 2020]. [7] J. W. Daryl, \"RukuRobot,\" [Online]. Available: https://rukurobot.weebly.com/. [Accessed 20 November2020]. [8] \"3dprint,\" [Online]. Available: https://3dprint.com/116817/3d-printed- rubikscube-robot/. [Accessed 20 November 2020]. [9] [Online]. Available: https://www.cs.brandeis.edu/~storer/JimPuzzles/RUBIK/Rubik3x3x3/READING/KociembaPage.pdf. [Accessed 21 November 2020] Rubik\'s cube solver [10] S. P. Rohith, A. Mohamed Sharif, S. Jayasankar, M. Harikrishnan “Autonomous Rubik’s Cube Solver Bot” International Journal of Scientific Research and Engineering Development, Vol.2, Issue 3, (May - June 2019) pp.146-151. [11] D. Zeng, M. Li, J. Wang, Y. Hou, W. Lu and Z. Huang “Overview of Rubik’s Cube and Reflections on Its Application in Mechanism” Chinese Journal of Mechanical Engineering ,Vol.31, Issue 1, (December 2018): pp.1-12. [12] Ayman M. Abo El-Maaty, Magda B. Fayek “Observations on Exploration and Exploitation Effects on Solving Rubik’s Cube Using Evolutionary Strategies” International Computer Engineering Conference, Cairo, Egypt: IEEE, 2017. pp. 9599. [13] Hassan Samadi, Mohammad Reza Daliri “Solve the Rubik’s Cube with Robot Based on NonInvasive Brain Computer Interface” Iranian Conference on Intelligent Systems (ICIS), Bam, Iran: IEEE, 2014. pp. 4-6.

Copyright

Copyright © 2022 Dr. M. B. Sudhan, Prabhanjan Desai, Surendra Kumar E, SK. Theja Sri, S. Rajwal. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.