1. Puzzles should be just one of many different parts of the interview.I agree with most of this approach, but I still feel that everyone needs to be very cautious about using puzzles that are basically brain-teasers. In the first comment on Albert's post, one of the readers made part of my point for me - they posted a potential puzzle, and it was immediately pointed out that is well known amongst the brain-teaser set. I posted a fairly lengthy response on Albert's blog, but I figured I might as well cross-post it here.
2. Try to find a set of puzzles that works for you and use the same puzzles with many candidates to get better comparability.
3. Focus primarily on approach and behavior and only secondarily on outcome.
4. Unless the position specifically calls for ability to think under stress (e.g. certain ops positions), try to put the candidate at ease. Being in an interview is stressful for many folks.
5. Ask for a vocalization or visualization of the thought process.
At the core, the most important distinction is between coding/algorithm puzzles and brain-teaser puzzles.
E.g., one of the best interview questions I've ever been asked basically boiled down to performing bipartite graph matching - it required deep understanding of algorithms and how to match them to real-world problems, and then being able to implement the code behind them - pure awesome.
On the other hand, some of the worst interview questions I've encountered are the form of "N pirates have to divide X gold among themselves" or "You're blindfolded in a room wearing a hat..."
Brain-teaser questions tend to have the drawback that they are very uneven - for people who love brain-teasers, many brain-teasers are well-known or simple variations on existing problems, but for people who don't, they're starting without the benefit of any of the background.
In addition, in my time at Google I saw heavy anecdotal evidence that brain-teaser aptitude correlates negatively with overall effectiveness as a developer. Sometimes the developer who searches too hard for clever solutions winds up missing the simple solutions.