I just remembered something:
A while back I visited China (yeah, a long while back) and we went to several temples. At one of them, there was this test you had to pass in order to qualify to join the order. It was a large stone ball, probably 250-300 lbs. or so, in a round, stone bowl. The object was to get the ball out of the bowl. Now the width of the bowl made just reaching in and picking it up exceedingly difficult and only a very large and strong person would be able to do that. I am neither of those things (though of higher-than-average-height for China). But, I was able to successfully get the stone ball out of the bowl. I did it by rolling the ball until I could propel it up, onto the wide ledge of the bowl, at which point it was out. What type of challenge would that be? Strength? Agility? Reasoning? A combination?
I don't know about your players, but I much prefer the puzzle to be something that I (the player) can work out without it just being a bunch of dice rolls. Of course, you players may prefer the dice rolls and that is absolutely fine; you know them so you know which approach to use. (Or something in-between or something completely different.)