While I enjoy puzzles, if they were to be integrated into a story, then the story would have to be
very compelling. And I agree with dadioflex, it sounds a bit like some adventure games, especially the Infocom and other great interactive fiction games of yore. Still, I'm up for it!
And for anyone who likes non-conventional stories that need to be untangled for maximum enjoyment, I'd like to suggest
Milorad Pavic's Dictionary of the Khazars and
Italo Calvino's Castle of Crossed Destinies.