Skip to main content
Home
plus.maths.org

Secondary menu

  • My list
  • About Plus
  • Sponsors
  • Subscribe
  • Contact Us
  • Log in
  • Main navigation

  • Home
  • Articles
  • Collections
  • Podcasts
  • Maths in a minute
  • Puzzles
  • Videos
  • Topics and tags
  • For

    • cat icon
      Curiosity
    • newspaper icon
      Media
    • graduation icon
      Education
    • briefcase icon
      Policy

      Popular topics and tags

      Shapes

      • Geometry
      • Vectors and matrices
      • Topology
      • Networks and graph theory
      • Fractals

      Numbers

      • Number theory
      • Arithmetic
      • Prime numbers
      • Fermat's last theorem
      • Cryptography

      Computing and information

      • Quantum computing
      • Complexity
      • Information theory
      • Artificial intelligence and machine learning
      • Algorithm

      Data and probability

      • Statistics
      • Probability and uncertainty
      • Randomness

      Abstract structures

      • Symmetry
      • Algebra and group theory
      • Vectors and matrices

      Physics

      • Fluid dynamics
      • Quantum physics
      • General relativity, gravity and black holes
      • Entropy and thermodynamics
      • String theory and quantum gravity

      Arts, humanities and sport

      • History and philosophy of mathematics
      • Art and Music
      • Language
      • Sport

      Logic, proof and strategy

      • Logic
      • Proof
      • Game theory

      Calculus and analysis

      • Differential equations
      • Calculus

      Towards applications

      • Mathematical modelling
      • Dynamical systems and Chaos

      Applications

      • Medicine and health
      • Epidemiology
      • Biology
      • Economics and finance
      • Engineering and architecture
      • Weather forecasting
      • Climate change

      Understanding of mathematics

      • Public understanding of mathematics
      • Education

      Get your maths quickly

      • Maths in a minute

      Main menu

    • Home
    • Articles
    • Collections
    • Podcasts
    • Maths in a minute
    • Puzzles
    • Videos
    • Topics and tags
    • Audiences

      • cat icon
        Curiosity
      • newspaper icon
        Media
      • graduation icon
        Education
      • briefcase icon
        Policy

      Secondary menu

    • My list
    • About Plus
    • Sponsors
    • Subscribe
    • Contact Us
    • Log in
    • How hard is the Rubik's cube?

      4 July, 2011

      A Rubik's cube, you'll be pleased to hear, can always be solved in at most 20 moves, no matter how badly it was scrambled up to start with. Mathematicians have proved that that's true, and they've also proved that 20 is the best you can do: there are particularly horrible starting positions for which you do need 20 moves. (A move is any twist of any little face.)

      Twenty is the Rubik's cube god's number, so-called for the following reason. Any constructive approach to solving a Rubik's cube requires some sort of method, or algorithm. For example, you might try to solve one side first, then another, and so on. An algorithm that solves the cube in the smallest possible number of moves for any given starting position is called god's algorithm: even if you can't figure out what that algorithm is, god, being omniscient, certainly can. The number of moves that god's algorithm takes from the worst possible starting position is god's number.

      graphs

      A bigger cube

      So far, so good, but what if you're looking at a bigger cube, one that has four little cubes in each row, or five, or six, or even more? What's god's number then? That's an incredibly hard question. Even for the standard 3×3×3 cube there are 43,252,003,274,489,856,000 starting positions of the cube. To work out god's number for the standard cube researchers cleverly exploited the symmetries involved to figure out how to solve it from all these positions, but they still needed the equivalent of 35 years' of computing time on a single computer to crack the problem. A similar approach for bigger cubes would require computing power that goes far beyond what's available today.

      However, a group of researchers from MIT, the University of Waterloo and Tufts University have managed to come up with an approximate answer. They have shown that for large enough numbers n, god's number for an n×n×n cube is proportional to n2/log⁡n. This means that you can find two positive numbers c1 and c2, and a third positive number N so that for all n>N, god's number g(n) satisfies c1n2log⁡n≤g(n)≤c2n2log⁡n.
      graphs

      The blue curve is the graph of n2/log(n) and the red curve is the graph of n2.

      This may seem woefully imprecise, but it gives you a rough idea of the rate at which god's number increases as the cube gets bigger. Computer scientists like these kind of results, because they measure how quickly a problem becomes harder as it gets bigger in size and so give them an idea of the chance a computer has of solving ever-harder levels of the problem in a reasonable amount of time.

      Researchers had already known that god's number for the Rubik's cube is proportional to n2. An n×n×n cube has 6n2 little faces: there are 6 faces of the big cube each of which contains n2 little ones. Solving the cube means manoevering each of these little faces into the right position. It's possible to show that the cube can be solved in a constant number of moves for each little face, which means that the number of moves needed is proportional to 6n2. And since you can ignore constant factors in results about proportionality, this means that god's number is proportional to n2. What's new about the result is the fact that the researchers were able to reduce n2 by a factor of 1/log⁡n. They did this by cleverly exploiting the fact that a sequence of moves can put several little faces into the right position at the same time. The researchers actually give an explicit algorithm for solving a scrambled cube making use of this fact.

      So next time you find yourself confronted with a large and scrambled Rubik's cube, have a look at their paper.

      Read more about...
      Rubik's cube
      • Log in or register to post comments

      Comments

      Tobias

      13 November 2021

      Permalink

      Whom ever wrote this, well done! You have a brilliant mind. Thank you for wording so well, I wish that I was taught with this tool at school.

      • Log in or register to post comments

      Read more about...

      Rubik's cube
      University of Cambridge logo

      Plus Magazine is part of the family of activities in the Millennium Mathematics Project.
      Copyright © 1997 - 2025. University of Cambridge. All rights reserved.

      Terms