[机械迷城] 利用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的位置就可以知道应该移动哪一步棋子，这样就解出了这个小谜局
