走格子的路线数统计问题

mathe

百度吧贴中有个 KeyTo9のFans的计算题感觉不错,特此转贴过来,
大家可以思考一下其可行的算法.我基本上可以猜测出来KeyTo9のFans在那里使用的算法(虽然他没有公布),有空时和大家一起详细分析一下:
http://tieba.baidu.com/f?kz=395424512

国际象棋棋盘上，一只車从左下角格走到右上角格一共有多少条简单路径？ 简单指不自交，即每个格子最多经过一次。
一般化为n×n棋盘，可以从比较小的n算起，然后尝试寻找通项公式.

同类问题：

2. n×n的棋盘，从左下角走到右下角一共有多少条简单路径？
3. n*n的棋盘，从左下角走到右上角一共有多少条简单路径？
4. n*n的棋盘，从左下角走到右下角，遍历所有格子一共有多少条简单路径？

而且KeyTo9のFans特别提到了这个题目他所用的算法非常有意思的竟然同另外一个关于围棋问题的算法基本相同:
http://tieba.baidu.com/f?kz=372248697
在19路棋盘上，共有多少种可能的局面？
在n×n的棋盘上，共有多少种可能的局面？

两问完成一问即可。

mathe

贴一下他的计算结果:
问题1的路径条数：

n s
1 1
2 2
3 12
4 184
5 8512
6 1262816
7 575780564
8 789360053252
9 3266598486981642
10 41044208702632496804
11 1568758030464750013214100
12 182413291514248049241470885236
13 64528039343270018963357185158482118
14 69450664761521361664274701548907358996488
15 227449714676812739631826459327989863387613323440
16 2266745568862672746374567396713098934866324885408319028
17 68745445609149931587631563132489232824587945968099457285419306

程序运行时间：

n t
10 0.7s
11 2.2s
12 7.8s
13 28s
14 106s
15 7min
16 28min
17 2h

问题4的路径条数：
n s
1 1  
2 1  
3 2  
4 8  
5 86  
6 1770  
7 88418  
8 8934966  
9 2087813834  
10 1013346943033
11 1111598871478668
12 2568944901392936854
13 13251059359839620127088
14 145194816279817259193401518
15 3524171261632305641165676374930
16 182653259988707123426135593460533473
17 20867537601324146829127267814319046730462
18 5108466695838037792668155733045329910045302167

程序运行时间：
n t
11 0.9s
12 3.5s
13 12s
14 51s
15 3min
16 13min
17 47min
18 3.5h


围棋可能局面数的计算结果:
n=12: 2h

n s
1 1
2 57
3 12675
4 24318165
5 414295148741
6 62567386502084877
7 83677847847984287628595
8 990966953618170260281935463385
9 103919148791293834318983090438798793469
10 96498428501909654589630887978835098088148177857
11 793474866816582266820936671790189132321673383112185151899
12 57774258489513238998237970307483999327287210756991189655942651331169

mathe

关于围棋问题,找到了一个源代码,用pike写的(呵呵,我不知道这是什么语言):
http://www.lysator.liu.se/~gunnar/legal.pike.txt
不过前面部分的注释介绍了所用的算法的思想,应该基本就是KeyTo9のFans所用的算法了.

无心人

Pike语言官方网站
作者：牛魔王 — 上次修改时间: 2007-01-09 13:52
Pike是一种解释性的，面向对象的编程语言。它看起来有点象C和C++，但更容易学习和使用。既适用于小型脚本语言应用，也适用于大型程序。Pike是很巧妙的语言，它是纯面向对象的，但形式上你也可以把它当成面向过程的语言来应用，并且Pike提供了lambda函数。在理念上，Pike是为了让程序员舒服而被设计的。
这个链接地址是： http://pike.ida.liu.se/

shshsh_0510

这类问题应该被深入研究过的，所以搜资料是最好的办法

shshsh_0510

如：http://arxiv.org/PS_cache/cond-mat/pdf/0506/0506341v2.pdf
http://mathworld.wolfram.com/Self-AvoidingWalk.html

medie2005

问题1：
n  s
1  1
2  2
3  12
4  184
5  8512
6  1262816
7  575780564
8  789360053252
9  3266598486981642
10  41044208702632496804
11  1568758030464750013214100
12  182413291514248049241470885236
13  64528039343270018963357185158482118
14  69450664761521361664274701548907358996488
15  227449714676812739631826459327989863387613323440
16  2266745568862672746374567396713098934866324885408319028
17  68745445609149931587631563132489232824587945968099457285419306
18 6344814611237963971310297540795524400449443986866480693646369387855336
19  1782112840842065129893384946652325275167838065704767655931452474605826692782532
20  1523344971704879993080742810319229690899454255323294555776029866737355060592877569255844

无心人

晕，光解的文字的形状就是个快速增长的曲线

shshsh_0510

自己算的？贴一下运行时间比较一下。