指尖陀螺网
导航

首页 > 独立钻石 > 详细内容

独立钻石Solitaire算法求解

发布时间:  浏览: 次  作者:www.tl6.net

关键字

茶余饭后,休闲娱乐,独立钻石,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算法

上一页 -下一页

关键词:独立钻石,Solitaire,算法求解

相关文章