Hey Dunin, the game that I'm making is actually really close to the third suggestion that you made. I'm hoping to procedurally generate a party with guests all moving around and talking, picking things up, putting things down. Then the murder happens and the murderer stashes the murder weapon somewhere.
The player has to question the guests and place everyone at each time. Then they would have to discover the murderer and locate the murder weapon.
I've got some ideas that should generate different unique solutions each playthrough. The tricky part is going to be making sure everything is solvable. I think I've got a method to make this possible.