Because you only see one correct answer on Duo, and becauise it takes a long time for Duou to add all the acceptable translations, you'll get the impression that Italian is much more rigid than it is.
abbiamo farfalle sulle nostre scarpe would be perfectly acceptable.
One trick is to search for a phrase on google. I did "sulle scarpe" (213K hits) and "sulle nostre scarpe" (60K hits). You need the quote marks of course.
I didn't make the same mistake here as I did on another similar translation, but I would like to know if this phrase can also be translated as "We have butterflies on shoes." Is there a better way to say that in Italian?
I'm imagining, in this case, a sales person screaming this at a crowed. "We've got butterflies! We've got shoes! We've got butterflies on shoes!"