麻省理工学院的教授丹尼尔·弗雷最近向我介绍了一个古老的机械难题被称为“中国的戒指”,“耐心”,或“Baguenaudier。”I have modified Daniel's simulator to produce a new app. The state space of the puzzle forms a hypercube.

内容

背景

有几十个YouTube视频的显示解决方案和速度竞赛酒馆难题称为“耐心”。金宝搏官方网站最好的视频是由泰Yann“Baguenaudier中国戒指。”Here is the link to his谜题教程。

维基百科告诉我们,Baguenaudier法国是“浪费时间”。

弗雷教授写了一个MATLAB模拟课程今年春天在麻省理工学院,2.086数值计算,“机械工程师”。My new app is based on his program.

谜题

谜题有6个钢钩,通常由钉子,连着一个基地。每个钩钢环连着。一块长活动称为航天飞机最初在指甲和螺纹环。目标是免费的航天飞机。这不是容易。

图片来源:麻省理工学院的丹尼尔·弗雷

我的新互动应用程序,耐心是包含在2.2版本克里夫的实验室在MATLAB的中央。我希望你能自己尝试解决难题之前,采取“没有耐心”自动化解决按钮。下面的gif动画显示了几个步骤开始时的解决方案,然后跳过许多中间步骤显示过去几个之前。

状态

六钩的位置向上或向下,提供了一个six-bit二进制数,描述状态的机制。最初,戒指都是订婚,所以二进制文件的状态000000年,当然,这是一个小数0。目标是自由的所有戒指,给一个二进制111111年,或十进制63。这个应用程序显示了十进制值在每个步骤图标题。

钩子是编号从1到6左边开始。因此,我们将使用“big endian”二元,最低有效位的左边。

规则

这一行patience.m,指的是状态向量年代和一个钩子n,控制可能的动作。

dbtype52:53耐心

52%移动允许吗?53好= (n = = 1) | | (n = = 2) & & ~ S (1) | | (n > 2) & & (~ (n - 1)所有(S (1: n - 2)));

规则说

这是所有你需要知道的操作难题。

事实证明,在任何一步最多两个,有时只有一个,六个钩子是一个法律行动。

例如,如果状态

S = [1 1 0 0 1 0]

有两种可能的举措。你可以点击钩1给

S = [0 1 0 0 1 0]

或者,你可以点击钩4给

S = [1 1 0 1 1 0]

最短路径

最优路径从一个给定的起始状态,如0,可以找到目标,63年,通过蛮力递归搜索,尝试所有可能的每一步行动。在这篇文章的最后的代码。从0到63的最短路径。

路径= shortest_path (0)

路径=列1到13 0 2 3 11 10 8 9 13 12 14 15 47 46列14到26 44 45 41 40 42 43 35 34 32 33 37 36 38列27日通过39 39 55 54 52 53 49 48 50 51 59 58 56 57列40到61年43 60 62 63

注意,最短路径从不重复状态,因为如果我们发现自己达到一个我们已经参观了,我们可以缩短路径通过跳过的额外步骤。

事实证明,唯一的起始状态,访问所有顶点31 = [1 1 1 1 1 0],对应于从第六钩和所有其他人。

每一步变化状态的2的幂。你可以恢复的鼠标点击的顺序会产生这个路径通过的log2变化。

钩子= log2 (abs (diff(路径)))+ 1

钩子= 1到13 2列1 4 1 2 3 1 2 6 1 2列14到26 1 3 1 2 1 4 1 2 3 1 2 1 27 - 39列5 1 2 3 1 2 1 4 1 2 1 3列40到42 1 2 1

情节

情节让我们国家的十进制值从0到63的最短路径。这是这个值的进步在42的步骤。偶数编号的步骤涉及切换第一钩,改变状态的值的±1。第六个钩只移动一次,在第11步,改变价值+ 32。第五个钩贡献其+ 16步28。

plot_path

长度

以下是每个起点的最短路径的长度。

L = 0 (64 1);为n = 0:63长度L (n + 1) = (shortest_path (n));结束酒吧(左)

超立方体和图表

住在一个六维空间困惑的状态。有64个顶点,编号从0到63。每个顶点连接到六个顶点的数量,用二进制表示,不同于自己的一点。连接——那些顶点和它们之间的联系,形成一个图被称为超立方体。

MATLAB的最新版本包括一个新对象的方法,图。我打算讨论超立方体和图在我的下一篇博文。

代码

这里的代码递归搜索,找到最短路径。完整的代码耐心应用程序现在是包含的克里夫的实验室在MATLAB的中央。

类型shortest_path

函数路径= shortest_path (m,路径)% shortest_path,或shortest_path(状态),状态是小数状态%值在0到63之间,是允许的最短路径问题%的状态转移到目标,63年。% % shortest_path (S, m,路径)是递归调用。如果输入参数个数= = 0 = 0状态;%默认结束如果输入参数个数< = 1%初始调用m = 0;以前% n路径= [];如果终止递归路径= = = 63%状态;返回结束如果状态= = 31 m = 0;结束%搜索最短路径pow2 = 2。^ (0:5);lmin =正;(1:m - 1 m + n = 1:6) Sn =国防部(地板(state. / pow2), 2); % Convert state to binary Sn(n) = ~Sn(n); % Flip one bit ok = (n==1) || (n==2)&&~Sn(1) || ... (n>2)&&(~Sn(n-1)&&all(Sn(1:n-2))); % Allowable move if ok staten = Sn*pow2'; % Recursive call pn = shortest_path(staten,n,[path staten]); if length(pn) < lmin lmin = length(pn); pbest = pn; end end end path = [state pbest]; end % shortest_path

谢谢

感谢丹尼尔·弗雷。

得到了MATLAB代码

发表与MATLAB®R2017a