Good programming puzzle requiring a lot of conditional logic?

Question

What is a classic programming puzzle which will require a lot of conditional logic and branches to solve?

Thanks

Answer 1

Eight queens and Towers of Hanoi are classics. Solving Sudoku is quite interesting too and is really a graph coloring problem in disguise.

Answer 2

I like the problem of writing a function that computes the least number of multiplications to compute x^N (e.g., for N = 30, you can compute x^N with 6 multiplies - x -> x^2 - > x^3 -> x^5 -> x^10 -> x^15 -> x^30.

There's no known efficient algorithm, so you have to use branch-and-bound. The conditional logic and branching come in when you are trying to bound. See this wikipedia article for more details - http://en.wikipedia.org/wiki/Addition_chain