## Based on a PIC32 Microcontroller

### Rubik’s cubes are a staple of every puzzle-lover’s collection. Even though they look simple, efficient solutions require very interesting algorithms. These three Cornell students made a self-contained system that guides users through the steps of solving a Rubik’s cube using a PIC32 MCU, with the moves displayed on a TFT.

This project is a self-contained system that guides the user through the steps to solve a Rubik’s cube. The user starts with a solved cube and scrambles it, using a set of moves described in detail in the “GUI Design” section of this article. A PIC32 microcontroller uses this sequence of moves to build a software model of the cube. It then returns a step-by-step solution “moveset.” The returned solution moveset is then displayed on the thin-film transistor (TFT) display for users to read and solve their own cubes. A block diagram of the system is shown in **Figure 1**.

We chose to implement our project on a PIC32 MCU for two reasons. First, we wanted our implementation of the cube model and solving algorithm to be efficient, and using a PIC32 would force this outcome. Second, something is inherently nice about a project being run by only a microcontroller.

##### HARDWARE

Our design contains two hardware peripherals: the TFT display and the UART-to-USB Adafruit serial cable. The TFT displays all the necessary visual information to the user. The UART-to-USB cable connects the PIC32 to the PC running a Python script. The Python script generates the graphical user interface (GUI), and sends serial data to the PIC32. The schematic (**Figure 2**) illustrates the necessary pin connections.

##### SOFTWARE DESIGN

The software is organized into modules: solver, gui, and pic32. The solver module implements the Rubik’s cube solving algorithm and associated state. The gui module implements a Python GUI that runs on a separate computer and allows that computer to communicate serially with the microcontroller. The pic32 module implements hardware-specific code such as the TFT display. We designed, implemented, and tested each module independently. **Figure 3** shows how these modules interact with each other.

##### SOLVER MODULE

** Cube State:** The 26 miniature cubes that make up a full Rubik’s cube are called “cubies.” Every Rubik’s cube has 12 edge cubies that can be in one of two orientations, and eight corner cubies that can be in one of three orientations. Since the six face cubies are not affected by face rotations, we only encode the edge and corner cubies in our cube representation. We encode edge cubies using 5 bits (the first bit encodes orientation, the next 4 bits encode permutation), and corner cubies also using 5 bits (the first 2 bits encode orientation, the next 3 bits encode permutation). Then we encode a cube state with two 64-bit integers. The first integer encodes the 12 edge cubies sequentially, and the second integer encodes the eight corner cubies sequentially. To read the value of an arbitrary cubie, we simply select the appropriate integer and read the orientation and permutation at the index of that cubie, using a bitmask (

**Figure 4**).

Moves cause transformations between cube states. Each move must specify the face of rotation, and whether the rotation is a quarter-turn clockwise, quarter-turn counter-clockwise, or a half-turn. We encoded the face of rotation for a move as a one-hot encoded 6-bit integer (one per face). We encoded the rotation value as a one-hot encoded 2-bit integer, where the rotation is quarter-turn clockwise by default. One bit flag makes the rotation counter-clockwise, and the other bit flag makes the rotation a half-turn. Then we encoded a single move as an 8-bit integer, where the first 2 bits encode information about the rotation value, and the last 6 bits encode information about the face of rotation.

— ADVERTISMENT—

—Advertise Here—

Finally, we implemented a transformation function, which takes a cube state and a move, and returns the new cube state obtained by applying the move to the original cube state (**Figure 5**). Decoding moves is relatively simple given their encoding. Each move requires shifting the permutations of four edges and four corners, which is also relatively simple.

Updating the orientations of the edges and corners was the tricky part that required a lot of trial and error. As it turns out, edges flip their orientation on quarter-turn rotations of two arbitrary opposite faces, which we selected to be the U and D faces. Corners change their orientations on quarter-turn rotations of four arbitrary opposite faces, including the U and D faces. We selected the other pair of opposite faces to be the F and B faces. The value by which corner orientations change depends on which corner they start in on the face of rotation.

Building the cube state model required a lot of testing between incremental improvements. Much of our testing came from taking a solved cube state, applying a random sequence of moves, and printing it to the console. Then we applied the same sequence of moves to a real Rubik’s cube and verified that each of the six faces matched what was predicted on the console. We performed this test hundreds of times on randomly generated sequences of moves before we were convinced our model was working correctly. We also added some automated tests, which verified that communicative moves produced equivalent states, and that certain move sequences, when applied to a solved cube, would produce a solved cube after a pre-computed number of steps.

