While computer science and engineering students are trained to recognise familiar problems with known solutions, they may not be sufficiently prepared to address novel real-world problems. A successful computer science graduate does far more than just program and we must train our students to reach the required levels of analytical and computational thinking, rather than hoping that it will just 'develop'. As a step in this direction, we have created and experimented with a new first-year level course, Puzzle-based Learning (PBL), that is aimed at getting students to think about how to frame and solve unstructured problems. The pedagogical goal is increase students' mathematical awareness and general problem solving skills by employing puzzles, which are educational, engaging, and thought provoking. We share our experiences in teaching such a course – apart from a brief discussion on our pedagogical objectives, we concentrate on discussing the presented material which covers (in two lectures) just one selected topic (pattern recognition). In this paper we present the ideas behind foundations for PBL and the material of the first of two lectures on pattern recognition, in which we address core concepts and provide students with sufficient exemplars to illustrate the main points.