One problem that's a personal curiosity for me has been this:
Given an inventory of train track pieces (my boys love Thomas), figure out what permutations make connecting, valid layouts. Report back any successful layouts, in descending order of complexity.
I've spent some spare cycles thinking about this one, and I've come to the conclusion that I'm just not smart enough. I could probably able to do it with straights, curves and a pot-load of coffee, but once you throw in switches and cross-over bridges -- fuggetaboutit.