We went through many different iterations of potential cube state models. We initially chose to represent cubes as a 54-element array, which maps a square on the cube to its color. This turned out to make the actual cube solver much harder to implement, since the algorithm relies on cubie orientations and permutations. Therefore, we found the above model to be most natural for the implementation of the cube solver algorithm.

** Cube Solver:** The Rubik’s cube solving algorithm we chose to implement is an improved version of Thistlethwaite’s algorithm [1]. Thistlethwaite’s original algorithm is guaranteed to find a solution within 52 moves, whereas our improved algorithm can find a solution within 46 moves. Thistlethwaite’s algorithm is an improvement over brute-force search algorithms, which would never terminate in such an overwhelmingly large state space, and over inefficient human algorithms that frequently break properties that are built up in previous stages, while progressing toward the next stage. It is a relatively complicated algorithm that is only practical for computer solving and not for humans to memorize.

Thistlethwaite’s algorithm is best explained via rudimentary group theory. It divides the space of cube states into four nested groups, where a group is defined by a set of moves and contains the set of cube states that can be solved using that set of moves. The algorithm progresses in four phases, where phase i aims to bring a cube from group G(i-1) to group Gi only using the set of moves in group G(i-1). Restricting the set of moves that can be applied to the cubes in a group fixes properties of the cubes that cannot be broken after that group is reached. The four groups of Thistlethwaite’s algorithm are given in **Table 1** and the fixed properties of their cubes are given in Figure 4.

Each phase is implemented as an iterative-deepening, depth-first search (IDDFS) over the state space of cubes in the current group. We implemented a single search function that runs IDDFS once for each phase, and three helper functions that provide phase-specific details to the single search function. Two of these helper functions return the moves and the maximum depth specific to each phase. The third helper function takes a cube state and returns a modified cube state, where everything that isn’t related to the properties being fixed is removed. Essentially, it reduces a cube state to its phase-equivalence class, so two different cube states are considered equal if their phase-specific properties are equal. These helper functions allow the phase-specific details to be factored out of the function that handles IDDFS.

We systematically explored the entire space of cubes in our implementation of Thistlethwaite’s algorithm to determine the maximum depth of each phase. For an arbitrary phase i, we take the solved cube and find its phase-equivalent state in Gi. Then we search the space using BFS using this phase-equivalent state as the first state in the search queue. For each state in the search queue, we apply the moves in Gi to obtain a set of phase-equivalent child states. For each child state, we check if it has already been found in a previous search, and add it to the search queue if it has not. The entire space is explored when there are no remaining states in the search queue.

At this point, we know how many unique states exist in that phase, and the maximum depth of the phase search. Summing the maximum depths of each phase yields the maximum solution length of our algorithm, which is 46. The reason why our maximum solution length is shorter than Thistlethwaite’s original algorithm is that he used simplifying moves for phases 2-4 to reduce the size of his look-up tables. The tables were printed in a 20-page document and scanned manually to solve cubes using his method. Since we are using a computer to generate solutions, we can explore many more states than he could print, and therefore arrive at a shorter solution using his method.

— ADVERTISMENT—

—Advertise Here—

The most constraining feature of the microcontroller in implementing our algorithm was the small memory size. We initially intended to implement the search as a bi-directional BFS, because it would have had to search over much fewer states. But after some basic computations, we realized the microcontroller simply did not have enough memory to support such a search. Instead, we turned to an IDDFS search, because it simulates BFS, ensuring each returned solution has minimal length, and because it runs in linear space. Since the largest branching factor of a search is 18 in phase 1, and the largest possible depth of a search is 15 in phase 4, we only needed to allocate a size of 18×15=270 to the search stack. Each search node uses 24 bytes to store a cube state, parent move, and depth. This means the memory requirements of our IDDFS search is under 6.5KB.

To test the cube solver, we wrote a test function to generate a cube randomly, find a sequence of solution moves using the solver, and apply the sequence of solution moves before verifying that the resulting cube was solved. We ran this function on thousands of randomly generated cubes before we were convinced that the solver generally worked. We also made sure to test the solution sequences on a real Rubik’s cube.

##### GUI MODULE

** GUI Design:** The user interface was designed with ease of use in mind for the user. With only four buttons and one input field, this goal was achieved. To use the GUI, a user types in a defined set of moves that are explained in a user manual. These moves are: F, R, U, B, L, D, F’, R’, U’, B’, L’, D’, F2, R2, U2, B2, L2, D2. This nomenclature can be visualized in Figure 5. A user scrambles a cube and writes down each move made, and inputs these moves into the “Move Input” input field.

