Most students struggle when faced with complex and open-ended tasks because the strategies taught in schools and universities simply require finding and applying the correct formulae or strategy to answer well-structured, algorithmic problems. For students to develop their ability to solve ill-structured problems, they must first believe that standardized procedural approaches will not always be sufficient for solving engineering and scientific challenges. In this paper we document the range of beliefs university students have about problem solving. Students enrolled in a physics course submitted a written reflection both at the start and the end of the course on how they solve problems. We coded approximately 500 of these reflections for the presence of different problem-solving approaches. At the start of the semester over 50% of the students mention in written reflections that they use Rolodex equation matching, i.e., they solve problems by searching for equations that have the same variables as the knowns and unknowns. We then describe the extent to which students’ beliefs about physics problem solving change by the end of a semester-long course that emphasized problem solving via context-rich, multifaceted problems. The frequency of strategies such as the Rolodex method reduces only slightly by the end of the semester. However, there is an increase in students describing more expansive strategies within their reflections. In particular there is a large increase in describing the use of diagrams, and thinking about concepts first.