Traffic Jam is a physical sliding puzzle that teaches sequential and recursive thinking: https://tinyurl.com/yxav6zx4

There's also a 1-dimensional version you can play in a classroom with people or on a table w/ coins or chess pieces: https://www.youtube.com/watch?v=KizRWfuT5uQ