Google AI


Modern Australian

How hard is it to scramble Rubik’s Cube?

  • Written by: Tim Garoni, Associate Professor, School of Mathematics, Monash University

Rubik’s Cube has been one of the world’s favourite puzzles for 40 years. Several different methods have been devised for solving it, as explained in countless books. Expert “speedcubers” can solve it in a matter of seconds.

In addition to such feats of astounding dexterity, there are many fascinating mathematical questions related to Rubik’s Cube. A move of the cube consists of rotating one of the six faces by either 90, 180, or 270 degrees. A staggering 43,252,003,274,489,856,000 possible states can be obtained by applying sequences of moves to the solved state.

Read more: How to solve a Rubik's cube in five seconds

Despite this complexity, it was shown in 2010 that Rubik’s Cube can always be solved in 20 moves or fewer, regardless of the initial state. This number is referred to as “God’s number”, as all known solution methods used by humans typically use significantly more moves than this optimal value.

How hard is it to scramble Rubik’s Cube? Rubik’s Cube in the solved state. Mike Gonzalez (TheCoffee)

But what about the opposite question: how many moves are required to scramble a solved cube? At first glance, this sounds like a much easier question than computing God’s number. After all, unlike solving a cube, scrambling one takes no skill whatsoever.

Similar questions have been answered successfully for card shuffling. A famous example is the 1990 study of the “riffle shuffle” by mathematicians Dave Bayer and Perci Diaconis. A deck of cards is defined as “mixed” if its ordering is random, with each possible order having the same probability of appearing. Bayer and Diaconis showed that seven riffle shuffles are necessary and sufficient to approximately mix a standard deck of playing cards.

Last year, mathematicians published a similar study of the 15 puzzle, which consists of a 4x4 square filled with 15 sliding tiles and one empty space.

What does it mean for a cube to be scrambled?

A typical person trying to scramble a Rubik’s Cube would repeatedly perform random moves on it. The resulting random sequence of states is a special case of what mathematicians call a Markov chain. The key property is that given the current state, the probability of what the next state will be does not depend on any of the previous states.

Applying the theory of Markov chains to cube scrambling, it follows that as the number of random moves increases, the probability of being in any particular one of the possible states becomes closer and closer to 1/43,252,003,274,489,856,000. Mathematicians call this a “uniform probability distribution”, as each possible state occurs with the same probability.

After any given number of random moves, the state of the cube will be random, but its probability distribution will not be exactly uniform; some states will be more likely to occur than others.

Let d(t) describe how much the probability distribution after t random moves differs from the uniform probability distribution. As the number of random moves (t) increases, the value of d(t) will decrease. The cube being scrambled corresponds to d(t) being small.

Markov-chain Monte Carlo

In the theory of Markov chains, this decrease in d(t) is called “mixing”. Besides card shuffling and puzzle scrambling, the theory of Markov chain mixing also has very serious practical applications. One of the most important computational tools in modern science and engineering is the Monte Carlo method. This method, like the famous casino after which it is named, relies fundamentally on chance. In essence, it attempts to approximately solve hard mathematical problems using multiple random guesses.

In practice, Markov chains are often used to produce these random states. To understand the accuracy of these Markov-chain Monte Carlo methods, the key task is to estimate how quickly d(t) decreases as t increases.

The pocket cube

How hard is it to scramble Rubik’s Cube? Pocket cube in a scrambled state. Mike Gonzalez (TheCoffee)

Studying the scrambling problem for the standard 3x3x3 Rubik’s Cube is currently a fascinating unsolved challenge. However, it becomes quite manageable if we turn our attention to a smaller 2x2x2 version, called the pocket cube.

In this cube, the edge and centre pieces are absent and only the corner pieces remain. The pocket cube has only 3,674,160 possible states, and its God’s number is only 11.

In the graph below, we plot d(t) for the pocket cube. After 11 moves, d(t) is still very large, at 0.695. The first value of t that yields a d(t) value below 0.25 (often called “the mixing time” in Markov chain theory) is 19. After 25 moves d(t) is 0.092; after 50 moves it is 0.0012; and after 100 moves it is 0.00000017.

How hard is it to scramble Rubik’s Cube? Distance of the pocket cube distribution from uniform after t moves. Eric Zhou

