Software developers do have a proclivity for puzzles. Perhaps that's why books like To Mock a Mockingbird exist. It's a collection of logic puzzles which is considered an introduction to lambda calculus, one of the core concepts of Lisp.
Interesting way to tie puzzles back to what programmers really do. However, I still think even these are useless for most jobs since these puzzles focus on comp sci problems and hardly any jobs do. Most jobs are about building CRUD application. What good is puzzle solving if you job revolves around storing stuff in a database, reporting on it and transforming it?
Re: random “solving” the two generals problem
The problem isn’t asking for a solution that works most of the time, it’s asking for a solution that works no matter what. The whole point is that such a solution is impossible.
It’s definitely possible (and not very hard) to come up with a strategy that works 99.99999% of the time (for as many 9s as you want).
Jeff,
I’m a big fan of Dennis Shasha’s “Dr. Ecco” series of books and magazine puzzle columns. If you’ve never read any of them, I’d encourage you to take a look.
It’s not that LISP is dense and impenetrable, although Common Lisp took it a good long way down that road. Unfortunately, many Lisp programmers were dense and impenetrable.
Lisp had a lot of nice features that never got used because Lisp vendors never understood their market, outside of research universities.
I remember one called the “Sleeping Barber” problem, related to communication between separate processes.
If I recall correctly, the eight queen problem is not about how many queens can be placed, the number of queens is always N for a NxN chess board. The problem is how to place the queens, and how many different solutions there are.
Here’s a great history of the traveling salesman problem.
http://www.tsp.gatech.edu/index.html
If you prove this is a NP-complete problem (not just NP-hard), you could win a $1,000,000 dollar millennium prize:
Boston only has two outbound routes and New York only has inbound routes, therefore the problem can not be solved. 
Also, the two generals problem is easily sovlable in the real world - you acknowledge the fact that a transaction may fail, and include sufficient auditing and administration tools to allow detection and repair of failures. And for those who haven’t studied the real world, the probability of six thousand messages being lost (after the first one is lost, given a dumbass with a backhoe hitting the network link at the wrong time) is approximately 100%. Any system designed with a suitable strategy to cope with a failure (whether the probability of failure is 99.999999999% or 0.000000001% will be equally effective.
The problem can not be solved - but in the real world you can always have a plan B to account for the reality.
Honestly, you can whinge about “probability” all you like, but if “the chance of failure is the same as your chance of winning the lottery” is your justification for not providing a strategy to cope with errors then I don’t want to use your software. And if you do provide quality software, then you’re acknowledging that there is always a possibility of failure.
Besides, if you try the “6 acknowledgement messages and then commit” approach to transactional reliability, your system will be a lot slower than most, and lets be fair - the odds of a network outage that can’t be automatically repaired pretty quickly is already quite low.
I’ve a coworker dealing with management of an outsourced program who is backtracking on just about everything she promised in writing, including giving the money back.
I’d love to see a similar problem used for the yet-to-be-hired programmer to figure out.
And honestly, isn’t dealing with people one of the hardest puzzles out there
Because of the nature of the situation, truthful and accurate, I can’t post my name, but I’m a regular reader.
as for other “fundamental” puzzles - perhaps the classic “conway’s game of life”? not an actual puzzle (althought you can create puzzles using it) but quite scientific and entertaining at the same time.
Einar, thanks for the correction. I didn’t quite finish writing the Eight Queens description up and I didn’t realize it before I pressed the post button. The question is not “how many queens can exist on a chessboard of a given size without attacking each other” (although that’s interesting, too).
the two generals problem is easily sovlable in the real world -
If two generals is too easy, you should move on to byzantine generals.
http://en.wikipedia.org/wiki/Byzantine_fault_tolerance
You now have (n) generals who must decide to attack unanimously. And here’s the other twist: some of them are traitors.
I think all job interviews are missing one essential skill test: can the person touch type?
There’s something wrong if you work in tech and you still have to hunt-and-peck and look at the keyboard while you type.
Screw hiring smart people – hire people who don’t make typos.
Short of spending a day looking over the shoulder of a candidate, there really is no remotely save way to be sure that they are capable enough to hire. Gets even worse if you have to hire someone to do something that YOU YOURSELF don’t understand (aka some expert sub-field). It’s odd that programmers with their desire to solve problems haven’t come up with a decent hiring solution yet.
By the way, you forgot the “sleeping barber”, a classic programming problem to process communication and synchronicity (is that a word ?) that involves deadlocks and starvation.
Good article about it: http://en.wikipedia.org/wiki/Sleeping_barber_problem
“Screw hiring smart people – hire people who don’t make typos.”
That’s why static type systems were created.
I love these puzzles: http://projecteuler.net.
I don’t know about others, but the problems I solve at work often look a lot like some of these puzzles.
–Donnie
The majority of developers to develop CRUD apps for IT shops, but there’s still a good number of us out there who work on more complex systems… embedded environments, physics simulations, routing, graphics, protocols, kernels, etc. I’ll be the first to say that solving these puzzles goes a LONG way toward success in those environments. I use this stuff every day.