（理工类）寒武能够到找到艾莉吗？

ly188

继续算~

aslie

太难了，哎，圣诞节前，一定要找到

磁铁

已经找到啦！感谢book师父已经指点寒武找到啦

ly188

改进了下算法,15分钟过去了,还没结果

yzh_nj_china

这个计算机得算上好长时间···

bookish

哈哈，根据版主的提示，改进了算法，总共只有7375个可能性，在PC机上只要1秒钟！等版主解禁之后再讲解。

ly兄，加油！

ly188

bookish 兄好厉害

磁铁

1位勇敢智慧的骑士bookish已经成功帮助了寒武，花心骑士ly188专心一点、别贪玩、加加油，我的乾坤大挪移正在等着呢

骑士宣言：
I will be kind to the weak.
I will be brave against the strong.
I will fight all who do wrong.
I will fight for those who cannot fight.
I will help those who call me for help.
I will harm no woman.
I will help my brother knight.
I will be true to my friends.
I will be faithful in love.

hanvool

引用第69楼bookish于2007-12-22 19:35发表的 :
哈哈，根据版主的提示，改进了算法，总共只有7375个可能性，在PC机上只要1秒钟！等版主解禁之后再讲解。

ly兄，加油！

bookish老师好厉害，连我最佩服的LY兄都盖住了，可真的有这么多可能性么

我为什么当初不选数学专业

一身的劲使不出，憋得慌

horky

怪不得我算不出来，原来你们都动用了超级计算机了。

这道题的确是道好题，不怕你脑筋好使，这么多大侠，还得要人脑加电脑才能算出来。
佩服！

ly188

//1.从第i点开始,通过边界寻找剩余可以走的方向集合ia
//2.取ia中下一个元素,如果为空执行4,否则,顺着这个方向走
//3.如果遇到正面朝上,则执行4,否则为6
//4.如果是ia的最后一个元素,则执行5,否则2
//5.寻找i的前一点p,以及相应集合ip,ip看作是ia,执行2
//6.如果i在边界上.执行7,否保存i点和ia执行8
//7.如果刚好顺着该边界的点序.(例:历史中只能叠加的顺序出现,不能出现倒序)
// 则保存i点和ia执行8,否则执行5
//8,通过方向得到i的下一点q.如果q=出口执行9,否则q=i执行1.
//9.如果正面朝上则退出.否则q=i执行1


bookish老师来讲讲吧
我头晕了~~~~~

ly188

还有很多没有考虑
比如当前方向不能和上一个方向反向
遇到边界弹出来至少2个? (这个未确定)

磁铁

已经有两位计算机工程骑士勇攀高峰，其中bookish骑士已经成功智取威虎山。现公布bookish骑士的昨天的代码（加密威望58），能够得到唯一正确的结果。其它骑士的其它算法代码如果做出正确的图，妙笔也继续成立。

（因为游戏是在1963年美国的一位理发师发明的，估计还有纯数学算法，也欢迎数学骑士来写准妙笔）

fferror

引用第9楼fferror于2007-12-20 21:45发表的 :
这片原野是个8*8的正方形，用(x,y)代表第x行第y列，出发点是(1,1)，目标点是(8,1)。
大约走了几步，发现寒武可以按照题目的要求走到(2,1)，覆盖的路径是(1,1)->(1,2)->(2,2)->(2,1)，即左上角边长为2的正方形区域。
按要求走到(3,1)好像不行。
但(4,1)可以，且所走路径为左上角边长为4的正方形区域。
于是大胆地归纳，猜测可以从(1,1)按照限制要求走到(偶数,1)，即任一偶数行的第一列，并且覆盖的路径是这个行数为边长的正方形。而目的点是(8,1)，所以预测寒武可以成功。Cheers!
.......

建议先不要解密。
继续诱惑各路高人。

944f4fe875fb39d

原来我的PC机也不慢啊。

在修改了程序错误之后，我把昨天的程序在我的PC机上运行了一下，完成全部搜索，该算法总共走了141,390,059步（包括试探），用时332秒。

修改后的新算法（老程序改了几个数字，加了几个限制），完成全部搜索，总共走了12864步，用时0.013秒。


