You should monetize with paid hints. I've got a similar game in the App Store (I'll be polite and skip linking to it) and as of this morning, 53.8% of my total revenue has come from hint packs.

To see what I mean by hints, see this HTML5 port of my game I've been doing (work in-progress): http://noisytyping.com/NCT6745/index.html