> towers of hanoi is also in P-space, has a trick to latch onto, and is still popular

Is it? It's popular to introduce people to, and it's fun to play with for a bit, but once you understand how to solve it, there's basically no value in replaying it.