In a challenge-based game, the difficulty of the game will usually be a primary driver of the tension the player feels, and therefore the player's engagement (when done properly). What the actual difficulty (the chance of success or failure) does here is build anticipation (and therefore tension, which creates engagement). If there is no chance of success or no chance of failure, there will be no anticipation generated from the mechanics themselves (there could be anticipation from other elements). If a player fails multiple times, the anticipation will build, but only if the player feels they are getting closer and closer to succeeding each time (meaning the challenge has been broken down properly). This often means that the punishment for failure needs to be fairly small (especially if the chance of failure is high), or the player will spend too much time not feeling like they are getting closer to success (which will destroy the anticipation, which will destroy the tension, which will destroy the engagement). It is also easy for failure to turn into bad tension just because it feels unfair to the player. Failing in a way that the player does not think was their fault, or if they feel the punishment is too large for a minor mistake, can quickly destroy engagement.
In addition to mapping out a progression chain, games that have challenge as a core engagement type will need to consider how difficulty is handled over time--the difficulty curve. The amount of tension created by difficulty depends heavily on the skill level of the player. What is easy for a skilled player can be impossible for an unskilled player, and what is easy for an unskilled player can be boring for a skilled player. A lack of skill can also prevent mastery of skills needed to progress in the game.
Differences in skill can be accounted for through techniques such as player chosen difficulty settings, dynamic difficulty settings, increases in character abilities (as opposed to the player's skill), etc. However, the real problem is that a player's skill will increase as they play the game. So regardless of what overall difficulty level has been selected, the challenges presented must become more difficult at a rate that is not too fast (which could cause a tension overload if the player isn't ready for it) but not too slow (which could cause boredom if the player isn't being challenged at all).
Maintaining the proper amount of tension while a player's skill increases is called "flow". This is done by regularly introducing more difficult challenges (causing a spike in tension), then allowing the tension to release "naturally" due to the player's increasing skill as they attempt to overcome the challenge (which could take multiple tries). This relationship between difficulty and skill is shown on the chart to the right, with the goal being to stay in the middle channel between overload and boredom. The relative difference between difficulty and skill is the tension, which would look like a tension curve if it was plotted vs. time.
Note that a game cannot just keep the difficulty perfectly balanced with the player's skill (a diagonal line right through the middle of the chart, for example). The relative difference between the difficulty and the player's skill must go up and down (just not too high or too low) in order to build and release tension, which is the way to create engagement. Just slowly and continuously ramping up the difficulty will not work because the constant tension will cause burnout long before the game becomes really engaging.
Since perfectly predicting how quickly a player's skill will increase is almost impossible, games often provide many optional opportunities for players to practice skills until they have mastered them, at which point they can move on to other parts of the game. Some players may skip those practice opportunities because that skill is pre-mastered, others will only need to practice once or twice, while others may need to practice dozens of times. The important thing is to make sure those practice opportunities are optional, that they do not feel punishing, and that they are an interesting part of the game. The other standard way to handle this problem is to just give the player better equipment or abilities just for trying to master a skill (usually through acquiring currency or leveling up), so that the "skill" will eventually be easy enough for them to perform. This "pseudo-mastery" isn't really true mastery of a skill, but it functionally works the same and can feel just as good to a player.
Depth and complexity can change over time as the audience's model of the experience changes, which means the perceived elegance of the possibility space changes over time as well. Introducing new characters in a narrative increases the complexity of the viewer's model, but will increase the depth even more if the characters are well-written. Increases in skill in a game could add additional depth (as new actions become possible), while the discovery of a dominant strategy in a game could reduce depth. Introducing new mechanics in a game increases complexity (but can be worth it if even more depth is created), while a player discovering a way to simplify their model of the game (a good heuristic, for example) would decrease complexity.
Since high complexity is often a barrier to individuals engaging with an experience, a good strategy is to keep complexity low at the beginning of an experience, then gradually increase it by introducing new elements, making sure that those new elements result in an even greater increase in perceived depth. Ideally, this will cause the elegance ratio to increase over time. Using this strategy will inherently help create a good difficulty curve.
The chart to the right shows perceived depth, complexity, and elegance over time for a good trading card game (note that the values in the chart are logarithmic). The complexity starts out low with just the base rules, but the perceived depth is not very high either. As more cards are introduced, the complexity goes up (since each card can have its own rules on it that the player must understand), but the perceived depth goes up even faster as more and more interesting situations, tactics, and choices become available. This causes the elegance ratio to increase over time (quickly at first while all the fundamentally different card types are being introduced, a bit slower when the new cards are only somewhat different, and then not much at all when new cards start to feel really similar to cards that have already been introduced).