mathe于2011年5月提问

中国象棋(9×10)棋盘上一只马从任何一个位置出发,没有重复经过所有格子最后返回起始点的不同方案有多少种?
如果不需要返回起始点,那么又有多少种方案?

KeyTo9_Fans出手,使用计算机经过艰难的计算,得出最终最后返回起点情况的数目为19381952998732022416892种。
但是不需要返回起点的情况复杂度太大,还没有人能够求出方案数。

详细信息

风云剑最先给出了两种枚举代码, 可以枚举产生一些马踏棋盘的局面 。

然后KeyTo9_Fans出手,给出了一种使用动态规划计数的重要算法。
他说这个问题和以前他已经解决过的走格子线路统计问题类似
那个问题在走格子路线数统计问题里,4种走法的位移为:
(0, 1) 、 (1,0)、(0,-1)、(-1,0)

我们可以根据这种走法,设计出C_4^2=6种瓷砖:
bricks
给每格铺上一种瓷砖。于是路线数统计问题就变成了铺瓷砖方案数统计问题。

我们从上往下铺瓷砖。

铺的时候需要考虑:

1、新铺的瓷砖和已经铺好的瓷砖的边沿是否匹配。

2、新铺的瓷砖和已经铺好的瓷砖的连通性是否合法。

可以用动态规划算法统计合法的铺瓷砖方案总数。

由于所有走法的坐标变化的绝对值不超过 (1 + 0)

所以边沿状态只有一行格子的信息。

而马踏棋盘有8种走法:
(1,2)、(2,1)、(1,-2)、(2,-1)、(-1,2)、(-2,1)、(-1,-2)、(-2,-1)
相应的一共有C_8^2=28种瓷砖。

所有走法的坐标变化的绝对值不超过(2 + 1)。

所以边沿状态有2行加1个格子的信息。

即19个格子的信息。

信息包括:

1、该格子的两个端口(上一步从哪里跳过来,下一步跳到哪里去)已经确定了几个?用一个数字0、1、2表示。

2、对于标了数字1的格子,它们的连通情况。用1a、1b、1c……表示。相同的字母表示目前已经相连,不同的字母表示目前尚未相连。

暂不考虑第2条信息,在最坏的情况下第1条信息就已经有3^{19}种可能了,这个数有点大。但实际情况会好多少,这个暂时不知道。

xbtianlang 先枚举出5\times 6棋盘有8条回路, 而6\times 7棋盘有1067638条回路

KeyTo9_Fans先利用他提出的算法计算了6\times n棋盘的回路数目,得出数目和运行时间如下表

棋盘规模 回路总数 程序运行时间
6\times 7 1067638 20s
6\times 8 55488142 42s
6\times 9 3374967940 56s
6\times 10 239187240144 70s

然后在OEIS网站找到对应的数列A175881

他继续计算7\times 2n棋盘的回路数目,得出

棋盘规模 回路总数
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 n得出

棋盘规模 回路总数
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;
}

并且 补充了7\times 2n的数目到30

然后数据提交到了OEIS A193054

直到2015年Fans换了TB级别硬盘, 终于可以9\times 2n问题发起冲击, 历经两个月艰苦计算,得出我们最终目标

棋盘规模 回路总数
9\times 6 3374967940
9\times 8 7112881119092574
9\times 10 19381952998732022416892

可能因为数据数目太少,好像没有提交OEIS。