I think that’s an important distinction to make when exploring what is or isn’t a puzzle game. There are lots of games where flawless execution matters as much as knowing what to do. For example, FPS games lean heavily towards the execution aspect while mixing in some solution identification too.
The purest examples of each game design style are also interesting. For example, you can play chess through snail mail, so being physically able to perform specific actions isn’t really necessary for victory. In the opposite end of the spectrum you have the simplest form of darts, which is all about skill. Just throw all the darts at the center and you’ll win. There are also more complicated versions for those who want to play a game that sits somewhere in the middle of this puzzle-execution specturm. Now that I think of it, most computer games seem to be a mixture of the two styles.