The pedagogical method known as Problem-solving Based Learning (PBL), which is the basis for the curricula of a number of universities in other countries, is analyzed and applied to a particular situation. The idea is to face the student to a set of well defined problems during a course, on a project-based basis, letting the task of “information assimilation” to the student by means of books. Some guidelines that may help in the implementation of these pedagogical methods without the need of going through such a radical system as that originally proposed, and that could fail in LatinAmerican cultures, are outlined. An example of the application of these ideas the development of an automated Sudoku-solver to study the NP-completeness theory in computer science is presented. It is concluded that the teaching-learning process is more efficient using these new approaches than the traditional ones.