One example is Sudoku. It's NP-hard, but in practice, it takes no time at all to solve your newspaper puzzle.

NP-hard just speaks about the algorithm complexity. The input size of a typical sudoku puzzles so small that even the most naive algorithm can do it quickly.