{"id":9032,"date":"2022-09-05T21:00:24","date_gmt":"2022-09-06T01:00:24","guid":{"rendered":"https:\/\/blogs.mathworks.com\/cleve\/?p=9032"},"modified":"2022-09-10T14:54:40","modified_gmt":"2022-09-10T18:54:40","slug":"rubiks-cube-superflips-and-gods-number","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/cleve\/2022\/09\/05\/rubiks-cube-superflips-and-gods-number\/","title":{"rendered":"Rubik&#8217;s Cube Superflips and God&#8217;s Number"},"content":{"rendered":"\r\n<div class=\"content\"><!--introduction--><div><ul><li>How hard is it to solve a Rubik's Cube?<\/li><li>When can you say that your Rubik's Cube is completely scrambled?<\/li><li>Why might the answer depend on where you went to school?<\/li><li>What interesting mathematical questions are involved?<\/li><\/ul><\/div><!--\/introduction--><h3>Contents<\/h3><div><ul><li><a href=\"#3c346c42-143c-4ddf-aa1d-d75e75c29b38\">Metrics<\/a><\/li><li><a href=\"#a32fd551-4332-475a-a222-185f9d2ae2d0\">God's number<\/a><\/li><li><a href=\"#eece078d-6a7b-423f-9218-5476dc32fcc1\">Superflip<\/a><\/li><li><a href=\"#e237f0a5-b64d-4df1-a432-d475f0d68ae5\">Q20<\/a><\/li><li><a href=\"#707dbec1-844c-46fe-9ea1-722ae2c4685c\">Q26<\/a><\/li><li><a href=\"#88069ce9-4903-4668-a121-0ba2741eabaa\">Compare<\/a><\/li><\/ul><\/div><h4>Metrics<a name=\"3c346c42-143c-4ddf-aa1d-d75e75c29b38\"><\/a><\/h4><p>The difficulty of solving any configuration of a Rubik's Cube is the smallest number of moves required to return to the intial configuration where each face is showing a single color.<\/p><p>But what, exactly, is a move?  The so-called <i>quarter-turn metric<\/i> says a move is turning any face by 90 degrees.  The <i>half-turn metric<\/i> says turning any face by either 90 or 180 degrees is a single move.  For example, using Singmaster notation and the quarter-turn metric, the sequence \"L L\", which turns the left face twice in the same direction, is two moves.  But in the half-move metric, the sequence becomes \"L2\" and counts as a single move.<\/p><p>Tomas Rokicki, who describes himself as <a href=\"https:\/\/tomas.rokicki.com\">a programmer from Palo Alto<\/a>, provides some history at <a href=\"https:\/\/cube20.org\/qtm\">cube20.org<\/a>.<\/p><p>\r\n<p style=\"margin-left:3ex;\">\r\nIn the early days of cube mathematics, two camps emerged on how to\r\n measure the difficulty of a position. West coast and Stanford\r\n mathematicians, free thinkers all, tended to prefer the half-turn\r\n metric, where any twist of any face, whether 90 degrees, 180 degrees,\r\n or 270 degrees counted as a single move. The east coast crowd,\r\n including MIT, tended to prefer the rigor of the quarter-turn metric,\r\n where a half-turn counted as two moves, since of course it could be\r\n accomplished by two consecutive quarter turns.\r\n<\/p>\r\n<\/p><p>When I began development of a Rubik's Cube simulator, <tt>Qube<\/tt>, I was unaware of this history and, even though I am a devout West-coaster, I just counted quarter-turns.  Now a toggle switch in <tt>Qube<\/tt> allows use of either metric.<\/p><h4>God's number<a name=\"a32fd551-4332-475a-a222-185f9d2ae2d0\"><\/a><\/h4><p>Let <tt>Q<\/tt> denote a cube position,<\/p><p>| <tt>Q<\/tt> | = minimum number of moves to solve <tt>Q<\/tt>,<\/p><p><tt><b>Q<\/b><\/tt> = the set of all possible <tt>Q<\/tt>'s, and<\/p><p><tt>G(<b>Q<\/b>)<\/tt> = maximum over <tt>Q<\/tt> in <b>Q<\/b> of | <tt>Q<\/tt> |.<\/p><p><tt>G(<b>Q<\/b>)<\/tt> is known as \"God's number\". <b>Q<\/b> contains over <tt>4.3*10^19<\/tt> positions, so computing <tt>G(<b>Q<\/b>)<\/tt> is a formidable optimization problem.  The definition of God's number does not require the optimal solution itself, only the number of moves.<\/p><h4>Superflip<a name=\"eece078d-6a7b-423f-9218-5476dc32fcc1\"><\/a><\/h4><p>The <i>superflip<\/i> of Rubik's cube is a configuration where the 8 corners, the 6 face centers, and the cube center show the initial colors, but the 12 edge cubelets have the colors reversed. In 1995, Michael Reid proved that solution of the superflip requires 20 half-turn metric moves. In 2010, Tomas Rokicki and colleagues, using hundreds of computers at Google, carried out a massive computation to prove that no other configuration took more than 20 moves, <a href=\"https:\/\/cube20.org\/qtm\">cube20.org<\/a>. This established that God's number for the half-turn metric is<\/p><p><tt>G(<b>Q<\/b>)<\/tt> = 20<\/p><h4>Q20<a name=\"e237f0a5-b64d-4df1-a432-d475f0d68ae5\"><\/a><\/h4><p>I use <tt>Q20<\/tt> to denote the superflip. Our first animation generates the superflip with 20 moves. A few rotations at the beginning and at the end are shown in more detail so that we can see the rotation matrices involved. A higher resolution video clip is available at this link: <a href=\"https:\/\/blogs.mathworks.com\/cleve\/files\/Q20.mp4\">Q20.mp4<\/a><\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/Q20.gif\" alt=\"\"> <\/p><p>The second animation shows a solution of <tt>Q20<\/tt> in 20 moves obtained by reversing and complementing the generating moves. Reid's proof shows that any other solution requires at least 20 moves. The high resolution clip is: <a href=\"https:\/\/blogs.mathworks.com\/cleve\/files\/Q20solve.mp4\">Q20solve.mp4<\/a><\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/Q20solve.gif\" alt=\"\"> <\/p><p>There are several other configurations that require 20 moves. Any configuration with <tt>G(Q) = 20<\/tt> can be regarded as completely shuffled in the half-turn metric.<\/p><h4>Q26<a name=\"707dbec1-844c-46fe-9ea1-722ae2c4685c\"><\/a><\/h4><p>For the quarter-turn metric, if you combine superflip and a configuration known as <i>fourspot<\/i> you have <tt>Q26<\/tt> . Only 8 corners and two face enters are correct. The edges, four face centers, and the cube center are all reversed. When 180 degree turns are counted as two 90 degree turns, this configuration is generated by 26 moves and solved by reversing and complementing the 26 moves. The high resolution clip is: <a href=\"https:\/\/blogs.mathworks.com\/cleve\/files\/Q26.mp4\">Q26.mp4<\/a><\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/Q26.gif\" alt=\"\"> <\/p><p>In 2014, a massive computation at the Ohio Supercomputer Center by Rokicki and Morley Davidson proved that only <tt>Q26<\/tt> (and its two rotations) required 26 quarter-turn moves  All other configurations need fewer. <a href=\"https:\/\/cube20.org\/qtm\">cube20.org<\/a>. So, this established that God's number for the half-turn metric is<\/p><p><tt>G(<b>Q<\/b>)<\/tt> = 26<\/p><p>The high resolution clip is: <a href=\"https:\/\/blogs.mathworks.com\/cleve\/files\/Q26solve.mp4\">Q26solve.mp4<\/a><\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/Q26solve.gif\" alt=\"\"> <\/p><h4>Compare<a name=\"88069ce9-4903-4668-a121-0ba2741eabaa\"><\/a><\/h4><p>Let's compare <tt>Q20<\/tt> and <tt>Q26<\/tt> by alternating between the two.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/flipper03.gif\" alt=\"\"> <\/p><p>The type 3 corner pieces are the same in <tt>Q20<\/tt> and <tt>Q26<\/tt>, and are in the correct initial position.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/flipper33.gif\" alt=\"\"> <\/p><p>The type 2 edge pieces are also the same in <tt>Q20<\/tt> and <tt>Q26<\/tt>, but are reversed from their initial position.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/flipper22.gif\" alt=\"\"> <\/p><p>All the action is with cubelets of type 0 and type 1. In a real, physical Rubik's Cube, this is one solid piece that holds the Cube together.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"http:\/\/blogs.mathworks.com\/cleve\/files\/flipper01.gif\" alt=\"\"> <\/p><script language=\"JavaScript\"> <!-- \r\n    function grabCode_552a77033bf74984addf11ae10f9bb2e() {\r\n        \/\/ Remember the title so we can use it in the new page\r\n        title = document.title;\r\n\r\n        \/\/ Break up these strings so that their presence\r\n        \/\/ in the Javascript doesn't mess up the search for\r\n        \/\/ the MATLAB code.\r\n        t1='552a77033bf74984addf11ae10f9bb2e ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' 552a77033bf74984addf11ae10f9bb2e';\r\n    \r\n        b=document.getElementsByTagName('body')[0];\r\n        i1=b.innerHTML.indexOf(t1)+t1.length;\r\n        i2=b.innerHTML.indexOf(t2);\r\n \r\n        code_string = b.innerHTML.substring(i1, i2);\r\n        code_string = code_string.replace(\/REPLACE_WITH_DASH_DASH\/g,'--');\r\n\r\n        \/\/ Use \/x3C\/g instead of the less-than character to avoid errors \r\n        \/\/ in the XML parser.\r\n        \/\/ Use '\\x26#60;' instead of '<' so that the XML parser\r\n        \/\/ doesn't go ahead and substitute the less-than character. \r\n        code_string = code_string.replace(\/\\x3C\/g, '\\x26#60;');\r\n\r\n        copyright = 'Copyright 2022 The MathWorks, Inc.';\r\n\r\n        w = window.open();\r\n        d = w.document;\r\n        d.write('<pre>\\n');\r\n        d.write(code_string);\r\n\r\n        \/\/ Add copyright line at the bottom if specified.\r\n        if (copyright.length > 0) {\r\n            d.writeln('');\r\n            d.writeln('%%');\r\n            if (copyright.length > 0) {\r\n                d.writeln('% _' + copyright + '_');\r\n            }\r\n        }\r\n\r\n        d.write('<\/pre>\\n');\r\n\r\n        d.title = title + ' (MATLAB code)';\r\n        d.close();\r\n    }   \r\n     --> <\/script><p style=\"text-align: right; font-size: xx-small; font-weight:lighter;   font-style: italic; color: gray\"><br><a href=\"javascript:grabCode_552a77033bf74984addf11ae10f9bb2e()\"><span style=\"font-size: x-small;        font-style: italic;\">Get \r\n      the MATLAB code <noscript>(requires JavaScript)<\/noscript><\/span><\/a><br><br>\r\n      Published with MATLAB&reg; R2022b<br><\/p><\/div><!--\r\n552a77033bf74984addf11ae10f9bb2e ##### SOURCE BEGIN #####\r\n%% Rubik's Cube Superflips and God's Number\r\n% * How hard is it to solve a Rubik's Cube?\r\n% * When can you say that your Rubik's Cube is completely scrambled?\r\n% * Why might the answer depend on where you went to school?\r\n% * What interesting mathematical questions are involved?\r\n \r\n%% Metrics\r\n% The difficulty of solving any configuration of a Rubik's Cube\r\n% is the smallest number of moves required to return to the intial\r\n% configuration where each face is showing a single color.\r\n%\r\n% But what, exactly, is a move?  The so-called _quarter-turn metric_ says\r\n% a move is turning any face by 90 degrees.  The _half-turn metric_ says\r\n% turning any face by either 90 or 180 degrees is a single move.  For\r\n% example, using Singmaster notation and the quarter-turn metric, the \r\n% sequence \"L L\", which turns the left face twice in the same direction,\r\n% is two moves.  But in the half-move metric, the sequence becomes \"L2\"\r\n% and counts as a single move.\r\n%\r\n% Tomas Rokicki, who describes himself as \r\n% <https:\/\/tomas.rokicki.com a programmer from Palo Alto>, provides\r\n% some history at <https:\/\/cube20.org\/qtm cube20.org>.\r\n%\r\n% <html>\r\n% <p style=\"margin-left:3ex;\">\r\n% In the early days of cube mathematics, two camps emerged on how to \r\n%  measure the difficulty of a position. West coast and Stanford \r\n%  mathematicians, free thinkers all, tended to prefer the half-turn\r\n%  metric, where any twist of any face, whether 90 degrees, 180 degrees, \r\n%  or 270 degrees counted as a single move. The east coast crowd, \r\n%  including MIT, tended to prefer the rigor of the quarter-turn metric, \r\n%  where a half-turn counted as two moves, since of course it could be \r\n%  accomplished by two consecutive quarter turns.\r\n% <\/p>\r\n% <\/html>\r\n%\r\n% When I began development of a Rubik's Cube simulator, |Qube|,\r\n% I was unaware of this history and, even though I am a devout\r\n% West-coaster, I just counted quarter-turns.  Now a toggle switch in \r\n% |Qube| allows use of either metric.\r\n\r\n%% God's number\r\n% Let |Q| denote a cube position, \r\n%\r\n% | |Q| | = minimum number of moves to solve |Q|,\r\n% \r\n% |*Q*| = the set of all possible |Q|'s, and\r\n%\r\n% |G(*Q*)| = maximum over |Q| in *Q* of | |Q| |.\r\n%\r\n% |G(*Q*)| is known as \"God's number\".\r\n% *Q* contains over |4.3*10^19| positions, so computing |G(*Q*)| is a\r\n% formidable optimization problem.  The definition of God's number does\r\n% not require the optimal solution itself, only the number of moves.\r\n\r\n%% Superflip\r\n% The _superflip_ of Rubik's cube is a configuration where the 8 corners,\r\n% the 6 face centers, and the cube center show   \r\n% the initial colors, but the 12 edge cubelets have the colors reversed.\r\n% In 1995, Michael Reid proved that solution of the superflip requires\r\n% 20 half-turn metric moves. In 2010, Tomas Rokicki and colleagues,\r\n% using hundreds of computers at Google, carried out a massive computation\r\n% to prove that no other configuration took more than 20 moves,\r\n% <https:\/\/cube20.org\/qtm cube20.org>.\r\n% This established that God's number for the half-turn metric is\r\n%\r\n% |G(*Q*)| = 20\r\n%\r\n\r\n%% Q20\r\n% I use |Q20| to denote the superflip. \r\n% Our first animation generates the superflip with 20 moves.\r\n% A few rotations at the beginning and at the end are shown in more\r\n% detail so that we can see the rotation matrices involved.\r\n% A higher resolution video clip is available at this link:\r\n% <https:\/\/blogs.mathworks.com\/cleve\/files\/Q20.mp4 Q20.mp4>\r\n%\r\n% <<Q20.gif>>\r\n%\r\n\r\n%%\r\n% The second animation shows a solution of |Q20| in 20 moves obtained\r\n% by reversing and complementing the generating moves.\r\n% Reid's proof shows that any other solution requires at least 20 moves.\r\n% The high resolution clip is:\r\n% <https:\/\/blogs.mathworks.com\/cleve\/files\/Q20solve.mp4 Q20solve.mp4>\r\n%\r\n% <<Q20solve.gif>>\r\n%   \r\n% There are several other configurations that require 20 moves.\r\n% Any configuration with |G(Q) = 20| can be regarded as completely\r\n% shuffled in the half-turn metric.\r\n\r\n%% Q26\r\n% For the quarter-turn metric,\r\n% if you combine superflip and a configuration known as _fourspot_\r\n% you have |Q26| .\r\n% Only 8 corners and two face enters are correct.\r\n% The edges, four face centers, and the cube center are all reversed.\r\n% When 180 degree turns are counted as two 90 degree turns,\r\n% this configuration is generated by 26 moves and solved by reversing\r\n% and complementing the 26 moves.\r\n% The high resolution clip is:\r\n% <https:\/\/blogs.mathworks.com\/cleve\/files\/Q26.mp4 Q26.mp4>\r\n%\r\n% <<Q26.gif>>\r\n%\r\n% In 2014, a massive computation at the Ohio Supercomputer Center\r\n% by Rokicki and Morley Davidson proved that only |Q26| (and its two\r\n% rotations) required 26 quarter-turn moves  All other configurations\r\n% need fewer.\r\n% <https:\/\/cube20.org\/qtm cube20.org>.\r\n% So, this established that God's number for the half-turn metric is\r\n%\r\n% |G(*Q*)| = 26\r\n%\r\n% The high resolution clip is:\r\n% <https:\/\/blogs.mathworks.com\/cleve\/files\/Q26solve.mp4 Q26solve.mp4>\r\n%\r\n% <<Q26solve.gif>>\r\n%\r\n\r\n%% Compare\r\n% Let's compare |Q20| and |Q26| by alternating between the two.\r\n%\r\n% <<flipper03.gif>>\r\n%\r\n\r\n%%\r\n% The type 3 corner pieces are the same in |Q20| and |Q26|,\r\n% and are in the correct initial position.\r\n%\r\n% <<flipper33.gif>>\r\n%\r\n\r\n%%\r\n% The type 2 edge pieces are also the same in |Q20| and |Q26|,\r\n% but are reversed from their initial position.\r\n%\r\n% <<flipper22.gif>>\r\n%\r\n\r\n%%\r\n% All the action is with cubelets of type 0 and type 1.\r\n% In a real, physical Rubik's Cube, this is one solid piece that holds\r\n% the Cube together.\r\n%\r\n% <<flipper01.gif>>\r\n%\r\n%\r\n##### SOURCE END ##### 552a77033bf74984addf11ae10f9bb2e\r\n-->","protected":false},"excerpt":{"rendered":"<div class=\"overview-image\"><img src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/flipper03.gif\" class=\"img-responsive attachment-post-thumbnail size-post-thumbnail wp-post-image\" alt=\"\" decoding=\"async\" loading=\"lazy\" \/><\/div><!--introduction--><div><ul><li>How hard is it to solve a Rubik's Cube?<\/li><li>When can you say that your Rubik's Cube is completely scrambled?<\/li><li>Why might the answer depend on where you went to school?<\/li><li>What interesting mathematical questions are involved?<\/li><\/ul><\/div><!--\/introduction-->... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/cleve\/2022\/09\/05\/rubiks-cube-superflips-and-gods-number\/\">read more >><\/a><\/p>","protected":false},"author":78,"featured_media":9167,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[32,5,23,6,47],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/9032"}],"collection":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/users\/78"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/comments?post=9032"}],"version-history":[{"count":10,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/9032\/revisions"}],"predecessor-version":[{"id":9164,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/9032\/revisions\/9164"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/media\/9167"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/media?parent=9032"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/categories?post=9032"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/tags?post=9032"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}