[机械迷城] 利用bfs解开谜局

[机械迷城] 利用bfs解开谜局

在玩机械迷城,出现了这样一个谜局:

有7个位置,其中六个有棋子,一个为空,只允许两种走法:按棋子的方向向前走到一个空位;跳过1个相对方向的棋子到空位。可以将问题建模为:1表示向下,0表示空位,2表示向上,这样就是长度为7,仅含”012″的字符串,通过适当的变化从”1110222″变到”2220111″。而每次移动棋子可以描述成字符串的替换:1向下走和2向上走就是分别为”10″替换为”01″,”02″替换为”20″;跳一格是”120″替换为”021″,”012″替换为”210″。将整个过程进行BFS,由于我们要知道走法,所以需要将整个路径保存下来。

class iNode:
    def __init__(self,_ss,_pp):
        self.ss = _ss
        self.pp = _pp
    def getss(self):
        return self.ss
    def getpp(self):
        return self.pp
        
Q=[ iNode("1110222","1110222") ]
s=Q[0]
while len(Q)<20:
    s=Q[0]
    if(s.getss()=="2220111"):
        res = s.getpp()
        break
    Q.remove(Q[0])
    repPat =[("02","20"),("10","01"),("120","021"),("012","210")]
    for it in repPat:
        if it[0] in s.getss():
            ns = s.getss().replace(it[0],it[1])
            Q.append(iNode(ns,s.getpp()+";"+ns))
   
for i in res.split(";"):
    print(i)


最后输出了结果:

1110222
1112022
1102122
1012122
1210122
1212102
1212120
1212021
1202121
0212121
2012121
2210121
2212101
2212011
2202111
2220111

可以关注0的位置就可以知道应该移动哪一步棋子,这样就解出了这个小谜局

发表评论

电子邮件地址不会被公开。 必填项已用*标注