You should just use some descriptive words like "Simple," "Intermediate," and "Complex." A number of stars is just that: A number. And if you use a number, than you have to explain the unit of measurement. Why do that when natural language offers words specifically meant for this situation?
For the best implementation, I would give each word a tooltip that goes into a bit more detail. For example, if you mouse over the word "Simple," a tooltip might appear saying "Easy and straightforward--great for exercising your use of language syntax." If you mouse over "Complex," it might say "Deeper and more complicated--great for practicing problem solving and simple design patterns." (These look to me like programming challenges, hence my tooltips talking about them like that.)
If you're worried that using English words will make it harder to scan a list of challenges, then I would experiment with color and typography to give the difficulty indicator more visual weight. Of course, you should also have sorting functionality.
Edit: Regarding mobile interfaces, I would place a small question mark icon next to the difficulty indicator. Tapping on the question mark would display a list of all the difficulty ratings at once, which could then be closed to return to the parent view. Question mark icons would add some clutter, though. It might be best to provide mobile users with an "intro" page they cycle through, where things like the difficulty rating are explained. That way, you can justify getting rid of the icons because users will already know about them.