I'm going to provide a counter-example to disprove. A slot machine is a video game that is not a puzzle since there is no solution.
I agree with "Most video games are puzzle games" though. There are exceptions like Rail Shooter. Button mash only game. Bullet hell games don't really have a puzzle element since solution is already shown by areas having no bullets in them.
I feel like this statement also hinges on "all video game strategy is a puzzle" people might disagree with.