def kasSees(rida, veerg):
  return rida in range(3) and veerg in range(3)

nihked=[[-1, 0], [0, -1], [1, 0], [0, 1]]
def sammuKaugusel(seis):
 tyhinr=seis.find("_")
 tyhirida=tyhinr // 3
 tyhiveerg=tyhinr % 3
 vastused=[]
 for nihe in nihked:
  if kasSees(tyhirida+nihe[0], tyhiveerg+nihe[1]):
    uus=list(seis)
    uus[tyhirida*3+tyhiveerg]=seis[(tyhirida+nihe[0])*3+tyhiveerg+nihe[1]]
    uus[(tyhirida+nihe[0])*3+tyhiveerg+nihe[1]]="_"
    vastused.append("".join(uus))
 return vastused

algkoht="12346_758"
uuritavad=[algkoht]
tagasitee={algkoht:algkoht}
while uuritavad:
  uuritav=uuritavad.pop(0)
  for seis in sammuKaugusel(uuritav):
    if seis not in tagasitee:
      tagasitee[seis]=uuritav
      uuritavad.append(seis)
      
koht="12345678_"
if koht in tagasitee:
  teekond=[koht]
  while koht!=algkoht:
    koht=tagasitee[koht]
    teekond.append(koht)
print(teekond)