我先是手算，确定了计算方法，发现可能的解很多，便开了一个数组t(k,i,j)，i是行号，j是列号，存放的数据是红心的朝向，

未走过=0，朝东=1，朝西=2，朝北=3，朝南=4，朝上=5，朝下=6。

这个数组其实是个堆栈，因为在手算的时候我就注意到，每走出一步，就会多出几个可能性，每一种还未验证过的可能性都被压入堆栈，堆栈指针为n。

24-27行描述了一个开始，堆栈指针n=0，红心朝上。

这里出现了一个数组u，它是用来记录这一步是从哪个方向走来的，从东面=1，从西面=2，从北面=3，从南面=4。

由于这个题目是上下对称的，若它有一个非对称解，那么必然就有一个镜像，即必有偶数个解。因为磁铁版主说了，解唯一，所以解必然不是非对称的。于是，我们就只要考虑上面一半区域里的走法。

接下去就是从寒武此刻所在位置向东南西北4个方向试探。

32行的mp是此刻红心的朝向。试探时调用了一个子程序position(mp, dir)，用来得到翻动之后红心的朝向，其实就是一张表，

mp=1 6, 5, 1, 1, 原红心向东，向东、西、北、南翻动后的朝向分别为 下、上、东、东
mp=2 5, 6, 2, 2, 原红心向西，向东、西、北、南翻动后的朝向分别为 上、下、西、西
mp=3 3, 3, 6, 5, 原红心向北，向东、西、北、南翻动后的朝向分别为 北、北、下、上
mp=4 4, 4, 5, 6, 原红心向南，向东、西、北、南翻动后的朝向分别为 南、南、上、下
mp=5 1, 2, 3, 4, 原红心向上，向东、西、北、南翻动后的朝向分别为 东、西、北、南
mp=6 2, 1, 4, 3, 原红心向下，向东、西、北、南翻动后的朝向分别为 西、东、南、北

先设定试探行动的指针，n_new=n

向东试探，36行计算的mp_new就是向东翻动后红心的朝向，试探成功的条件是：

37行：
if (tj[ n] < 7) 不在右边界上；
if (!t[ n][ ti[ n]][ tj[ n] + 1]) 右边的格子没走过；
if (mp_new != 5) 红心不朝上

如果成功，39-48行就把堆栈指针n_new增加，把它送入第n_new层堆栈保存起来，寒武在这次试探中此时所处的位置则记录在ti[n_new]和tj[n_new]中。如果不成功则什么也不做。

然后向西试探，试探成功的条件是53行：

if (tj[ n]) 不在左边界上；
if (ti[ n]) 不在第1行（如果在第1行，向西走是进入死区）；
if (!t[ n][ ti[ n]][ tj[ n] - 1]) 左边的格子没走过；
if (mp_new != 5) 红心不朝上

然后向北试探，试探成功的条件是69行：

if (ti[ n]) 不在上边界上；
if (tj[ n] < 7) 不在最右边一列（如果在最右边，向上走是进入死区）；
if (tj[ n]) 不在最左边一列（如果在最左边，向上走是进入死区）；
if (!t[ n][ ti[ n] - 1][ tj[ n]]) 上边的格子没走过；
if (mp_new != 5) 红心不朝上

然后向南试探，试探成功的条件是85行：

if (ti[ n] < 3) 不在下边界上；
if (!t[ n][ ti[ n] + 1][ tj[ n]]) 下边的格子没走过；
if (mp_new != 5) 红心不朝上

现在，四个方向都试探过了。如果有路可走，就有 n_new>n，那几条路也已送入堆栈，寒武不必留在原地，所以，102-109行把原来在堆栈n中的内容去除，寒武则到堆栈最上层的那个位置，开始新的探索（109、115行）。

如果四个方向的试探都失败了（n_new=n），先检查，是不是每个空格都走过了（118行），如果还有空格，说明刚才寒武所在位置n是条死胡同，放弃它，把指针往下移一下（120行），站到下面一层所记录的位置上（121行）。如果n<0，说明所有可能性都已试过了，结束计算（122行）。

