Sudoku
One solution, checked after every removal
The grid is filled completely, then clues are removed one at a time. After each removal the puzzle is solved again from scratch; the moment a second valid answer appears, that clue goes back. A hard 9×9 removes about fifty clues, so the solver runs about fifty times per puzzle. This pass is slow, which is why it is often skipped — and invisible until someone fills a grid legally and is told they are wrong.
The check is exponential, so it runs on 4×4 and 9×9. On 16×16 it would take too long and is skipped.