ly兄，加油！ 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. 引用第69楼bookish于2007-12-22 19:35发表的 :
哈哈，根据版主的提示，改进了算法，总共只有7375个可能性，在PC机上只要1秒钟！等版主解禁之后再讲解。
ly兄，加油！
bookish老师好厉害，连我最佩服的LY兄都盖住了，可真的有这么多可能性么
我为什么当初不选数学专业
一身的劲使不出，憋得慌 怪不得我算不出来，原来你们都动用了超级计算机了。 这道题的确是道好题，不怕你脑筋好使，这么多大侠，还得要人脑加电脑才能算出来。
佩服！ //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老师来讲讲吧
我头晕了~~~~~ 还有很多没有考虑
比如当前方向不能和上一个方向反向
遇到边界弹出来至少2个? (这个未确定) 已经有两位计算机工程骑士勇攀高峰，其中bookish骑士已经成功智取威虎山。现公布bookish骑士的昨天的代码（加密威望58），能够得到唯一正确的结果。其它骑士的其它算法代码如果做出正确的图，妙笔也继续成立。
（因为游戏是在1963年美国的一位理发师发明的，估计还有纯数学算法，也欢迎数学骑士来写准妙笔） 引用第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!
.......
建议先不要解密。
继续诱惑各路高人。 原来我的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和tj中。如果不成功则什么也不做。
然后向西试探，试探成功的条件是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的思路很不错，期待他能有纯数学方面的妙笔出现
楼主的图片怎么贴上后转移到这里就失踪了，再贴一次：
啥叫高人···
这可不是什么开玩笑的题目，来源于1964年的《Scientific American》，后来有多期进行讨论，引无数英雄竟折腰，后来引申为一系列问题，延续了12年才有了初步的解决。（当时没有计算机） 引用第38楼磁铁于2007-12-23 22:53发表的 :
这可不是什么开玩笑的题目，来源于1964年的《Scientific American》，后来有多期进行讨论，引无数英雄竟折腰，后来引申为一系列问题，将近10年才有了初步的解决。（当时没有计算机）
所以，要羡慕~~~
book老师跟ly188老师的水平才羡慕啊~~~
这个题的确有深度~~~
页:
1
[2]