关键字

茶余饭后，休闲娱乐，独立钻石，solitaire，DFS，剪枝。

摘要

茶余饭后，休闲娱乐。

百度略为查找，算法实现很多，但并不认为很多实现在实践中可以在有限的内存、可接受的时间内，得出结果。

在实验环境[1]中，20s得到第一个解。内存使用2GBytes多。

交换p1,p2顺序，306秒得到第一个解。

连跳算1步的话，在目前方法中，只找到最好20步解。

问题

棋盘如下，感谢金涬博士和我一起无聊，并赠送实物跳棋。

日常跳棋规则，110跳为001。

目标，从中心为0，跳到最后只剩1个子在中心。(独立钻石名称由此而来)

算法实现

DFS无可争议。先不考虑连跳，找到解时，需要31部；搜索规则为，针对当前盘面的0(空格)(搜索0和搜索1是对称的)，尝试4个方向。需要保存当前盘面和当前动作，作为搜索回溯记录。

时间复杂度极高(O(n!))，需要考虑可接受时间内得到解。

剪枝，对任意盘面，根据规则不变性，如果其后续搜索无法得到解，则，当再次碰到该盘面时，无须搜索。

优化，搜索时，需要大量重复进行的操作，进行简化或优化。乘除变加减，内存动态分配变静态，减少函数调用次数，化简各种可能引起引起高代价的操作，如，list.remove()，list.append()，list.pop()

棋盘board=[0]*49，p=i*7+j，i、j为行、列。则上下左右可简化为+/-7，+-1，跳上下简化为+/-14，+/-2。

board_stack=[None]*32，静态化，保存当前搜索步的棋盘栈。

zero_list_stack= [None]*32，静态化，最多32个状态，其中每个元素为zeri_list=[0]*32，最多32个0。对当前位置p的0，如果可以跳棋，位置p变1，p1,p2变0。next_zero_list[point_idx]=p1，next_zero_list[step+1]=p2，将p位置替换成p1，p2增加到末尾。可交换p1，p2位置。

action=[0]*31，记录每部的动作，最多31部。动作为point_idx=action[step]//4，表示针对当前zero_list里的0搜索，direction=action[step]%4，表示对当前0的四个方向，当point_idx>step，即所有0都被检查过时，回溯。(step时，zero_list里有step+1个0，索引从0开始)

board_mark=np.zeros((2**14,2**14),dtype=np.uint32)，2^33位，对应33种盘面空间。前14+14位分别对应i,j行列。后5位取值0–31，对应uint32上每位。打标记为，board_mark[idx_i,idx_j]|=1<<idx_bit；检查标记为，board_mark[idx_i,idx_j]&(1<<idx_bit)

程序主体就是依据action规则不变，循环检查，直到得到解，本质上是DFS。试验环境[1]中，20秒得到第一个解，如替换p1,p2位置，306秒得到第一个解。

程序源代码

链接:https://pan.baidu.com/s/196OkF7Q8QVU_klQwe0Hz2A

 提取码:5a5s

最优解尝试

连跳算1步，则每跳1步，步长+0或+1，取决于是否收尾相连。当当前步长已严格大于当前最小步长时，回溯，并标记该点。被回溯盘面，仍然可能是最优解，因此，在不完全遍历时，不能保证得到最优解。

尝试过好几种方案，最后只保留权衡时间，只保留以下方案。

所有路径已找到路径，均保留为可访问。

current_path_len>min_path_len时，标记该盘面可访问；前序盘面，有可能因此回溯被标记为不可再访问，此处是造成最短路径可能丢失的原因。

结果见，

链接:https://pan.baidu.com/s/196OkF7Q8QVU_klQwe0Hz2A

 提取码:5a5s

后话

形式化

盘面有33个位置，规定有子为1，无子为0。可能的盘面数为2^33，数量为8G(8.59x10^9)个潜在盘面。按照规则，每跳一步，盘面少一个1；当剩下最后一个1，得到解，游戏结束，整个过程31步。我们关心的是最后一个1在盘面正中的解。可以理解为，在盘面空间，按照规则，找出一条从起始盘面到终止盘面的路径。这是一个标准的图中路径搜索问题。

问题的时间复杂度为O(n!)。

设An是盘面有n+1个0或32-n个1的盘面集合（计算机下标从0开始引起的巴适），其中，n=0,1,2,…,31。目标是找到一条a0,a1,a2,…,a31，其中ai属于Ai。可以看出，Ai和Aj的交集为空。An的元素数为C（33,n+1）（组合数，33取n+1的组合），例如，A0表示盘面有1个0的集合，元素数为C（33,0+1）=33。如果Ai中的盘面到A(i+1)的盘面都是可到底，则搜索数将是C(33,1)xC(33,2)x…C(33,32)，约为7.13x10^211(计算这个数字已经很无聊了)，已超全宇宙原子数了。限于规则，An只可能有4x(n+1)种可能到An+1，因为只有0可以落子，落子可能来自4个方向。这样，在不考虑盘面对称和旋转的情况下，可能的搜索次数为4x8x12x…x124=4^31x31!，约3.79x10^52。考虑到棋盘1和0的对称性，可能的搜索次数约为4^31x(16!)x(15!)，约为1.26x10^44。即使通过规则剔出掉不可达盘面，其可能的搜索次数也不可小视。

路径长度

设f(a0,a1,…,a31)为路径长度，则对任意i,f(a0,a1,…,a31)<=f(a0,a1,…,ai)+f(ai,a(i+1),…,a31)，满足三角不等式。a(i-1)、ai、a(i+1)可以连跳时，f(a0,a1,…,a31)=f(a0,a1,…,ai)+f(ai,a(i+1),…,a31)–1；不可以连跳时，f(a0,a1,…,a31)=f(a0,a1,…,ai)+f(ai,a(i+1),…,a31)。

当f(b0,b1,…,b(i-1))>f(a0,a1,…,a(i-1))时，f(b0,b1,…,b(i-1),ai,a(i+1),…,a31)>=f(a0,a1,…,a(i-1),ai,…,a31)。

曾尝试利用此规则，在寻找最优解中优化，但尝试失败。

参考

[1]独立钻石https://baike.baidu.com/item/%E7%8B%AC%E7%AB%8B%E9%92%BB%E7%9F%B3/1137021?fr=aladdin

[2]试验环境

硬件：AlienWareM14，Intel®Core™i7-2760QMCPU@2.40GHz；内存8G

操作系统：Windows7专业版

软件：Python3.6.8

[3]A*算法，Dijkstra算法，Floyd算法