Part 1 turned out to be what I'd consider balanced for difficulty: it had a clearly-correct answer, and took about half a day to be solved.
Part 2 was an unmitigated disaster: it took 20 minutes to solve, and someone else guessed the end-game I had planned.
Part 3 was in between the two - it took about 4 hours to solve.
It's obviously very easy to just carpet-bomb the puzzle with red herrings all over the place, littering it with irrelevant clues. I feel that's a bit blunt though.
The converse is just as bad: if the puzzle only contains relevant information then someone can start anywhere and pretty quickly figure out the answer.
What I'm wondering is given an only-relevant-information detective puzzle, how much distraction should I add? As a supplementary question, how can I judge it to try to strike a balance between the solution and the red herrings?