Could problem solving be the object of teaching in early education? Could appropriate teaching interventions develop to scaffold children's efforts to solve problems? These were the central questions of this article. The sample consisted of 18 children attending public pre-school in Cyprus. The problem they were asked to solve was to find all solutions of the pentomino. The children's problem solving was supported by graphically representing their solutions on squared paper. The findings show that children responded positively to the problem and were successful in finding all solutions for the specific problem. The graphical representation of the solutions and the forms of teacher-children and children-children interactions played an important role in the positive outcome of the activity. (author abstract)