马踏棋盘回路计数问题

xbtianlang

经过近2小时的计算，6×7的哈密顿回路是： 2011-5-31 15:41:03 Total: 1067638 2011-5-31 17:14:07 按照这样的递增速度，9×10的，即使经年累月也几乎算不出来。

KeyTo9_Fans

我写了一个程序，可以快速计算$6$*$n$的棋盘的马步回路总数，结果如下： 棋盘规模?回路总数?程序运行时间 $6$*$7$:?$1067638$?$20s$ $6$*$8$:?$55488142$?$42s$ $6$*$9$:?$3374967940$?$56s$ $6$*$10$:?$239187240144$?$70s$ …… 当行数达到$8$时，每增加$1$行，运行时间增加$14s$。（在答案小于$2^64$的前提下） 通过搜索以上数据，发现这个工作已经被别人在半年前率先完成了： http://oeis.org/A175881 所幸的是，网上暂时未能搜索到$7$*$2n$的棋盘的马步回路总数。 我应该尽快改进我的程序，争取率先完成$7$*$2n$的棋盘的马步回路总数的计算工作。

xbtianlang

我的程序这几天刚设计出来，所以效率很低，7×8的算了整整一个通宵才到3000万，估计有几十亿。 版主既然能算6*10，就直接设计7*10,8*10，9*10好了。

mathe

我写了一个程序，可以快速计算$6$*$n$的棋盘的马步回路总数，结果如下： 棋盘规模?回路总数?程序运行时间 $6$*$7$:?$1067638$?$20s$ $6$*$8$:?$55488142$?$42s$ $6$*$9$:?$3374967940$?$56s$ $6$*$10 ... KeyTo9_Fans 发表于 2011-6-1 03:34

非常不错，链接里面已经算到很多项了: 0, 0, 0, 0, 8, 9862, 1067638, 55488142, 3374967940, 239187240144, 15360134570696, 964730606632516, 61989683445413228, 4005716717182224826, 255967892553030600920, 16378998506224697063588, 1050504687249683771795632, 67351449674771471216148786, 4314151246752166099728445868, 276453522147273309254029785276, 17717606001764726850971209939188, 1135386328785418512845166305951994, 72754625853111517738642395445641832, 4662311340698795306229004946849255108, 298772700964630993744576968415214630040, 19145888052227167790585189427230454709502, 1226902568798073025855948189578313739199398, 78622502118507651703659030426757524782646558, 5038287048556094010756276060713112469110084532, 322863244258188584511076820531771298243292346804, 20689713115693125810120458424283134088711708746418, 1325838052128808846982470604742513077251389064878480, 84962322582242436449028078490147227914653412498469176, 5444553480688572729507994773339404670293124094670063400, 348897761885575809340513599895637906535045836867112425442, 22358059291249098112956347313304579317330515128430578229580, 1432748662105938633370488721737295472216003424322051173765262, 91813368745075979865082473968848043302481279531417429418851766, 5883582334056740305836749071273843581025553554521365508472081512, 377031597006006571424070743308269493020186682009428464253448495336

mathe

此题与走格子路线数统计问题： http://bbs.emath.ac.cn/viewthread.php?tid=517 是同一类问题。 在走格子路线数统计问题里，$4$种走法的位移为： $(0,1)$、$(1,0)$、$(0,-1)$、$(-1,0)$ 我们可以根据 ... KeyTo9_Fans 发表于 2011-5-27 14:48

状态数目随着行的数目增加而迅速增加。对于9*n问题，不知道计算到5行时状态数目增加到多少。如果这时状态数目还不是多的离谱（比如规模在百万左右就还可以），我们可以将9*5行状态结果保存起来。然后同样另外一侧的5行也是这些状态，两边进行匹配就可以了。而匹配过程中，我们可以做一些简单索引，比如两边如果匹配，它们的联通分支数目必须相等，这样可以部分增加匹配的速度。 而同样，如果我们能够将9*6的所有状态都计算出来，那么反向的9*6的状态也同样在里面了，它们最边界两行必将重叠，于是应该可以相互计算对方的状态，由此可以更快的计算总数目

xbtianlang

