# encoding=utf-8   ## por causo dos comentários com acentos
 
def queue(x=[]) : return x      ## definição rápida de uma fila...
def enqueue(q,x): q.insert(0,x)
def dequeue(q)  : return q.pop()
 
 
def vaiCavalo(orig,dest):        ## vaiCavalo is © Bacco
   saltos = [(-1,-2),(-2,-1),(-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2)]
 
   visitada = [[False]*8 for i in range(8)]
   ts = queue([orig+(0,)])             ## fila das tentativas=[(x,y,nivel)]
   path={ 0:orig }
 
   while ts:                           ## enquando há mais tentativas
      nx,ny,lev = dequeue(ts)          ## get proxima tentativa
      path[lev]=(nx,ny)
      if (nx,ny) == dest :
          return ("found",lev,path)
      for dx,dy in saltos:             ## agendar novas tentativas
          x,y = nx+dx, ny+dy
          if 0 <= x < 8 and 0 <= y < 8 and not visitada[x][y]:
              enqueue(ts,(x,y,lev+1))
              visitada[nx][ny] = True
 
   return "not found"
 
print("passos feitos:", vaiCavalo((3, 2),(3, 3)))

IyBlbmNvZGluZz11dGYtOCAgICMjIHBvciBjYXVzbyBkb3MgY29tZW50w6FyaW9zIGNvbSBhY2VudG9zCgpkZWYgcXVldWUoeD1bXSkgOiByZXR1cm4geCAgICAgICMjIGRlZmluacOnw6NvIHLDoXBpZGEgZGUgdW1hIGZpbGEuLi4KZGVmIGVucXVldWUocSx4KTogcS5pbnNlcnQoMCx4KQpkZWYgZGVxdWV1ZShxKSAgOiByZXR1cm4gcS5wb3AoKQoKCmRlZiB2YWlDYXZhbG8ob3JpZyxkZXN0KTogICAgICAgICMjIHZhaUNhdmFsbyBpcyDCqSBCYWNjbwogICBzYWx0b3MgPSBbKC0xLC0yKSwoLTIsLTEpLCgtMiwxKSwoLTEsMiksKDEsMiksKDIsMSksKDIsLTEpLCgxLC0yKV0KCiAgIHZpc2l0YWRhID0gW1tGYWxzZV0qOCBmb3IgaSBpbiByYW5nZSg4KV0KICAgdHMgPSBxdWV1ZShbb3JpZysoMCwpXSkgICAgICAgICAgICAgIyMgZmlsYSBkYXMgdGVudGF0aXZhcz1bKHgseSxuaXZlbCldCiAgIHBhdGg9eyAwOm9yaWcgfQoKICAgd2hpbGUgdHM6ICAgICAgICAgICAgICAgICAgICAgICAgICAgIyMgZW5xdWFuZG8gaMOhIG1haXMgdGVudGF0aXZhcwogICAgICBueCxueSxsZXYgPSBkZXF1ZXVlKHRzKSAgICAgICAgICAjIyBnZXQgcHJveGltYSB0ZW50YXRpdmEKICAgICAgcGF0aFtsZXZdPShueCxueSkKICAgICAgaWYgKG54LG55KSA9PSBkZXN0IDoKICAgICAgICAgIHJldHVybiAoImZvdW5kIixsZXYscGF0aCkKICAgICAgZm9yIGR4LGR5IGluIHNhbHRvczogICAgICAgICAgICAgIyMgYWdlbmRhciBub3ZhcyB0ZW50YXRpdmFzCiAgICAgICAgICB4LHkgPSBueCtkeCwgbnkrZHkKICAgICAgICAgIGlmIDAgPD0geCA8IDggYW5kIDAgPD0geSA8IDggYW5kIG5vdCB2aXNpdGFkYVt4XVt5XToKICAgICAgICAgICAgICBlbnF1ZXVlKHRzLCh4LHksbGV2KzEpKQogICAgICAgICAgICAgIHZpc2l0YWRhW254XVtueV0gPSBUcnVlCgogICByZXR1cm4gIm5vdCBmb3VuZCIKCnByaW50KCJwYXNzb3MgZmVpdG9zOiIsIHZhaUNhdmFsbygoMywgMiksKDMsIDMpKSk=