def vaiCavalo( origem, destino ):
   casasTestadas = [[False]*8 for i in range(8)]
   passos = [origem+[[]]]
 
   while True:
      proximosPassos = []
      for passo in passos:
         for movimento in [[-1,-2],[-2,-1],[-2,1],[-1,2],[1,2],[2,1],[2,-1],[1,-2]]:
            x,y = passo[0]+movimento[0], passo[1]+movimento[1]
            if [x,y] == destino:
               return passo[2]+[[x,y]]
            if 0 <= x < 8 and 0 <= y < 8 and not casasTestadas[x][y]:
               proximosPassos.append([x,y,passo[2]+[[x,y]]])
               casasTestadas[x][y] = True
      passos = proximosPassos
 
print("Caminho feito:\n", vaiCavalo([1,1],[7,7]))

ZGVmIHZhaUNhdmFsbyggb3JpZ2VtLCBkZXN0aW5vICk6CiAgIGNhc2FzVGVzdGFkYXMgPSBbW0ZhbHNlXSo4IGZvciBpIGluIHJhbmdlKDgpXQogICBwYXNzb3MgPSBbb3JpZ2VtK1tbXV1dCgogICB3aGlsZSBUcnVlOgogICAgICBwcm94aW1vc1Bhc3NvcyA9IFtdCiAgICAgIGZvciBwYXNzbyBpbiBwYXNzb3M6CiAgICAgICAgIGZvciBtb3ZpbWVudG8gaW4gW1stMSwtMl0sWy0yLC0xXSxbLTIsMV0sWy0xLDJdLFsxLDJdLFsyLDFdLFsyLC0xXSxbMSwtMl1dOgogICAgICAgICAgICB4LHkgPSBwYXNzb1swXSttb3ZpbWVudG9bMF0sIHBhc3NvWzFdK21vdmltZW50b1sxXQogICAgICAgICAgICBpZiBbeCx5XSA9PSBkZXN0aW5vOgogICAgICAgICAgICAgICByZXR1cm4gcGFzc29bMl0rW1t4LHldXQogICAgICAgICAgICBpZiAwIDw9IHggPCA4IGFuZCAwIDw9IHkgPCA4IGFuZCBub3QgY2FzYXNUZXN0YWRhc1t4XVt5XToKICAgICAgICAgICAgICAgcHJveGltb3NQYXNzb3MuYXBwZW5kKFt4LHkscGFzc29bMl0rW1t4LHldXV0pCiAgICAgICAgICAgICAgIGNhc2FzVGVzdGFkYXNbeF1beV0gPSBUcnVlCiAgICAgIHBhc3NvcyA9IHByb3hpbW9zUGFzc29zCgpwcmludCgiQ2FtaW5obyBmZWl0bzpcbiIsIHZhaUNhdmFsbyhbMSwxXSxbNyw3XSkp