Representing Rubik's Cube

I owned a Rubik’s Cube but never learned to solve it. I can get two “layers” in place, and I have been told that I am on the path to a solution, but I could never complete the third layer.

Over the summer, there was a bit of press about Rubik’s Cube. Using servers donated by Google, researchers proved that any cube could be solved in at most 20 moves.

I recently interviewed to teach an algorithms course at Lewis & Clark College. The interview included teaching an advanced algorithms class for an hour. While preparing, I became intrigued with the idea of representing Rubik’s Cube and having the computer solve it.

After about eight hours (spread over four days and nights) of trying different representations, I settled on a good one in Ruby.

The first thing to note is that each face has a center. The centers never move, so the relationships between the centers never change. I represented this with a class variable and an instance method to access it:

  @@neighbors = {
    "w" => %w(r b o g),
    "r" => %w(y b w g),
    "y" => %w(o b r g),
    "o" => %w(w b y g),
    "g" => %w(y r w o),
    "b" => %w(w r y o)

  def neighbors

A move is a rotation around one of the six centers. A counterclockwise rotation is a sequence of three clockwise rotations. (When you play with a cube, you might think about “rotating the middle layer,” but this is nothing but rotating one face clockwise and the other face counterclockwise.)

When a piece rotates around a center, its neighbors get substituted with new ones. I could have hard-coded the new neighbors, too, but I thought it more expressive to compute and then cache them instead:

  @@rotated = {}

  def rotated
    if @@rotated.empty?
      neighbors.each_pair do |color, color_neighbors|
        @@rotated[color] = color_neighbors.dup
        @@rotated[color] = @@rotated[color].unshift(@@rotated[color].pop)

When you make a move, pieces move from one position to another. Because the relationships between centers are fixed, each position can be uniquely identified by a set (unordered) of colors. A pair of colors identifies “side” positions, and a triple of colors identifies “corner” positions. There are 20 such positions:

  def canonical_key(colors)

  require 'set'
  @@positions =

  def positions
    if @@positions.empty?
      neighbors.each_pair do |color, color_neighbors|
        color_neighbors.each_with_index do |neighbor, index|
          @@positions < < canonical_key([color, neighbor])
          @@positions << canonical_key([color, neighbor, color_neighbors[(index + 1) % color_neighbors.length]])

A piece can similarly be identified by a set of colors.

You might think a cube can be represented by mapping twenty position sets to twenty piece sets. (I went down this path.) However, this is not sufficient information to fully represent the cube, because a piece may be in a position in various orientations, and you need to represent that. A side piece in a given position could be in two orientations, and a corner piece could be in three orientations.

To capture the orientation of the piece, I represent the piece as a mapping from position colors to piece colors. A piece is in its solved position if each of its position colors maps to the same piece color (an identity map). A piece is in its solved position but in the wrong orientation if the domain (position) set and range (piece) set are identical but the mapping is not an identity mapping.

The following code creates a mapping from the 20 positions to the pieces occupying each position.

  def position_pieces
    if @position_pieces.empty?
      positions.each do |name|
        @position_pieces[name] =''))

A Piece can tell if it’s home. The rotate() method simply substitutes position elements from olds with corresponding elements from news.

class Piece
  def initialize(position)
    @position_colors = {}
    position.each do |color|
      @position_colors[color] = color

  def home?
    @position_colors.keys.inject(true) { |current, position| current && (@position_colors[position] == position) }

  def rotate(olds, news)
    new_position_colors = {}
    @position_colors.each_pair do |oldpos, color|
      if (index = olds.index(oldpos))
        new_position_colors[news[index]] = color
        new_position_colors[oldpos] = color
    @position_colors = new_position_colors

  def position

  def serialize { |position| @position_colors[position] }.join

  def deserialize(colors)
    @position_colors.keys.sort.each_with_index do |position, index|
      @position_colors[position] = colors.split('')[index]

The cube is solved if all of its pieces are home.

  def solved?
    position_pieces.values.inject(true) { |solved, piece| solved && piece.home? }
  end returns a new cube in its solved (home) position.

After a bit of experimentation, I found it useful for the cube to maintain its history of rotations:

  attr_reader :history

  def initialize
    @position_pieces = {}
    @history = []
    yield self if block_given?

A move is made by calling rotate_ccw() or rotate_cw() on the cube and passing them the color of the axis to rotate around. To rotate a face of the cube around a color, we find positions neighboring that color. For each of these, we retrieve the piece occupying the position and assign it to its new position.

  def positions_neighboring(color) { |pos| !pos.index(color).nil? }

  def rotate_ccw(color)
    @history < < [:rotate_ccw, color]
    rotate(color, rotated[color], neighbors[color])

  def rotate_cw(color)
    @history << [:rotate_cw, color]
    rotate(color, neighbors[color], rotated[color])

  def rotate(color, from, to)
    # for each position neighboring the color
    neighboring_positions = positions_neighboring(color)
    positions_neighboring(color).map do |pos|
      # find the piece occupying the position
      # assign the piece to the rotated position
      position_pieces[pos].rotate(from, to)
    end.each do |piece|
      position_pieces[canonical_key(piece.position)] = piece

You can call unsolve() on the cube to scramble it by a random number of moves between 10 and 30. That method also has an optional parameter for how many moves to scramble it by. For each scrambling move, it simply chooses a random color and calls rotate_cw() with that color.

  def random_color
    neighbors.keys[(rand * neighbors.keys.length).to_i]

  def unsolve(moves = ((rand * 20).to_i + 10))
    # a random number of times
    moves.times do
      # choose a random color
      # rotate

To write a breadth-first search to solve the cube, I had to be able to persist the state of a cube. To avoid repeating positions that have already been tried, I needed a way to quickly compare one state to another. I decided to serialize and deserialize a cube to/from a string.

Other than not repeating positions that have already been tried, breadth-first search is a brute-force method and probably needs some optimizations. I find that cubes scrambled by more than six moves take a long time to solve.

  def serialize do |key|

  def self.deserialize(string)
    names = string.split('.') do |c|
      c.position_pieces.keys.sort.each_with_index do |key, index|

  def self.all_colors

  def solve
    processed = []
    solved = false
    # put the current state on the list
    to_visit = [serialize()]
    # While the list is nonempty
    while to_visit.length > 0 && !solved
      processed_state = to_visit.pop
      processed < < processed_state
      # For each rotated state
      Cube.all_colors.each do |color|
        rotated_cube = Cube.deserialize(processed_state).rotate_ccw(color)
        rotated_state = rotated_cube.serialize()
        puts "#{color} : #{rotated_state}"
        # If it is not on the list, put it on the end of the list
        to_visit.insert(0, rotated_state) unless (to_visit.include?(rotated_state) || processed.include?(rotated_state))
        # If it is a solved state, find the path to the current state
        solved ||= rotated_cube.solved?

Because this is using a breadth-first search, it can find the shortest path to a solution. The next step is to store the path from the initial cube to the solution.

Tags: Fun, Technical

Created at: 16 October 2010 7:10 AM