马踏棋盘计数
January 26, 2020
mathe于2011年5月提问
中国象棋(9×10)棋盘上一只马从任何一个位置出发,没有重复经过所有格子最后返回起始点的不同方案有多少种? 如果不需要返回起始点,那么又有多少种方案?
KeyTo9_Fans出手,使用计算机经过艰难的计算,得出最终最后返回起点情况的数目为19381952998732022416892种。 但是不需要返回起点的情况复杂度太大,还没有人能够求出方案数。
详细信息
风云剑最先给出了两种枚举代码, 可以枚举产生一些马踏棋盘的局面 。
然后KeyTo9_Fans出手,给出了一种使用动态规划计数的重要算法。 他说这个问题和以前他已经解决过的走格子线路统计问题类似 那个问题在走格子路线数统计问题里,4种走法的位移为: (0, 1) 、 (1,0)、(0,-1)、(-1,0)
我们可以根据这种走法,设计出种瓷砖:
给每格铺上一种瓷砖。于是路线数统计问题就变成了铺瓷砖方案数统计问题。
我们从上往下铺瓷砖。
铺的时候需要考虑:
1、新铺的瓷砖和已经铺好的瓷砖的边沿是否匹配。
2、新铺的瓷砖和已经铺好的瓷砖的连通性是否合法。
可以用动态规划算法统计合法的铺瓷砖方案总数。
由于所有走法的坐标变化的绝对值不超过 。
所以边沿状态只有一行格子的信息。
而马踏棋盘有8种走法: (1,2)、(2,1)、(1,-2)、(2,-1)、(-1,2)、(-2,1)、(-1,-2)、(-2,-1) 相应的一共有种瓷砖。
所有走法的坐标变化的绝对值不超过(2 + 1)。
所以边沿状态有2行加1个格子的信息。
即19个格子的信息。
信息包括:
1、该格子的两个端口(上一步从哪里跳过来,下一步跳到哪里去)已经确定了几个?用一个数字0、1、2表示。
2、对于标了数字1的格子,它们的连通情况。用1a、1b、1c……表示。相同的字母表示目前已经相连,不同的字母表示目前尚未相连。
暂不考虑第2条信息,在最坏的情况下第1条信息就已经有种可能了,这个数有点大。但实际情况会好多少,这个暂时不知道。
xbtianlang 先枚举出棋盘有8条回路, 而棋盘有1067638条回路。
KeyTo9_Fans先利用他提出的算法计算了棋盘的回路数目,得出数目和运行时间如下表
棋盘规模 | 回路总数 | 程序运行时间 |
---|---|---|
$6\times 7$ | 1067638 | 20s |
$6\times 8$ | 55488142 | 42s |
$6\times 9$ | 3374967940 | 56s |
$6\times 10$ | 239187240144 | 70s |
然后在OEIS网站找到对应的数列A175881
他继续计算棋盘的回路数目,得出
棋盘规模 | 回路总数 |
---|---|
$7\times 2$ | 0 |
$7\times 4$ | 0 |
$7\times 6$ | 1067638 |
$7\times 8$ | 34524432316 |
$7\times 10$ | 1250063279938854 |
$7\times 12$ | 38350427205194670084 |
接下去mathe帮忙运行得出
棋盘规模 | 回路总数 |
---|---|
$8\times 5$ | 44202 |
$8\times 6$ | 55488142 |
$8\times 7$ | 34524432316 |
$8\times 8$ | 13267364410532 |
$8\times 9$ | 7112881119092574 |
$8\times 10$ | 4235482818156697040 |
$8\times 11$ | 2085986745706526487660 |
$8\times 12$ | 1105402225545775529519346 |
$8\times 13$ | 586820020252349733523479144 |
$8\times 14$ | 311550865844403670432538061432 |
$8\times 15$ | 162703111270599746594928785964078 |
$8\times 16$ | 85817858712661606753131465774443178 |
$8\times 17$ | 45194091394912063170099393989692461352 |
$8\times 18$ | 326323885119378112085100727490253780278 |
并且给出了Fans的源代码如下:
#include
#include
#include
#include
using namespace std;
#define __int64 long long
const unsigned int pm=503,pn=8388608;
char fn[96];
unsigned char a[20],b[20];
unsigned int c[pn],h,i,j,k,l,m,n,t;
unsigned long long o;
unsigned __int64 ui,vi,ans[32],u[pn],v[pn];
FILE *ou[pm],*in;
#ifndef MODR
#define MODR 0
#endif
unsigned __int64 add(unsigned __int64 x, unsigned __int64 y)
{
if(MODR==0)return x+y;
if((-MODR)-x>y)return x+y;
return x+y+MODR;
}
void pr(unsigned int f,unsigned __int64 v)
{
fwrite(&v,sizeof(unsigned __int64),1,ou[f]);
}
void pri(unsigned __int64 v)
{
fwrite(&v,sizeof(unsigned __int64),1,in);
}
void sc(unsigned int f,unsigned __int64 &v)
{
if(fread(&v,sizeof(unsigned __int64),1,ou[f])!=1)v=0ull;
}
void sci(unsigned __int64 &v)
{
if(fread(&v,sizeof(unsigned __int64),1,in)!=1)v=0ull;
}
unsigned __int64 id(unsigned char a[])
{
unsigned char c[16],i,j;
unsigned __int64 s;
memset(c,0,16);
for(i=0;i1)
if(c[j])
{
a[c[j]-1]=i-c[j]+2;
a[i]=0;
}
else c[j]=i+1;
}
s=0;
for(i=0;i1)
{
a[i+a[i]-1]=k;
a[i]=k++;
}
}
}
void ad(unsigned __int64 x)
{
unsigned __int64 s;
s=id(b);
pr(s%pm,s);
pr(s%pm,x);
o++;
}
unsigned int d(unsigned int x)
{
unsigned int i;
for(i=1;;i++)
if(i!=x&&a[i]==a[x])return i;
}
void c1(unsigned int x)
{
unsigned int i,j;
if(a[x]==1)return;
memcpy(b,&a[1],l);
if(a[x]==a[0])
{
j=h/m+2;
b[x-1]=1;
for(i=0;ij*m&&b[i]!=0)break;
if(i>=l)ans[j]=add(ans[j],vi);
return;
}
if(!a[x])b[x-1]=a[0];
else
{
b[x-1]=1;
b[d(x)-1]=a[0];
}
ad(vi);
}
void c2(unsigned int x,unsigned int y)
{
unsigned int i,j;
if(a[x]==1||a[y]==1)return;
memcpy(b,&a[1],l);
if(a[x]&&a[x]==a[y])
{
j=h/m+2;
b[x-1]=1;
b[y-1]=1;
for(i=0;ij*m&&b[i]!=0)break;
if(i>=l)ans[j]=add(ans[j],vi);
return;
}
if(a[x])
{
b[x-1]=1;
b[y-1]=1;
if(a[y])b[d(y)-1]=a[x];
else b[y-1]=a[x];
}
else
if(a[y])
{
b[x-1]=a[y];
b[y-1]=1;
}
else
{
b[x-1]=15;
b[y-1]=15;
}
ad(vi);
}
bool cmp(unsigned int i,unsigned int j)
{
return u[i]1)
{
if(j>1)c1(m-2);
if(j&&h/m1)
{
if(h/mm-2){printf("%llu\n",ans[h/m+2]);fflush(stdout);}
}
// scanf("%d",&h);
return 0;
}
并且 补充了的数目到30
然后数据提交到了OEIS A193054
直到2015年Fans换了TB级别硬盘, 终于可以向问题发起冲击, 历经两个月艰苦计算,得出我们最终目标
棋盘规模 | 回路总数 |
---|---|
$9\times 6$ | 3374967940 |
$9\times 8$ | 7112881119092574 |
$9\times 10$ | 19381952998732022416892 |
可能因为数据数目太少,好像没有提交OEIS。