What are some problems that are simple on the surface but require a strong ability for planning your actions and "reasoning" through the process? Chess and Go fit the description but are too complex. Doing math proofs is an excellent test in reasoning, but requires immense background knowledge, whereas I'm looking for something with a simple goal and a simple set of rules.

A perfect example would be the "Sokoban" puzzles, which were used as a metric in the Beyond A* paper. What are some problems similar in nature? Even simple text-based or arithmetic problems that require predicting the future and taking actions accordingly would fit the criteria.