I had this idea in mind a while back, the Mono-AttackType challenge. Basically, your Pokemon's moves must correspond to their type.
For example, a Blastoise would only be allowed to use a moveset such as Surf, Hydro Cannon, Withdraw, Rain Dance, all of which are Water type. (Obviously by considering this, dual-type Pokemon are a lot more useful probably)
Coming off my mind right away are moves such as Confuse Ray which could only be present on Ghost Pokemon.
The rule would be that you must delete moves of type not matching that Pokemon as soon as possible, either by overwriting them with the appropriate moves or deleting them. It would be a must to enforce that by the time you meet the move deleter, you MUST delete all non-matching type moves.
An alternative way to make the challenge easier to implement would be to do it the other way round, i.e. your Pokemon's moves must NOT be of the same type as the Pokemon itself; i.e. a Charizard with Earthquake, Rock Slide, Swords Dance and Dragon Claw.
(This would make the challenge much easier, imo, as you have a lot more coverage, though you lose STAB)