There are multiple factors to consider (as always). As you posted a link to your game, I also want to talk about the specific implications for your special case.
1. Player responsibility
This was already explained quite nicely by @Anko. If the player feels like he is actually responsible for his failure and has a chance to improve via the knowledge he gained by failing, he is more tempted to do so.
With games that contain somewhat randomly generated content like The Binding of Isaac and probably your puzzle game, that is quite a hard goal to accomplish on a higher difficulty. On most of such games, you can fail very hard or win very high without actually playing better or worse.
You could of course go with hand-crafted levels, or use the method I'll explain in #3.
2. Instant restart
Not necessarilly a huge point, but definitely important: Enable players to restart instantly. If they feel like they messed up or did indeed fail a level they need to be able to restart in a moments notice so that neither gameplay is interrupted nor thought is distracted. With all skill-based games, you are learning by doing, and the less time you spend doing in a session, the less you learn in a session.
Additionally, interruptions can be frustrating. Especially with the short attention span your game gets on a mobile platform, make every second count. A very good example is Super Hexagon where you can restart so instantly, it doesn't even always feel like failure. As a counter-example, Space Run has a 5-10 second cutscene and requires you to redo your ship configuration on every restart, which is very critical as it is a difficult, failure-base game.
3. "I nearly did it!"
As an addition to player responsibility: you can fool the player, which isn't necessarily a bad thing.
You would need a somewhat dynamic difficulty level which makes the game a bit harder or a bit easier depending on how the player does at the moment. This can emulate the feeling of being in control, but you have to be careful to not overdo it. In your case, if you detect the player is running behind, give him a few more words so he can catch up to the goal and barely make or not make it.
This way, if he fails, he will be more compelled to try again, or (and this is where the success of Candy Crush lies), make him buy a few extra moves or extra time to complete the level. Extra Credits has an excellent video on the topic. This would of course be an excellent hook for monetization.
4. Rewards
Only indirectly related to difficulty, let players unlock achievements or trophies, show them cool animations for good combos, make them feel like they're working towards a goal even if the odds aren't quite in their favour right now. Most First-Person-Shooters use this principle these days and they have good reason to do so, as they operate in a high-frustration/high-reward field.
There they are, my two cents on the topic. Keep in mind that you may want to question my reasoning to let your own thoughts and ideas emerge.