I imagine our goal is to work with how boss-fights is to boss fighting strategies, we need a tag that is that same relation to puzzle solutions.
Which makes me say puzzles.
I don't want to use puzzle-solving, because
puzzles matches closer to what we have. Most of our tags of this class talk about the element we're looking at - we're looking at boss fights, we're looking at mechanics, we're looking at items. We don't use
item-explanation, so in that vein, puzzles fits a lot better.
I'd like to think about how non-puzzle type challenges fit into there (say, gauntlet rooms), in which the more frustrating ones can be very much the same inspiration for questions as puzzles may be. But that's probably a subject for another question.
This is actually how puzzle is already half being used. Since we want to phase out genre tags from gameplay questions, then it fits pretty well. Many of the actual puzzle-game questions tagged with this can keep the tag because they're asking about how to solve a puzzle. The ones actually referring to the genre, I would suggest puzzle-game.