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

nihked=[[-1, 0], [0, -1], [1, 0], [0, 1]]
seis="1234567_8"

def kysiAlamseisud(seis):
 tyhinr=seis.find("_") 
 tyhirida=tyhinr // 3
 tyhiveerg=tyhinr % 3
 alamseisud=[]
 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]]="_"
    alamseisud.append("".join(uus))
 return alamseisud
 
leitud=[seis]
tagasitee={seis:None}
veel=True
loppseis="12345678_"
while leitud and veel:
  uuritav=leitud.pop(0)
  for abiseis in kysiAlamseisud(uuritav):
     if abiseis not in tagasitee:
       tagasitee[abiseis]=uuritav
       leitud.append(abiseis)
       if abiseis==loppseis: veel=False
       
print(tagasitee)
koht=loppseis
teekond=[]
while koht:
  teekond.append(koht)
  koht=tagasitee[koht]
teekond.reverse()
print(teekond)


print("ühe käiguga lõpus" if loppseis in kysiAlamseisud(seis) else "ei saa ühe käiguga")