I don't think I've ever heard of Demon's Souls being categorized as a puzzle game. I suppose some of the bosses have a trick to figure out? But I'd still think it falls into the action RPG genre by a wide margin.
Imo it's better to approach Demon's Souls as an exploration puzzle game with RPG stuff and combat, not as an action RPG (such as Dark Souls 3).