A-Level Computer Science: Imogen F’s Fiendishly Clever Pocket Cube Algorithm
Friday 16 September 2022
ALEX LAMING, HEAD OF COMPUTING
For her A Level Computer Science non-exam assessment, Imogen F (OQ 2022) pursued her passion for the Rubik’s cube by developing a programmed intelligent algorithm to solve a smaller version known as the pocket cube. In order to achieve this Imogen had to liaise with an end user group to develop requirements and analyse the needs of the system. Imogen produced a full design specification and then wrote the solution using the Python programming language.
Imogen demonstrates her amazing ability to solve the Rubik’s cube – November 2020
The brief was to develop a system where the starting positions of a cube could be entered by a user and would then be solvable by a pre-written algorithm which would then show the steps of the solution. To make the program intelligent the cube was to store each solved cube in a file and then compare with these solutions before running the main algorithms to see if the cube had been solved from its starting point already. This was a form of machine learning.
In order to program the cube solver Imogen had to use some highly complex programming theory. Imogen developed a fully object-oriented programming solution in Python which connected with several pre-written library modules such as ‘tkinter’ for the interface development and ‘random’ for the use of random number generation. Imogen also had to develop several data structures to store the positions of the cubes and the moves programmatically and then she deployed a technique called tree traversal to search the possible moves so as to establish the steps to be taken.
The project took Imogen a whole year and involved many technical hurdles to overcome and lots of testing using virtual box software before she got the solution working to perfection. The finished system can solve any cube arrangement entered (which is a huge number of permutations) and prevents illegal entries such as those with uneven numbers of coloured squares (there must be four of each). The finished system went through rigorous testing using a black-box test plan and end user feedback.