Friday, 17 February 2017

Details on how the Mac Twist Rubik's Cube solver works.


I have been in the process of teaching my 13yr old son to program and we had started with the Lego Mindstrom programing in the EV3 language but had progressed to point where my son had outgrown the EV3 and was now programing in Small Basic.

My son kept expressing to me he wanted to make a Rubik's Cube solving robot and I kept replying "It's possible to do it but I think it's probably a bit too big for you." He didn't really accept my response so he started to google how to solve a "Rubik's cube" and found his way to the official Rubik's cube website that had the solution there, see https://www.rubiks.com/blog/how-to-solve-the-rubiks-cube  He here learnt the beginner method to solve the Rubik's cube and I watched him walking around the house practicing solving Rubik's cubes.

So now I was impressed with his persistence and I though well if he understands the steps and procedures to solve the cube then it is just a case of writing a program that does the same thing then build a robot that carries out the turning of the faces.

We set about writing the cube solving program in Small Basic. Code is here https://gist.github.com/flyboy74/7f57863d39a91f067b9c859865a51536

First Step was to be able to handle the arrays that to hold the data of what color tile was where. We made 6 arrays(1 for each face) that where 2 dimensional 3 x 3(3 rows and 3 columns). We wrote 12  sub routines (1 for each possible movement, each face being turned in both direction)that update the arrays of where the new colors will be after that movement see all the subroutines at the bottom of the code listed above, they are named R(), Ri(), L(), Li(), F(), Fi(), B(), Bi(), T(), ,Ti(), D(), Di() to represent the 6 faces right, left, front, back, top and down and whether they turn clockwise or anti clockwise.

Second Step was to write a subroutine to display the arrays on the screen so that we can see what is going on and that the array handling sub routines are working properly. you can see this routine in the code it is called writecube()

Now we have the building blocks to write the cube solving routine.

Third Step write the solving routine. We broke this into 6 steps, the same as what my son was using in real life to solve cubes by hand seehttps://www.rubiks.com/blog/how-to-solve-the-rubiks-cube 

The first step to solve the white cross on top face is the hardest because the cube is totally messed up in the beginning and there is so many different possibilities. It basically works like this: It loops around and around doing same process over and over till the white cross is finished. The process is this: If there is a needed tile on bottom face then move faces to place it in correct place on top elseif look in the second row of the 4 side faces and place any found on bottom face so next loop around it will be placed in correct place on top elseif look on the 1st row of of the side faces and place any found on the 2nd row so they will be found next loop around elseif look on the 3nd row of side faces and any found place in second row to be found next loop around elseif check for needed tiles on top face just in an incorrect place and move any found to the bottom face to be found next loop around. After checking all those possiblites there isn't anywhere else the needed tiles can be so if looping around and around the routine should be able to complete the top cross.

The second step to solve is the top corner tiles. We do the same thing and loop around doing same process until all 4 tiles are compete. the process is this : If needed tiles in 3 row of side faces found move to correct place on top face elseif check row 1 of side faces and any found move to row 3 to be found next loop around elseif check bottom face and any needed tiles move to row 3 of side faces to be found next loop around elseif check top face for needed tile but in wrong place and move to the row 3 of sides faces to be found next loop around.

To see our program after we had completed to here see https://www.youtube.com/watch?v=4b9WrSvGqT4

The third step to solving is the 2nd row of the side faces, it starts to get easier now because the cude is starting to become solved and less place to look for incorrectly placed tiles. It works the same way again, we loop around doing the same process until completed the process is: if any need tiles on bottom face then move to correct place on side faces elseif look on 2nd row of side faces for needed tiles but in wrong place and move to bottom to be found next loop around.

The fourth step to solve is the bottom face. The only place they can be is on the bottom face just can be in the wrong position. So we just if we find any then move to correct place

The last step is to move the tiles on bottom face till around till tiles on row 3 in side faces are in correct postion.

Fourth Step in making the MacTwist was just to hook it up to the robot and solve some cubes in real life. see https://www.youtube.com/watch?v=XwmS-PspKXk

Fifth Step is now to get a camera to read the faces so that we don't have to type in what colors are on what faces. This is a big step and I will write my next blog to explain how we achieved this.


No comments:

Post a Comment