Five philosophers sit around a circular table. In front of each philosopher is a large plate of rice. The philosophers alternate their time between eating and thinking. There is one chopstick between each philosopher, to their immediate right and left. In order to eat, a given philosopher needs to use both chopsticks. How can you ensure all the philosophers can eat reliably without starving to death?
Odd numbered philosophers pick up the right chopstick first and then the left, while even numbered philosophers pick up the left chopstick first and then the right.
A salesperson has a route of cities that make up his or her beat. What's the most efficient sales route that visits each city exactly once, and then returns to the home city?
Given eight queens on a standard 8 x 8 chessboard, how many unique positions-- exclusive of rotations and mirror images-- can those eight queens occupy without attacking each other?
Two armies, each led by a general, are preparing to attack a city. The armies are encamped outside the city on two mountains separated by a large valley. In order to capture the city, the generals must attack at exactly the same time. The only way for the generals to communicate is by sending messengers through the valley. Unfortunately, the valley is occupied by the city's defenders, so there's a chance any given messenger will be captured. Each general has no way of knowing if their messenger arrived. How do the generals coordinate their attack?
You have a stack of discs, from largest to smallest, that slide on to the first peg of a three peg board. Your goal is to move the entire stack of discs from the first peg to the third peg. However, you can only move the topmost disc of any peg, and smaller discs must always be placed on larger discs. How many moves will it take? I consider this the "greatest hits" of classic computer science puzzles. But I'm sure I've forgotten a few. Are there any other puzzles I've missed that express fundamental computer science concepts, the type that would be taught in a typical undergraduate computer science course?