For anyone who wants to play Minesweeper without the hassle of trying to track down a known-good *.exe, I recommend Minesweeper X [0]. The board size isn't limited plus a ton of other features. It also works perfectly under WINE with Winetricks.
https://www.chiark.greenend.org.uk/~sgtatham/puzzles/
It has an option to "ensure solubility" similar to the one @gergoerdi mentions above.
http://linux.softpedia.com/get/GAMES-ENTERTAINMENT/Puzzle/GN...
And as always with old XP era exes: ReactOS has its own compatible copies and you can use them in Windows and they will usually work (minesweeper from ReactOS does work on Windows 10, I just checked).