Um, I just thought...
rand() uses an extremely reversible algorithm (linear congruential). All your mine-generation algorithms use rand() in some way, including the STL shuffle functions methinks. I *could* reverse the generation and discover your mines, without breaking any of the above rules, no? ;)