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
    @@neighbors
  end

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)
      end
    end
    @@rotated
  end

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)
    colors.sort.join
  end

  require 'set'
  @@positions = Set.new

  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]])
        end
      end
    end
    @@positions
  end

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] = Piece.new(name.split(''))
      end
    end
    @position_pieces
  end

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
    end
  end

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

  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
      else
        new_position_colors[oldpos] = color
      end
    end
    @position_colors = new_position_colors
    self
  end

  def position
    @position_colors.keys
  end

  def serialize
    @position_colors.keys.sort.map { |position| @position_colors[position] }.join
  end

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

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

  def solved?
    position_pieces.values.inject(true) { |solved, piece| solved && piece.home? }
  end

Cube.new 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?
  end

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)
    position_pieces.keys.select { |pos| !pos.index(color).nil? }
  end

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

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

  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
    end
    self
  end

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]
  end

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

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
    position_pieces.keys.sort.map do |key|
      position_pieces[key].serialize
    end.join(".")
  end

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

  def self.all_colors
    @@neighbors.keys
  end

  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?
      end
    end
  end

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.