Good programming puzzle requiring a lot of conditional logic?

开发者_开发知识库What is a classic programming puzzle which will require a lot of conditional logic and branches to solve?

Thanks

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

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

Sudoku

Here are a lot of small programming puzzles. a Lot of them are about logic

If the purpose is for an interview (i.e. you need to have a candidate bang out some code as part of the evaluation process), I've always liked Project Euler question 11.

If it's for your own use to learn a new language, etc. I prefer some of the code kata at codingdojo.org (the OCR one is pretty entertaining in any language).