Minesweeper

Clear the board without hitting a mine. Read the numbers, flag the danger and beat your best time.

Minesweeper shipped with Windows 3.1 in 1992, and Microsoft's stated purpose was teaching people to use the right mouse button — the flag. It descends from Mined-Out on the ZX Spectrum in 1983.

It is also a genuinely hard problem in the formal sense: deciding whether a given board configuration is consistent is NP-complete, proved by Richard Kaye in 2000. Most positions yield to local counting, but the ones that do not require reasoning across the whole board, and some boards contain positions where no amount of logic beats a coin flip.