Writing puzzle-solving and game-playing programs can generate excitement in students. Such programs are usually assigned as projects in an AI course. These are major software projects expected to be completed by students who usually have had no prior instruction in SE concepts. Often, these are required to be implemented in languages and paradigms in which the students have minimal expertise resulting in frustration among students as well as faculty. We discuss a "problem stereotypes and solution frameworks" approach to teaching CS1/2 (most likely prerequisites to AI) which ensures that the students have exposure to a judicious amount of SE methodology. We extend this approach to teaching an AI course by identifying the State-Space-Search and Two-Person-Zero-Sum-Game stereotypes. We have developed a solution framework (consisting of Java abstract classes) that can be used to solve typical problems falling into these stereotypes. Using the framework, a student will be able to develop a puzzle-solver or a game-player program mainly by focusing on problem-specific details. Preliminary experimentation has revealed that the students found it easy to use the framework and were successful in developing puzzle-solvers. We believe that our approach based on reusable software infrastructure enables students to develop interesting programs early in their undergraduate careers.