http://en.wikipedia.org/wiki/Travelling_salesman_problem#His... "In 2006, Cook and others computed an optimal tour through an 85,900-city instance given by a microchip layout problem, currently the largest solved TSPLIB instance. For many other instances with millions of cities, solutions can be found that are guaranteed to be within 2-3% of an optimal tour."

Once you're discussing real things, they aren't puzzles anymore. One of my favorite things to do in interviews is to just actually have a discussion, as peers, about a real-world technical problem with multiple potential tradeoffs and no one right answer.

If they can't get the naive brute force solution in a few minutes, that indicates something pretty bad. If they treat it as a permutation question and get the n! brute force answer, that is much better (and is still something that can be done in about the same amount of time. If you treat the problem as numbered permutations then checking for diagonals even becomes non-tedious, making it easier to write out on a whiteboard than the naive brute force solution).

If they get a proper solution in only a few minutes, you know that they either have their act together, or that they have seen the problem before and remember the solution. That in itself is a good indicator, though if they get a proper solution right away there should be some follow-up questions to get a handle on how exactly they were able to solve it that quickly.

This was a real problem for me as a programmer early in my career and a source of great anxiety on interviews. I've gotten better at it later in life almost solely because I needed to do so for interviewing purposes, but to be honest, I don't think it is a real world problem if someone isn't great at simultaneously reasoning through a complex problem and communicating while doing so. I suspect there is a large group of people like me who are very experienced and knowledgeable programmers who may come off poorly in whiteboard-coding interviews because actively focusing on complex problems makes it difficult for them to interact in the real world.

I do think being able to communicate is key for developers, but even when I had issues with this I could very clearly communicate how I went about solving the complex problem after I had finished it (or at least was convinced I was on the right track with one or two solutions and my mind wasn't running through the problem on dozens of different threads anymore) and it never impacted any real world collaboration because it is extremely rare that you ever sit around with a bunch of other programmers trying to reason through exactly the same algorithm at the same time, and even when that does happen, IME it is better to just get a few independent solutions and then communicate about the pros and cons of each rather than just "brainstorm" in real-time.

However, I'd be pissed off if the job turns out to be like 99% of most jobs, writing boring CRUD enterprise apps.