马踏棋盘回路计数问题

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上运行。