{"id":2292,"date":"2017-02-06T12:00:40","date_gmt":"2017-02-06T17:00:40","guid":{"rendered":"https:\/\/blogs.mathworks.com\/cleve\/?p=2292"},"modified":"2017-02-03T16:14:20","modified_gmt":"2017-02-03T21:14:20","slug":"patience-chinese-rings-puzzle","status":"publish","type":"post","link":"https:\/\/blogs.mathworks.com\/cleve\/2017\/02\/06\/patience-chinese-rings-puzzle\/","title":{"rendered":"Patience Chinese Rings Puzzle"},"content":{"rendered":"<div class=\"content\"><!--introduction--><p>MIT's Professor Daniel Frey recently introduced me to an ancient mechanical puzzle known as \"Chinese Rings\", \"Patience\", or \"Baguenaudier.\"  I have modified Daniel's simulator to produce a new app. The state space of the puzzle forms a hypercube.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/patience_puzzle.jpg\" alt=\"\"> <\/p><!--\/introduction--><h3>Contents<\/h3><div><ul><li><a href=\"#843044b3-d3d5-4087-843f-62df243cfc6e\">Background<\/a><\/li><li><a href=\"#582ae349-ed0b-4044-87d7-2359cd610d2a\">Puzzle<\/a><\/li><li><a href=\"#fa2e7737-6095-4491-b122-b738c86ac2bb\">State<\/a><\/li><li><a href=\"#1470a47e-815c-44b6-b7b7-c065c4df609f\">Rule<\/a><\/li><li><a href=\"#f49bfca9-a5b8-43a8-8441-5bea3a258647\">Shortest Path<\/a><\/li><li><a href=\"#36f10905-0e3f-463f-ade0-2bce32234390\">Plot<\/a><\/li><li><a href=\"#4818938a-d0b4-4548-8c15-5edae05f8446\">Lengths<\/a><\/li><li><a href=\"#7746ac04-d1e5-42ba-83bd-8d67ea29583f\">Hypercubes and Graphs<\/a><\/li><li><a href=\"#a0648013-3815-498a-84cf-ab960749de56\">Code<\/a><\/li><li><a href=\"#6eabc33b-b80a-46b4-b91f-7f887c988ff2\">Thanks<\/a><\/li><\/ul><\/div><h4>Background<a name=\"843044b3-d3d5-4087-843f-62df243cfc6e\"><\/a><\/h4><p>There are dozens of YouTube videos showing solutions and speed contests for the tavern puzzle called \"Patience\".  The best video is by Ty Yann, \"Baguenaudier Chinese Rings.\"  Here is the link to his <a href=\"https:\/\/www.youtube.com\/watch?v=qtkvROd1YLY\">puzzle tutorial<\/a>.<\/p><p>Wikipedia tell us that <i>Baguenaudier<\/i> is French for \"time-waster\".<\/p><p>Prof. Frey has written a nice MATLAB simulator for his course this spring at MIT, <a href=\"http:\/\/catalog.mit.edu\/search\/?search=2.086\">2.086<\/a>, \"Numerical Computation for Mechanical Engineers.\" My new app is based on his program.<\/p><h4>Puzzle<a name=\"582ae349-ed0b-4044-87d7-2359cd610d2a\"><\/a><\/h4><p>The puzzle has six steel hooks, often made from nails, attached to a base.  A steel ring is attached to each hook.  A long movable piece known as the shuttle is initially threaded around the nails and through the rings.  The objective is to free the shuttle.  It ain't easy.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/capture_trim.png\" alt=\"\"> <\/p><p>Image credit: Daniel Frey, MIT<\/p><p>My new interactive app, <tt>patience<\/tt>, is included with version 2.2 of <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/59085-cleve-laboratory\">Cleve's Laboratory<\/a> in MATLAB Central.  I hope you will try to solve the puzzle yourself before you resort to the \"no patience\" automated solve button.  The following animated gif shows several steps at the start of the solution, then skips many intermediate steps before showing the last several.<\/p><p><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/patience.gif\" alt=\"\"> <\/p><h4>State<a name=\"fa2e7737-6095-4491-b122-b738c86ac2bb\"><\/a><\/h4><p>The position of the six hooks, up or down, provides a six-bit binary number that characterizes the state of the mechanism.  Initially, the rings are all engaged, so the state in binary is <tt>000000<\/tt>, which, of course, is a decimal 0.  The objective is to free all the rings, giving a binary <tt>111111<\/tt>, or decimal 63.  The app shows the decimal value at each step in the figure title.<\/p><p>The hooks are numbered from 1 through 6 starting on the left. So, we will use \"big endian\" binary, with the least significant bit at the left.<\/p><h4>Rule<a name=\"1470a47e-815c-44b6-b7b7-c065c4df609f\"><\/a><\/h4><p>This one line in <tt>patience.m<\/tt>, which refers to the state vector <tt>S<\/tt> and a hook number <tt>n<\/tt>, controls the possible moves.<\/p><pre class=\"codeinput\">   dbtype <span class=\"string\">52:53<\/span> <span class=\"string\">patience<\/span>\r\n<\/pre><pre class=\"codeoutput\">\r\n52            % Is the move allowed ?\r\n53            ok = (n==1) || (n==2)&amp;&amp;~S(1) || (n&gt;2)&amp;&amp;(~S(n-1)&amp;&amp;all(S(1:n-2)));\r\n<\/pre><p>The rule says<\/p><div><ul><li>Hook 1 can always be toggled.<\/li><li>Hook 2 can be toggled if hook 1 is up.<\/li><li>Any hook numbered 3 through 6 can be toggled if the hook immediately   to its left is up and all the others before it are down.<\/li><\/ul><\/div><p>That's all you need to know to operate the puzzle.<\/p><p>It turns out that at any step at most two, and sometimes only one, of the six hooks is a legal move.<\/p><p>For example, if the state is<\/p><pre class=\"language-matlab\">S = [1 1 0 0 1 0]\r\n<\/pre><p>there are two possible moves.  You can click on hook 1 to give<\/p><pre class=\"language-matlab\">S = [0 1 0 0 1 0]\r\n<\/pre><p>Or, you can click on hook 4 to give<\/p><pre class=\"language-matlab\">S = [1 1 0 1 1 0]\r\n<\/pre><h4>Shortest Path<a name=\"f49bfca9-a5b8-43a8-8441-5bea3a258647\"><\/a><\/h4><p>The optimum path from a given starting state, such as 0, to the goal, 63, can be found by a brute force recursive search that tries all possible moves at each step.  The code is at the end of this post. Here is the shortest path from 0 to 63.<\/p><pre class=\"codeinput\">   path = shortest_path(0)\r\n<\/pre><pre class=\"codeoutput\">path =\r\n  Columns 1 through 13\r\n     0     2     3    11    10     8     9    13    12    14    15    47    46\r\n  Columns 14 through 26\r\n    44    45    41    40    42    43    35    34    32    33    37    36    38\r\n  Columns 27 through 39\r\n    39    55    54    52    53    49    48    50    51    59    58    56    57\r\n  Columns 40 through 43\r\n    61    60    62    63\r\n<\/pre><p>Notice that a shortest path never repeats any state because if we find ourselves reaching a state that we've already visited, we could shorten that path by skipping the extra steps.<\/p><p>It turns out that the only starting state that visits all vertices is <tt>31 = [1 1 1 1 1 0]<\/tt>, which corresponds to starting with the sixth hook up and all the others down.<\/p><p>Each step changes the state by a power of two. You can recover the sequence of mouse clicks that would generate this path by taking the log2 of the changes.<\/p><pre class=\"codeinput\">   hooks = log2(abs(diff(path))) + 1\r\n<\/pre><pre class=\"codeoutput\">hooks =\r\n  Columns 1 through 13\r\n     2     1     4     1     2     1     3     1     2     1     6     1     2\r\n  Columns 14 through 26\r\n     1     3     1     2     1     4     1     2     1     3     1     2     1\r\n  Columns 27 through 39\r\n     5     1     2     1     3     1     2     1     4     1     2     1     3\r\n  Columns 40 through 42\r\n     1     2     1\r\n<\/pre><h4>Plot<a name=\"36f10905-0e3f-463f-ade0-2bce32234390\"><\/a><\/h4><p>Let's plot the decimal value of the state for the shortest path from 0 to 63.  Here is the progress of this value over the 42 steps. The even numbered steps involve toggling the first hook, which changes the value of the state by plus or minus one.  The sixth hook is moved only once, at step 11, changing the value by +32.  The fifth hook contributes its +16 at step 28.<\/p><pre class=\"codeinput\">   plot_path\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/patience_blog_01.png\" alt=\"\"> <h4>Lengths<a name=\"4818938a-d0b4-4548-8c15-5edae05f8446\"><\/a><\/h4><p>Here are the lengths of the shortest paths from each starting position.<\/p><pre class=\"codeinput\">   L = zeros(64,1);\r\n   <span class=\"keyword\">for<\/span> n = 0:63\r\n       L(n+1) = length(shortest_path(n));\r\n   <span class=\"keyword\">end<\/span>\r\n   bar(L)\r\n<\/pre><img decoding=\"async\" vspace=\"5\" hspace=\"5\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/patience_blog_two.png\" alt=\"\"> <h4>Hypercubes and Graphs<a name=\"7746ac04-d1e5-42ba-83bd-8d67ea29583f\"><\/a><\/h4><p>The puzzle's state lives in a six-dimensional space. There are 64 vertices, numbered 0 from to 63.  Each vertex is connected to the six vertices whose numbers, expressed in binary, differ from its own by one bit.  That connectivity arrangement -- those vertices and the connections between them -- form a <i>graph<\/i> known as a <i>hypercube<\/i>.<\/p><p>Recent versions of MATLAB include methods for a new object, the <i>graph<\/i>. I plan to discuss hypercubes and graphs in my next blog post.<\/p><h4>Code<a name=\"a0648013-3815-498a-84cf-ab960749de56\"><\/a><\/h4><p>Here is the code for the recursive search that finds the shortest path. The code for the complete <tt>patience<\/tt> app is now included with <a href=\"https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/59085-cleve-laboratory\">Cleve's Laboratory<\/a> in MATLAB Central.<\/p><pre class=\"codeinput\">   type <span class=\"string\">shortest_path<\/span>\r\n<\/pre><pre class=\"codeoutput\">\r\nfunction path = shortest_path(state,m,path)\r\n% shortest_path, or shortest_path(state), where state is a decimal state \r\n% value  between 0 and 63, is the shortest path of allowable puzzle moves\r\n% from that state to the objective, 63.\r\n%\r\n% shortest_path(S,m,path) is the recursive call.\r\n\r\n        if nargin == 0\r\n            state = 0;  % Default\r\n        end\r\n        if nargin &lt;= 1\r\n            % Initial call\r\n            m = 0;  % Previous n\r\n            path = [];\r\n        end\r\n        if state == 63  % Terminate recursion\r\n            path = state;\r\n            return\r\n        end\r\n        if state == 31\r\n            m = 0;\r\n        end\r\n        % Search for shortest path\r\n        pow2 = 2.^(0:5);\r\n        lmin = inf;\r\n        for n = [1:m-1 m+1:6]\r\n            Sn = mod(floor(state.\/pow2),2);  % Convert state to binary\r\n            Sn(n) = ~Sn(n);  % Flip one bit\r\n            ok = (n==1) || (n==2)&amp;&amp;~Sn(1) || ...\r\n                 (n&gt;2)&amp;&amp;(~Sn(n-1)&amp;&amp;all(Sn(1:n-2)));  % Allowable move\r\n            if ok\r\n                staten = Sn*pow2';\r\n                % Recursive call\r\n                pn = shortest_path(staten,n,[path staten]);\r\n                if length(pn) &lt; lmin\r\n                    lmin = length(pn);\r\n                    pbest = pn;\r\n                end\r\n            end\r\n        end\r\n        path = [state pbest];\r\nend % shortest_path\r\n<\/pre><h4>Thanks<a name=\"6eabc33b-b80a-46b4-b91f-7f887c988ff2\"><\/a><\/h4><p>Thanks to Daniel Frey.<\/p><script language=\"JavaScript\"> <!-- \r\n    function grabCode_ea254cadff30471a9559c21c69c9f659() {\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='ea254cadff30471a9559c21c69c9f659 ' + '##### ' + 'SOURCE BEGIN' + ' #####';\r\n        t2='##### ' + 'SOURCE END' + ' #####' + ' ea254cadff30471a9559c21c69c9f659';\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 2017 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_ea254cadff30471a9559c21c69c9f659()\"><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; R2017a<br><\/p><\/div><!--\r\nea254cadff30471a9559c21c69c9f659 ##### SOURCE BEGIN #####\r\n%% Patience Chinese Rings Puzzle\r\n% MIT's Professor Daniel Frey recently introduced me to an ancient\r\n% mechanical puzzle known as \"Chinese Rings\", \"Patience\", or\r\n% \"Baguenaudier.\"  I have modified Daniel's simulator to produce a new app.\r\n% The state space of the puzzle forms a hypercube.  \r\n%\r\n% <<patience_puzzle.jpg>>\r\n\r\n%% Background\r\n% There are dozens of YouTube videos showing solutions and speed contests\r\n% for the tavern puzzle called \"Patience\".  The best video is by Ty Yann, \r\n% \"Baguenaudier Chinese Rings.\"  Here is the link to his\r\n% <https:\/\/www.youtube.com\/watch?v=qtkvROd1YLY puzzle tutorial>.\r\n\r\n%%\r\n% Wikipedia tell us that _Baguenaudier_ is French for \"time-waster\".\r\n\r\n%%\r\n% Prof. Frey has written a nice MATLAB simulator for his course this spring\r\n% at MIT, <http:\/\/catalog.mit.edu\/search\/?search=2.086 2.086>, \r\n% \"Numerical Computation for Mechanical Engineers.\"\r\n% My new app is based on his program.\r\n\r\n%% Puzzle\r\n% The puzzle has six steel hooks, often made from nails, attached to a\r\n% base.  A steel ring is attached to each hook.  A long movable piece\r\n% known as the shuttle is initially threaded around the nails and through\r\n% the rings.  The objective is to free the shuttle.  It ain't easy.\r\n%\r\n% <<capture_trim.png>>\r\n%\r\n% Image credit: Daniel Frey, MIT\r\n\r\n%%\r\n% My new interactive app, |patience|, is included with version 2.2 of\r\n% <https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/59085-cleve-laboratory\r\n% Cleve's Laboratory> in MATLAB Central.  I hope you will try to solve the\r\n% puzzle yourself before you resort to the \"no patience\" automated solve\r\n% button.  The following animated gif shows several steps at the start of\r\n% the solution, then skips many intermediate steps before showing the\r\n% last several.\r\n%\r\n% <<patience.gif>>\r\n\r\n%% State\r\n% The position of the six hooks, up or down, provides a six-bit binary\r\n% number that characterizes the state of the mechanism.  Initially,\r\n% the rings are all engaged, so the state in binary is |000000|, which,\r\n% of course, is a decimal 0.  The objective is to free all the rings,\r\n% giving a binary |111111|, or decimal 63.  The app shows the decimal\r\n% value at each step in the figure title.\r\n\r\n%%\r\n% The hooks are numbered from 1 through 6 starting on the left.\r\n% So, we will use \"big endian\" binary, with the least significant bit\r\n% at the left.\r\n\r\n%% Rule\r\n% This one line in |patience.m|, which refers to the state vector |S|\r\n% and a hook number |n|, controls the possible moves.\r\n\r\n   dbtype 52:53 patience\r\n   \r\n%% \r\n% The rule says\r\n%\r\n% * Hook 1 can always be toggled.\r\n% * Hook 2 can be toggled if hook 1 is up.\r\n% * Any hook numbered 3 through 6 can be toggled if the hook immediately\r\n%   to its left is up and all the others before it are down.\r\n%\r\n% That's all you need to know to operate the puzzle.\r\n\r\n%%\r\n% It turns out that at any step at most two, and sometimes only one,\r\n% of the six hooks is a legal move.\r\n\r\n%%\r\n% For example, if the state is\r\n%\r\n%   S = [1 1 0 0 1 0]\r\n%\r\n% there are two possible moves.  You can click on hook 1 to give\r\n%\r\n%   S = [0 1 0 0 1 0]\r\n%\r\n% Or, you can click on hook 4 to give\r\n%\r\n%   S = [1 1 0 1 1 0]\r\n%\r\n\r\n%% Shortest Path\r\n% The optimum path from a given starting state, such as 0, to the\r\n% goal, 63, can be found by a brute force recursive search that tries\r\n% all possible moves at each step.  The code is at the end of this post.\r\n% Here is the shortest path from 0 to 63.\r\n\r\n   path = shortest_path(0)\r\n   \r\n%%\r\n% Notice that a shortest path never repeats any state because if we find\r\n% ourselves reaching a state that we've already visited, we could \r\n% shorten that path by skipping the extra steps.\r\n\r\n%%\r\n% It turns out that the only starting state that visits all vertices is\r\n% |31 = [1 1 1 1 1 0]|, which corresponds to starting with the sixth\r\n% hook up and all the others down.\r\n\r\n%%\r\n% Each step changes the state by a power of two.\r\n% You can recover the sequence of mouse clicks that would generate\r\n% this path by taking the log2 of the changes.\r\n\r\n   hooks = log2(abs(diff(path))) + 1\r\n\r\n%% Plot\r\n% Let's plot the decimal value of the state for the shortest path\r\n% from 0 to 63.  Here is the progress of this value over the 42 steps.\r\n% The even numbered steps involve toggling\r\n% the first hook, which changes the value of the state by plus or minus\r\n% one.  The sixth hook is moved only once, at step 11, changing the\r\n% value by +32.  The fifth hook contributes its +16 at step 28.\r\n\r\n   plot_path\r\n   \r\n%% Lengths\r\n% Here are the lengths of the shortest paths from each starting position.\r\n\r\n   L = zeros(64,1);\r\n   for n = 0:63\r\n       L(n+1) = length(shortest_path(n));\r\n   end\r\n   bar(L)\r\n\r\n%% Hypercubes and Graphs\r\n% The puzzle's state lives in a six-dimensional space.\r\n% There are 64 vertices, numbered 0 from to 63.  Each vertex is\r\n% connected to the six vertices whose numbers, expressed in binary,\r\n% differ from its own by one bit.  That connectivity arrangement REPLACE_WITH_DASH_DASH\r\n% those vertices and the connections between them REPLACE_WITH_DASH_DASH form a _graph_\r\n% known as a _hypercube_.\r\n\r\n%%\r\n% Recent versions of MATLAB include methods for a new object, the _graph_.\r\n% I plan to discuss hypercubes and graphs in my next blog post.\r\n\r\n%% Code\r\n% Here is the code for the recursive search that finds the shortest path.\r\n% The code for the complete |patience| app is now included with\r\n% <https:\/\/www.mathworks.com\/matlabcentral\/fileexchange\/59085-cleve-laboratory\r\n% Cleve's Laboratory> in MATLAB Central.\r\n\r\n   type shortest_path\r\n   \r\n%% Thanks\r\n% Thanks to Daniel Frey.\r\n##### SOURCE END ##### ea254cadff30471a9559c21c69c9f659\r\n-->","protected":false},"excerpt":{"rendered":"<div class=\"overview-image\"><img decoding=\"async\"  class=\"img-responsive\" src=\"https:\/\/blogs.mathworks.com\/cleve\/files\/patience_puzzle.jpg\" onError=\"this.style.display ='none';\" \/><\/div><!--introduction--><p>MIT's Professor Daniel Frey recently introduced me to an ancient mechanical puzzle known as \"Chinese Rings\", \"Patience\", or \"Baguenaudier.\"  I have modified Daniel's simulator to produce a new app. The state space of the puzzle forms a hypercube.... <a class=\"read-more\" href=\"https:\/\/blogs.mathworks.com\/cleve\/2017\/02\/06\/patience-chinese-rings-puzzle\/\">read more >><\/a><\/p>","protected":false},"author":78,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":[],"categories":[11,5,23,4],"tags":[],"_links":{"self":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/2292"}],"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=2292"}],"version-history":[{"count":7,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/2292\/revisions"}],"predecessor-version":[{"id":2312,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/posts\/2292\/revisions\/2312"}],"wp:attachment":[{"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/media?parent=2292"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/categories?post=2292"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.mathworks.com\/cleve\/wp-json\/wp\/v2\/tags?post=2292"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}