Incrementally, by tiny steps. Including a lot of doing first, then realizing later this is relevant to some chess/math thing.
Also the idea of "problems" like "chess problems" and "math problems" is itself constructed. Chess wasn't created by stacking together enough "chess problems" until they turned into a game - it was invented and tuned as a game for a long time before someone thought about distilling "problems" from it, in order to aid learning the game; from there, it also spilled out into space of logical puzzles in general.
This is true of every skill, too. You first have people who master something by experience, and then you have others who try to distill elements of that skill into "problems" or "exercise regimes" or such, in order to help others reach mastery quicker. "Problems" never come first.
Also: most "problems" are constructed around a known solution. So another answer to "how did the first humans solve" them is simply, one human back-constructed a problem around a solution, and then gave it to a friend to solve. The problem couldn't be too hard either, as it's no fun to not be able to solve it, or to require too much hints. Hence, tiny increments.