I actually solved this problem in my first year of learning programming; mind you I didn't have a computer, only (limited)access to it at college. The only thing I knew was recursion. I thought hard for 3 days, discovered (he hee..) back-tracking and found the solution. For some reason, I cannot solve interview puzzles, and tried and failed to get into Google and FB.