Perhaps an interesting twist might be to start with something apparently impossible, then make a map based on justifying it somehow other than "magic did it."

Of course, that sounds like a completely different challenge. I think this is a good idea, but it has to be presented carefully to avoid a flood of no effort maps.