如果四个方向的试探都失败了，并且每个空格都走过了，那么，这条路就走到头了，我们只要看看这条路的尽头是不是寒武要去的地方就可以了。

124行： if (ti[ n] == 3) 在下边界上

既然路的尽头在下边界上，那么，只要寒武按照刚才的路径向下镜像复制下去，就可以找到公主了。

126-133行只是把记录每一步是从哪个方向来的，改为要向哪个方向走，便于根据输出结果绘图。

以下是新算法的完整的程序。

1    #include <ansi_c.h>
2    #include <math.h>
3    #include <stdio.h>
4    #include <stdlib.h>
5   
6    // free=0, e=1, w=2, n=3, s=4, t=5, b=6
7    // move e(right)=1, w(left)=2, n(up)=3, s(down)=4
8   
9    int position(int mp, int direction)
10   {
11     short int n[ 6][ 4] = {6, 5, 1, 1, 5, 6, 2, 2, 3, 3, 6, 5, 4, 4, 5, 6, 1, 2, 3, 4, 2, 1, 4, 3};
12     return n[ mp - 1][ direction - 1];
13   }
14   
15   #define MM 1000
16   short int t[ MM][ 4][ 8], u[ MM][ 4][ 8], v[ 4][ 8], ti[ MM], tj[ MM];
17   
18   int main (void)
19   {
20     int i, j, k, n, nn, ss, n_new, mp, mp_new;
21   
22     ss = time(0);
23     nn = 0;
24     n = 0;
25     ti[ n] = tj[ n] = 0;
26     for (i = 0; i < 4; i++) for (j = 0; j < 8; j++) t[ 0][ i][ j] = u[ 0][ i][ j] = 0;
27     t[ 0][ 0][ 0] = 5;
28   
29   L_0:
30     nn++;
31     n_new = n;
32     mp = t[ n][ ti[ n]][ tj[ n]];
33     // printf("%d\n", mp);
34   
35     // right
36     mp_new = position(mp, 1);
37     if (tj[ n] < 7) if (!t[ n][ ti[ n]][ tj[ n] + 1]) if (mp_new != 5)
38     {
39       n_new++;
40       for (i = 0; i < 4; i++) for (j = 0; j < 8; j++)
41       {
42         t[ n_new][ i][ j] = t[ n][ i][ j];
43         u[ n_new][ i][ j] = u[ n][ i][ j];
44       }
45       ti[ n_new] = ti[ n];
46       tj[ n_new] = tj[ n] + 1;
47       t[ n_new][ ti[ n_new]][ tj[ n_new]] = mp_new;
48       u[ n_new][ ti[ n_new]][ tj[ n_new]] = 1;
49     }
50   
51     // left
52     mp_new = position(mp, 2);
53     if (tj[ n]) if (ti[ n]) if (!t[ n][ ti[ n]][ tj[ n] - 1]) if (mp_new != 5)
54     {
55       n_new++;
56       for (i = 0; i < 4; i++) for (j = 0; j < 8; j++)
57       {
58         t[ n_new][ i][ j] = t[ n][ i][ j];
59         u[ n_new][ i][ j] = u[ n][ i][ j];
60       }
61       ti[ n_new] = ti[ n];
62       tj[ n_new] = tj[ n] - 1;
63       t[ n_new][ ti[ n_new]][ tj[ n_new]] = mp_new;
64       u[ n_new][ ti[ n_new]][ tj[ n_new]] = 2;
65     }
66   
67     // upword
68     mp_new = position(mp, 3);  
69     if (ti[ n]) if (tj[ n] < 7) if (tj[ n]) if (!t[ n][ ti[ n] - 1][ tj[ n]]) if (mp_new != 5)
70     {
71       n_new++;
72       for (i = 0; i < 4; i++) for (j = 0; j < 8; j++)
73       {
74         t[ n_new][ i][ j] = t[ n][ i][ j];
75         u[ n_new][ i][ j] = u[ n][ i][ j];
76       }
77       ti[ n_new] = ti[ n] - 1;
78       tj[ n_new] = tj[ n];
79       t[ n_new][ ti[ n_new]][ tj[ n_new]] = mp_new;
80       u[ n_new][ ti[ n_new]][ tj[ n_new]] = 3;
81     }
82   
83     // downword
84     mp_new = position(mp, 4);
85     if (ti[ n] < 3) if (!t[ n][ ti[ n] + 1][ tj[ n]]) if (mp_new != 5)
86     {
87       n_new++;
88       for (i = 0; i < 4; i++) for (j = 0; j < 8; j++)
89       {
90         t[ n_new][ i][ j] = t[ n][ i][ j];
91         u[ n_new][ i][ j] = u[ n][ i][ j];
92       }
93       ti[ n_new] = ti[ n] + 1;
94       tj[ n_new] = tj[ n];
95       t[ n_new][ ti[ n_new]][ tj[ n_new]] = mp_new;
96       u[ n_new][ ti[ n_new]][ tj[ n_new]] = 4;
97     }
98     // printf("nn=%d, n=%d\n", nn, n);
99     
100     if (n_new > n)
101     {
102       for (k = n; k < n_new; k++) for (i = 0; i < 4; i++) for (j = 0; j < 8; j++)
103       {
104         t[ k][ i][ j] = t[ k + 1][ i][ j];
105         u[ k][ i][ j] = u[ k + 1][ i][ j];
106         ti[ k] = ti[ k + 1];
107         tj[ k] = tj[ k + 1];
108       }
109       n = n_new - 1;
110       if (n > MM - 4)
111       {
112         printf("not finifshed\n");
113         goto L_end;
114       }
115       goto L_0;
116     }
117   
118     for (i = 0; i < 4; i++) for (j = 0; j < 8; j++) if (!t[ n][ i][ j])
119     {
120       n--;
121       if (n >= 0) goto L_0; // if (n) goto L_0;
122       else goto L_end;
123     }
124     if (ti[ n] == 3)
125     {
126       for (i = 0; i < 4; i++) for (j = 0; j < 8; j++)
127       {
128         if (u[ n][ i][ j] == 1) v[ i][ j - 1] = 1;
129         else if (u[ n][ i][ j] == 2) v[ i][ j + 1] = 2;
130         else if (u[ n][ i][ j] == 3) v[ i + 1][ j] = 3;
131         else if (u[ n][ i][ j] == 4) v[ i - 1][ j] = 4;
132       }
133       v[ ti[ n]][ tj[ n]] = 0;
134   
135       for (i = 0; i < 4; i++)
136       {
137         for (j = 0; j < 8; j++) printf("%d-%d ", t[ n][ i][ j], v[ i][ j]);
138         printf("\n");
139       }
140       printf("\n");
141     }
142     n--;
143     if (n >= 0) goto L_0; // if (n) goto L_0;
144   L_end:
145     printf("nn=%d, time=%ds\n", nn, time(0)-ss);
146     scanf("%d", &i);
147     return 0;
148   }

磁铁

此题竟然难倒无数英雄好汉 ，这是很古老和偏僻的一个题，很难搜索到，现在在园地上各位骑士用计算机工程求解颇有新意也颇有难度，比较适合学术妙笔区的各位高人继续研讨

建议给bookish骑士(主ID)优秀原创学术妙笔奖，ly188(主ID)原创探讨妙笔奖
fferror的思路很不错，期待他能有纯数学方面的妙笔出现

楼主的图片怎么贴上后转移到这里就失踪了，再贴一次：

yzh_nj_china

啥叫高人···

磁铁

这可不是什么开玩笑的题目，来源于1964年的《Scientific American》，后来有多期进行讨论，引无数英雄竟折腰，后来引申为一系列问题，延续了12年才有了初步的解决。（当时没有计算机）

yzh_nj_china

引用第38楼磁铁于2007-12-23 22:53发表的 :
这可不是什么开玩笑的题目，来源于1964年的《Scientific American》，后来有多期进行讨论，引无数英雄竟折腰，后来引申为一系列问题，将近10年才有了初步的解决。（当时没有计算机）

所以，要羡慕~~~
book老师跟ly188老师的水平才羡慕啊~~~
这个题的确有深度~~~