MATLAB Examples

MATLAB based Rubik's Cube® Solver using an Arduino

How many of you have successfully solved a Rubik's Cube® before? How long did you take to solve a cube that your friend scrambled? I have been able to successfully solve a Rubik's Cube, but have never been able to solve it in less than a couple days in all my previous attempts. Therefore for this summer we were excited to build a MATLAB® controlled solver which would solve a scrambled cube in a few minutes. The main requirement of this project was to keep it low cost. As a result, we needed to use readily available materials to build the cube solver apparatus. Further, we wanted to use the support provided in MATLAB R2014a for interactive communication with Arduino boards, and USB based webcams. This would allow us to implement the entire algorithm in MATLAB and focus our efforts on the algorithm.

Contents

Required hardware

Before we get into the details of the algorithm to solve a scrambled Rubik's Cube, let us first go through the process of building the cube solver apparatus. Given the requirement to keep the hardware to a low cost, we reused material that was left over from previous hardware projects. Below is a list of items we used to build the solver setup:

Note that a SparkFun RedBoard has an instruction set and pin-out identical to an Arduino Uno. We used the RedBoard for our project.

The setup is shown in the photographs below:

Verify that MATLAB is connected to the hardware

Once you have all the required hardware in hand, it is important to verify connectivity to the RedBoard, the servo motors and the USB webcam from MATLAB. It is a good practice to always perform this verification process prior to building the setup to prevent the need to dismantle the setup at a later stage due to faulty hardware.

To enable MATLAB to connect to the hardware, the following Hardware Support Packages are required:

Follow the instructions at each link to download and install the required packages. Next, execute the example code provided as a part of the installation of the above packages to verify that MATLAB can connect to the RedBoard and to the USB webcam. Since the RedBoard has an instruction set identical to the Arduino Uno, we set Board_Type to Uno in the support package examples. If you are using a different Arduino board (that is supported by the Hardware Support Package) then choose the appropriate value. Click here if you have any trouble with connecting to the SparkFun RedBoard. For troubleshooting connectivity to the USB webcam, go here.

To verify connectivity to the servo motors, let us connect the two servo motors to the RedBoard as shown below:

Following this, let us clear the MATLAB workspace and recreate an Arduino object and connect to the servo motors:

clear

