You could just kill the snake....
A close look at the game's package may offer a clue.
Have you rubbed the lamp three times now?
You can put the bridle on the snake from a (barely) safe distance.
Did you try getting the low-down from the horse's mouth?
Get the key from the cave, and take the return carpet flight.