2011-6-1 13:12:50 path 1 1 28 3 14 11 26 9 18 23 20 4 13 30 27 6 15 24 21 8 17 29 2 5 12 25 10 7 16 19 22 path 2 1 28 3 14 11 26 9 16 19 22 4 13 30 27 6 15 24 21 8 17 29 2 5 12 25 10 7 18 23 20 path 3 1 28 3 24 11 26 9 20 17 14 4 23 30 27 6 21 12 15 8 19 29 2 5 22 25 10 7 18 13 16 path 4 1 28 3 24 11 26 9 18 13 16 4 23 30 27 6 21 12 15 8 19 29 2 5 22 25 10 7 20 17 14 path 5 1 28 3 12 25 10 7 18 23 20 4 13 30 27 6 15 24 21 8 17 29 2 5 14 11 26 9 16 19 22 path 6 1 28 3 12 25 10 7 16 19 22 4 13 30 27 6 15 24 21 8 17 29 2 5 14 11 26 9 18 23 20 path 7 1 28 3 22 25 10 7 20 17 14 4 23 30 27 6 21 12 15 8 19 29 2 5 24 11 26 9 18 13 16 path 8 1 28 3 22 25 10 7 18 13 16 4 23 30 27 6 21 12 15 8 19 29 2 5 24 11 26 9 20 17 14 path 9 1 28 25 8 5 20 23 12 17 14 26 7 30 3 24 9 18 15 22 11 29 2 27 6 19 4 21 10 13 16 path 10 1 28 25 8 5 20 23 10 13 16 26 7 30 3 24 9 18 15 22 11 29 2 27 6 19 4 21 12 17 14 path 11 1 28 25 18 5 20 23 14 11 8 26 17 30 3 24 15 6 9 22 13 29 2 27 16 19 4 21 12 7 10 path 12 1 28 25 18 5 20 23 12 7 10 26 17 30 3 24 15 6 9 22 13 29 2 27 16 19 4 21 14 11 8 path 13 1 28 25 6 19 4 21 12 17 14 26 7 30 3 24 9 18 15 22 11 29 2 27 8 5 20 23 10 13 16 path 14 1 28 25 6 19 4 21 10 13 16 26 7 30 3 24 9 18 15 22 11 29 2 27 8 5 20 23 12 17 14 path 15 1 28 25 16 19 4 21 14 11 8 26 17 30 3 24 15 6 9 22 13 29 2 27 18 5 20 23 12 7 10 path 16 1 28 25 16 19 4 21 12 7 10 26 17 30 3 24 15 6 9 22 13 29 2 27 18 5 20 23 14 11 8 2011-6-1 13:12:50 棋盘: 回路数 3*10: 16 4*10: 0 5*10: 13311268 6*10: 239187240144 7*10: ? 8*10: ? 9*10: ? 以10为边长，可能有点大，不知道有没有更好的扩充方法？

KeyTo9_Fans

经过2小时30分钟的计算，得到7*8棋盘的马步回路总数是34524432316。 由于我的笔记本电脑内存不够大，我只能将中间状态的数据写到硬盘上。 在硬盘上读写数据比在内存中读写数据慢10倍以上。 每个状态需要用16字节的数据表示。 中间状态数目的峰值是69414932，占用了1.04GB的硬盘空间。 计算8*9棋盘的马步回路总数估计要用30GB的硬盘空间，5天的时间。 如果是9*10的棋盘，大概需要800GB空间，6个月的时间。

mathe

8*9的资源要求不大 9*10的就不行了需要优化

KeyTo9_Fans

7*2n棋盘的闭马路总数如下： 7*2: 0 7*4: 0 7*6: 1067638 7*8: 34524432316 7*10: 1250063279938854 7*12: 38350427205194670084 7*14的闭马路总数太多，我们只知道这个数除以2^64的余数为2987064776549805854。 ##### 现在暂时没有空闲的台式机可用，而我的笔记本电脑空不出30GB的硬盘空间，所以暂时不能计算8*n棋盘的闭马路总数。 等到一个月后我的台式机把另外一个程序跑完了，才可以计算8*n棋盘的闭马路总数。

mathe

可以上载源代码吗？我可以帮你运行。不过我要在Linux上运行。