Speaking of chess, you might be able to argue that some old RTS games are puzzle games when playing campaign, such as the first Command & Conquer. You often have very limited resources, the AI will do specific things at specific times or with specific triggers, and you're often given specific constraints, like a time limit or keeping a specific thing alive. In this case, though, it's mostly because the AI is so primitive that almost every action is scripted in advance for that specific map.