Sokoban is one of the most respected puzzle games ever made — a Japanese design from 1981 whose rules fit in a sentence: you push crates around a warehouse onto marked targets, and you can only push, never pull.
That single restriction is what makes it deep. A crate pushed into a corner is stuck forever, and a crate pushed against a wall can only move along it. Solving a level means seeing several moves ahead to which pushes are irreversible, which is why Sokoban is studied in computer science as a genuinely hard planning problem.
You push crates onto marked targets and can only push, never pull. Every level is solvable, but many pushes are irreversible — which is the whole difficulty.
Because pushes can't be undone in-world, small mistakes make a level unsolvable without a restart. It's studied in computer science as a benchmark planning problem for exactly that reason.
It dates from 1981, designed by Hiroyuki Imabayashi in Japan, and has been ported and imitated continuously since.