It's Puzzle time after a long time!

It's been ages since I posted anything related to puzzles. I just came across this beautiful post by Jeff Atwood where he talks about some of the Classic Computer Science Puzzles. This post made me nostalgic and took me back in time to my college days. Though not a puzzle Ackerman function fascinated me a lot. You can read more about it in a previous post of mine. Coming back to Computer Science Puzzles, many of us feel they lack the real life implications. I disagree here.

Check this post of mine where I discuss how Domino's has to apply a variation of TSP to solve their delivery issues. The Graph coloring problem is a something that is visible to all of us who have anything to do with maps. Yes, I do agree most of the problems may not find a direct application to the things that we do daily. But, if we think a little some of the real life issues can be addressed with these theoretical stuff(not all mind you!).

With this I stop here, and reproduce the puzzles that Jeff refers to in his post.

"

Dining Philosophers Concurrency and Deadlocks	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?
Travelling Salesman P=NP	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?
Eight Queens Algorithm Design	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 Generals Communication Protocols	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?
Towers of Hanoi Recursion	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?

"
Do you know of more such puzzles? Drop in the comments section. Nothing can be more fun than solving a hard puzzle.

Related Posts:
The Domino's Dilemma
Challenge Your Computer
Crazy Guy on the Plane
Catch the Chicken


Liked this Post: Subscribe to the RSS feed to get the posts to you. You have the advantage of getting my deli.cio.us links on the feed.