So how many moves should you use to fully scramble a pocket cube? The answer depends on how small you would like d(t) to be. However, it is certainly true that God’s number of moves is insufficient. As a bare minimum, one should not use fewer than 19 moves. Further details, including code to compute d(t), are available here.

And of course, once you’ve scrambled your cube, all that’s left to do is solve it again.

Read more: Your guide to solving the next online viral maths problem

Authors: Tim Garoni, Associate Professor, School of Mathematics, Monash University

Read more https://theconversation.com/how-hard-is-it-to-scramble-rubiks-cube-129916

The Fire Safety Checklist Every Australian Short-Stay Host Should Run

Picture an Airbnb guest arriving late, tired, in a place they’ve never been. They don’t know where the exits are, which door leads to the garage, or h...

Better Business Photos Without Misleading Customers: An Australian Guide

A timber dining set looks inviting against a sunny deck, with cushions, lanterns and enough chairs for the whole family. But imagine the retailer sell...

Understanding a dental implant Melbourne Treatment Plan

A dental implant Melbourne patients may consider is one option for replacing a missing tooth, but suitability depends on oral health, bone support a...

How 3PL Logistics Australia Supports Faster and More Efficient Supply Chains

Why Has 3PL Logistics Become Important for Growing Businesses?  Gone are the days when supply chains were simpler and in minimal quantity. Now, the...

Common Skin Concerns and Treatment Options Available in Melbourne

Skin concerns can develop gradually or become noticeable following changes in age, lifestyle, sun exposure or hormonal factors. Pigmentation, rednes...

Why a Code-Compliant Home Can Still Feel Uncomfortable

When people build or renovate a home, they usually expect that meeting current building requirements will also produce a comfortable place to live. ...

Breach of Contract in Business: What Are Your Options?

Contracts are essential to business relationships. They establish expectations, allocate responsibilities and provide a framework for delivering goods...

How Pest Control Companies Can Rank for the Problems Customers Search First

Introduction SEO for Pest Control needs to start with the customer’s problem. Most people do not search for pest services in a neat or technical wa...

What Are the Benefits of Renovating an Older Home in Sydney?

Sydney has plenty of character homes, from Federation cottages to mid-century brick homes. Renovating rather than rebuilding can preserve what makes t...

Pool and Deck Design: How to Plan the Perfect Outdoor Living Space for Your Sydney Home

For many Australians, the backyard is where life happens. Summer barbecues, weekend swims and long evenings outdoors are all part of the lifestyle, ...

Is Solar Pool Heating Worth It? What Sydney Homeowners Should Know

There's nothing quite like a backyard pool on a hot Sydney day. But once autumn rolls in, many pools sit unused for months because the water is simp...

Planning a Luxury House Move: A Week-by-Week Timeline for Prestige Sydney Homes

Selling or buying a prestige home is a major milestone. Whether it's a waterfront residence in Birchgrove, a grand Federation home in Haberfield or ...

Downsizing or Upgrading Your Caravan? Here's How to Sell It Without the Hassle

Selling a caravan can feel like a major task, especially when you are unsure about its value, paperwork, or how to find a buyer. Whether you are dow...

The Best Overseas Adventure Holidays for Australians Who Love the Outdoors

Australia offers no shortage of incredible outdoor experiences, but sometimes the best way to satisfy your sense of adventure is to head overseas. A...

Cape Town Wine Shuttle: Winelands Tasting & Tours

Embark on an unforgettable journey through the picturesque Cape Winelands, where world-class wines and breathtaking scenery await. Our Cape Town Win...

Metal Fabrication: Choosing Metal Fabrication Melbourne Services for Custom Projects

What Modern Metal Fabrication Involves From individual components to complete structures, metal fabrication brings together processes such as desig...

Why Giant Rats Tail Grass Keeps Coming Back After Spraying

Giant Rats Tail Grass (GRT) is one of the most frustrating pasture weeds for farmers and lifestyle property owners. You spray an infested area, see th...

When Custom Cardboard Boxes Make Sense for Your Business

Custom cardboard boxes can be useful when a standard carton does not fit a product, packing method or presentation requirement particularly well. A ...