I recently got into climbing (+ bouldering). Although I get super bored at regular gyms, I never bore of climbing, I think, because it's like programming -- for the body. Problem solving applied to an element that is both sociable and physical.
I also got bored at regular gyms, and realized that combat-oriented martial arts may be the ultimate problem-solving challenges. You have to muster all your intellectual and physical capabilities "against" an intelligent opponent who acts/reacts "in realtime", but also is prepared to it (the boulders layout is carefully crafted beforehand, but it doesn't react!). Jiu-jitsu may be one of the most adequate because it seems not as dangerous as striking arts (albeit by becoming competitive one may gain serious back-related aches or even injuries).
Agreed with the combat-oriented sports being the ultimate problem-solving challenge. Used to box (still occasional do), have never obtained the same technical satisfaction anywhere else. There are so many different facets to it. Ring generalship, creating angles, stances that gain or lose out on defensive or offensive capabilities, psychological game by use of feints and disruptive rhythms. It's not called the sweet science for nothing. Should hold true for other combat sports as well.
There's freedom in it: sometimes I wanna play chess; other times: just checkers.