Well, it's not mine, it's by Abigail-II, and it may be sneakier than you intended, but the regular expression that made my jaw drop recently was the n-queen problem solver in Backtracking through the regex world. I'm not sure of its pedagogic value for beginners, but it's certainly a mind-expander.