port = 'COM20';
board_type = 'Uno';
arduino_board = arduino(port, board_type)
arduino_board = 

  arduino with properties:

                    Port: 'COM20'
                   Board: 'Uno'
     AvailableAnalogPins: [0, 1, 2, 3, 4, 5]
    AvailableDigitalPins: [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
               Libraries: {'I2C', 'SPI', 'Servo'}

The port defines the COM port over which your Arduino board is communicating with MATLAB. You can find the COM port your board is connected to by expanding 'Ports(COM & LPT)' under 'Device Manager' on a Windows machine. board_type defines the Arduino board you are using to run your project, e.g., 'Mega2560', 'Uno'.

Once the arduino object arduino_board is created, let us create servo motor objects. The servo objects are used to control the physical servo motors connected to your Arduino board:

% Servo connected to the Cube holder
servo_front_pin = 13;
% Servo connected to the Cube gripper
servo_back_pin =  9;

% Define the max and min PWM pulse durations
servo_front_max_pwm = 2250e-6;
servo_front_min_pwm = 750e-6;
servo_back_max_pwm = 2300e-6;
servo_back_min_pwm = 800e-6;

% Create a servo object for the two servo motors
servo_front = servo(arduino_board, servo_front_pin, 'minpulseduration', ...
                                                servo_front_min_pwm, ...
                                                'maxpulseduration', ...
                                                servo_front_max_pwm);
servo_back = servo(arduino_board, servo_back_pin, 'minpulseduration', ...
                                                servo_back_min_pwm, ...
                                                'maxpulseduration', ...
                                                servo_back_max_pwm);

Along with providing the arduino board object and I/O pins on which the motors are connected as inputs, additional arguments that control the span of the servo rotation can be passed in. In the above lines, 'minpulseduration' defines the pulse width that is used to position the motor at zero degrees, whereas the 'maxpulseduration' defines the pulse width for the 180 degree position. The specific pulse width values can usually be obtained from the datasheet of the servo you are using. However, you may need to tweak the values a bit in order to compensate for slight mechanical inaccuracies. Note that we have done this to align our servo motors.

Once the connection is established to the servo, use writePosition function to test the servo motors and verify that MATLAB can control them:

% Move the first servo
positionHolder = 78/180;
writePosition(servo_front, positionHolder);

% Move the second servo
positionGripper =  20/180;
writePosition(servo_back, positionGripper);

If the servo motors do not move, try changing the values of the positionHolder and positionGripper variables. Also, ensure that the motors are connected to the Arduino as shown above.

Set up the Cube Solver Apparatus

After verifying the hardware connectivity from MATLAB, we assembled our cube solver as shown above. The following video showsthe key features and basic operations of the solver:

The accompanying file sketch_dimensions.jpg shows the dimensions and layout of the various components. In addition, cube_gripper.lxf can be opened with LEGO Digital Designer to help you build an identical setup, and setup_tips.pdf offers a few additional tips to optimally set up the solver.

Read the initial state of the scrambled cube

We are now ready to play with the motors and control them as desired. The MATLAB Support Package for Arduino Hardware provides the writePosition function, which instructs the servo to move to a user-defined position. We use this function to reset the front and back servos to their initial states prior to solving the cube. The maximum range of the servo motor we used is 180 degrees, therefore we divide the required angle by 180 to ensure the input is between [0, 1]:

retract =  15/180;
center  = 90/180;

writePosition(servo_back, retract);
writePosition(servo_front, center);

Here the back servo is instructed to move to the 15 degrees position, which retracts the gripper attached to it. The front servo is moved to the 90 degrees position, which aligns the cube handler with the gripper. These values might need to be changed depending on the orientation of the servo motors in your setup.

With the initial setup complete, the cube solver needs to read in the initial facelet configuration of the 3x3 Rubik's Cube. This is used by the cube solving algorithm to calculate a sequence of moves to solve the scrambled cube. Therefore, to save the user from manually entering the colors of the 54 squares, we use a webcam and image processing to capture the initial state of all 6 sides.

In this article we refer to the six sides of the cube as 'faces'. Each face has nine facelets, eight of which can be moved around, and the middle facelet which cannot be moved. Therefore, we define the color of a face by referring to the color of the immovable center piece. We use the following naming pattern for each face of the cube:

  • Front (F) - face with the red immovable facelet
  • Right (R) - face with the blue immovable facelet
  • Back (B) - face with the orange immovable facelet
  • Left (L) - face with the green immovable facelet
  • Up (U) - face with the white immovable facelet
  • Down (D) - face with the yellow immovable facelet

Each face is also assigned a letter index (the first letter of the name of the face shown in parenthesis). These letters are used by the algorithm to solve the cube. Remember, a Rubik's Cube is solved if every facelet on a given face is the same color as the center facelet on that face.

With the servo motors initialized, we placed the cube in the holder with the 'Front' face (with red immovable middle facelet) facing the camera and the 'Up' face (with white immovable middle facelet) facing away from the RedBoard. The algorithm expects this initial position. Using the webcam connected to the cube solver setup, we identify the color of each facelet on all sides of the cube:

[cube_state, R]= readCubeFaces(servo_front, servo_back);
Reading configuration for side: 1
Reading configuration for side: 2
Reading configuration for side: 3
Reading configuration for side: 4
Reading configuration for side: 5
Reading configuration for side: 6

The custom function readCubeFaces first takes a snapshot of the Front face of the cube and identifies the colors on each of the facelets with the help of functions provided in Image Processing Toolbox. The cube is then flipped and rotated a number of times in a preset sequence to capture the facelet colors on the other five faces. The faces are read in the following preset order: Front, Right, Back, Left, Up and Down. After the process is complete, the captured initial cube state is displayed to the user.

Click the Save & go button to accept the captured state and proceed further. When you press this button the algorithm checks for any possible errors in the captured state. If none are found, it proceeds to solve the cube. On the contrary, if there are any errors then the initial cube state is shown again to correct the errors. The incorrect colors can be identified by looking at the cube and corrected by replacing the incorrect letter. Cancel undoes any unsaved changes, while the Reset button clears out all facelet configuration entries.

Solve the scrambled cube

With the initial configuration of the cube saved, the solve45 function is called to find the set of moves required to solve the cube. This function is an implementation of Thistlethwaite's algorithm for solving a Rubik's Cube. We chose Thistlethwaite's 45 algorithm as it is a well-known algorithm for finding the minimum set of moves, and it is guaranteed to solve a cube in at most 45 moves. The solve45 and associated functions were provided by a MATLAB Central File Exchange submission written by Joren Heit.

The solve45 function accepts the initial state of the cube and then outputs a solution sequence of human readable moves of the form:

  • F: Turn the Front face 90 degrees clockwise
  • F': Turn the Front face 90 degrees anti-clockwise
  • F2: Turn the Front face by 180 degrees
  • B: Turn the Back face 90 degrees clockwise
  • B': Turn the Back face 90 degrees anti-clockwise
  • B2: Turn the Back face by 180 degrees

The same naming pattern applies to turn the Up, Down, Left and Right faces. The first letter indicates which face to turn, and the presence of ' or 2, indicates the direction or amount of rotation.

To directly implement the above sequence we would need 6 servos, each controlling an individual face of the cube. However, we only have two servos. Therefore, in order to manipulate the individual faces of the cube in succession, we have written a set of basic operations that the cube solver can perform to achieve the same effect. Since our design uses only two servo motors, we are restricted to manipulating just the single face that is in contact with the cube holder. Therefore, to expose other faces of the cube for manipulation, the cube needs to be rotated and flipped. The following is the list of all the basic operations:

  • FlipCubeForward: flips the cube, by pushing it against the wall of the cube holder.
  • TurnCubeLeft: rotates the whole cube holder to the left.
  • TurnCubeRight: rotates the whole cube holder to the right.
  • TurnFaceAntiClock: rotates the face directly in contact with the cube holder by 90 degrees anti-clockwise as seen by someone holding the cube and looking directly at this face.
  • TurnFaceClock: rotates the face directly in contact with the cube holder by 90 degrees clockwise as seen by someone holding the cube and looking directly at this face.

Each of the above functions execute a sequence of writePosition functions to move the front and back servos as required. As an example, you can see the sequence of commands executed in the TurnCubeLeft function below. The pause command is used between the writePosition commands to provide sufficient time for the Arduino and the servo motor to complete the previous change in position.

function final_cube_state = TurnCubeLeft(cube_state, servo_front, servo_back)

PAUSE_DURATION = .5;
   pause(PAUSE_DURATION);
   writePosition(servo_back, 15/180);
   pause(PAUSE_DURATION);
   to_pos_l = readPosition(servo_front) + 90/180;
   writePosition(servo_front,  to_pos_l);
   pause(PAUSE_DURATION);
   % Identify the final state of the cube
   final_cube_state = [cube_state(3) cube_state(2) (10 - cube_state(1))];
end

Further, to illustrate the need for these basic operations let us consider an example. Suppose the high level instruction to be executed is F, which means turn the Front face 90 degrees clockwise. Also assume that the cube is currently in a state where the Left side faces the camera and the Front side faces the right side of the cube solver. The video below depicts this scenario.

The cube solver first turns the whole cube left by 90 degrees. This is done as the cube solver can only push the cube against the back wall. Note that the cube solver cannot turn the cube right by 270 degrees, as it is not allowed by a 180 degree rotation servo motor. After turning left, the cube is then flipped forward, which gets the desired cube face ready for manipulation. Finally, the desired face is turned 90 degrees anti-clockwise, using the TurnFaceClock function.

Therefore the high level move F from the Thistlethwaite's 45 Algorithm is translated into TurnCubeLeft -> FlipCubeForward -> TurnFaceClock in this case.

F TurnCubeLeft
FlipCubeForward
TurnFaceClock

Now, that we have covered Thistlethwaite's algorithm and the translation of the high level commands to low level commands using the custom basic operation functions, let us now look at solving the scrambled cube. Both calculating the required moves to solve the scrambled cube and the basic operations to execute them have been combined to create the solvePhysicalCube function. This function accepts the current state of the cube after the different facelet colors have been identified and then uses the Thistlethwaite's algorithm to calculate the high level solution to eventually solve the scrambled cube:

solvePhysicalCube(cube_state, servo_front, servo_back, R);
Raw move B	 Move number: 1 	 Moves remaining: 14
Raw move U	 Move number: 2 	 Moves remaining: 13
Raw move D	 Move number: 3 	 Moves remaining: 12
Raw move B	 Move number: 4 	 Moves remaining: 11
Raw move F'	 Move number: 5 	 Moves remaining: 10
Raw move U2	 Move number: 6 	 Moves remaining: 9
Raw move R2	 Move number: 7 	 Moves remaining: 8
Raw move F2	 Move number: 8 	 Moves remaining: 7
Raw move R2	 Move number: 9 	 Moves remaining: 6
Raw move U2	 Move number: 10 	 Moves remaining: 5
Raw move F2	 Move number: 11 	 Moves remaining: 4
Raw move U2	 Move number: 12 	 Moves remaining: 3
Raw move F2	 Move number: 13 	 Moves remaining: 2
Raw move L2	 Move number: 14 	 Moves remaining: 1
Raw move F2	 Move number: 15 	 Moves remaining: 0

Once this function has executed all the identified moves, the cube is solved! Here is a video of a complete run of the Rubik's Cube solver.