I did it recently without a staircase within one afternoon. The Galaxy Sword is very useful to make short work of those damned flying serpents and one or two ghosts. I don't engage with the mummies at all if it can be avoided, have a coffee or a Spiced Eel, carry a lot of bombs, thus dashing through every floor looking for an open staircase or - muchmuch better! - a shaft, and if there is none, I bomb my way through.
Of course it's a matter of luck. In my recent run-through I found at least three shafts, every one several levels deep. Which means you better go there on a lucky day (when the spirits are happy). But with a Galaxy Sword, a good many bombs and enough food (melons are good, cheese too) in your backpack and possibly some speed-ups such like coffee or Spiced Eel, you should be able to make it within a day.