How do we represent a Rubik’s Cube in memory? There are several different options, each with their own advantages and disadvantages.
Month: August 2017
Finding Optimal Solutions to the Rubik’s Cube – 2. Mathematics
Before we start trying to find optimal solutions to the Rubik’s cube, it would be a good idea to understand how large the search space is. In order to do that, it is helpful to split the analysis into separate pieces. We will separately consider: 1) Permutations of the corner pieces, 2) Orientations of the corner pieces, 3) Permutations of the edge pieces, 4) Orientations of the edge pieces. If we can calculate each of these quantities, we should be able to multiply them together to count the total number of possible combinations.
Finding Optimal Solutions to the Rubik’s Cube – 1. Introduction
The Rubik’s Cube is a 3-dimensional puzzle invented by Erno Rubik in 1974. The puzzle is scrambled by performing a sequence of N rotations of any of the 6 faces. Each rotation will disrupt both the permutation of the edges and corners, as well as the orientation of those pieces. The cube is said to be solved when all colors on each of the 9 pieces of each of the 6 faces match. Our goal, then, is this:
Given a scrambled cube, produce the shortest sequence of rotations necessary to restore the cube to the solved state.