Note that the orientation of the Rubik’s cube must remain the same throughout the entire process. Then, the user clicks “Solve” and the solving moves are flashed to the TFT screen of the PIC32. A user can then step forward and backward through the solving moves (**Figure 6**) using the “TFT Controls” buttons. The Python interface also parses the user input in the background before sending it to the PIC32 for processing. When the user clicks “Solve,” the GUI takes the user’s input and turns each move into an element in an array. Each move in the array is converted into an 8-bit binary representation. Finally, the array is encoded and a header, the number of moves, and a terminating character are added. This encoded “package” is then sent to the PIC32 via the UART serial connection.

The next move “>” and the previous move “<” buttons work in the same way as the “Solve” button. Only the header and terminating characters are needed, however, because button differentiation is done with the header characters (**Figure 7**).

##### PIC32 MODULE

** TFT Display:** Our system has three different states of the display. The first state is on the start-up of the system. In this state, the TFT displays the words “Solving Guide,” and waits for the user to start the solving process. The second state occurs after the user has sent in a moveset to be solved. The TFT displays “Solving…” in this state. For simple cube states, this process usually takes no longer than 30 seconds. Once the PIC32 has finished solving the cube, the TFT moves to its final state. In this state, the user is shown the current step number, the move that should be performed, and the move that was performed previously. The user can navigate between moves from the beginning to the end of the solution moveset.

This solution state display is maintained by stepping forward or backward through the solution moveset every time the user presses one of the GUI buttons. We wanted to add a nice message for the user at the end of solving a Rubik’s cube. So, additionally, at the very end of the moveset, if the user presses the next button, the TFT will display “Solved! Congratulations.”

##### POSSIBLE IMPROVEMENTS

Although the cube solver works correctly, its main issue is that it is painfully slow, taking nearly 30 minutes on sufficiently complex cube states. This is because the IDDFS searches the massive state space in essentially a brute-force fashion. The number of nodes IDDFS needs to search increases exponentially with depth. More specifically, the number of nodes n IDDFS needs to search at a depth of d is given by: n=b^d, where b is the branching factor of the tree (that is, the number of moves allowed in the phase). So, if the minimum solution size of a phase is sufficiently long, then IDDFS needs to search a huge number of nodes to discover the solution.

We can make a few improvements to the system in the future to make it run faster.The first improvement is keeping a hash table of visited cube states and pruning them from the search tree if they are encountered again. This would effectively reduce the branching factor of the search tree. For example, in G0 the branching factor would reduce from a hard 18 to about 13, allowing deeper levels of the tree to be accessed more quickly.

Second, a more general improvement would be to generate a look-up table for each state of each phase. The look-up table would be indexed by the phase-equivalent cube state and would store the depth of a solution from that cube state. Then the solving algorithm would simply walk through the look-up table and select the next move as any move that decreases the solution depth. Such an algorithm would run in constant time but also would require generating a look-up table before use. Generating this table would take a substantial amount of time and require considerable space.

##### CONCLUSION

Overall, this project was a great way to learn about microcontroller programming and dealing with constraints. The solving guide is functional, the GUI is simple to use, and the bulk of the work was performed on the PIC32. The memory constraints forced us to write a sophisticated algorithm that was efficient enough to perform on 32KB of RAM, after realizing our first attempt used 2MB. In the end, we met our goal of performing the solution calculation on the PIC32 and were able to convert that into a usable solving guide. The biggest lesson we learned, however, was to simply add more memory.

**REFERENCES**

[1] Thistlethwaite’s algorithm

https://www.jaapsch.net/puzzles/thistle.htm[2] Rubik’s Cube Solver

https://rubiks-cube-solver.com/

**RESOURCES**

Microchip | www.microchip.com

Adafruit | www.adafruit.com

**RESOURCES**

Microchip | www.microchip.com

Adafruit | www.adafruit.com

— ADVERTISMENT—

—Advertise Here—

PUBLISHED IN CIRCUIT CELLAR MAGAZINE • AUGUST 2022 #**38**5 – Get a PDF of the issue

Alexander Drazic is a master's student at Cornell University studying Electrical and Computer Engineering. He is interested in computer networks, telecommunications, and hobby electronics.

Tushar Khan is a Cornell University graduate of Computer Science. He has a variety of academic interests including AI, programming language theory, and mathematics.

Myles Cherebin is a Cornell University graduate of Electrical and Computer Engineering. Some of his technical interests are embedded development and app development.