A polyomino puzzle is a collection of polyominos that can be joined to make a simple shape. The game Ten-Yen was one of the first of these. It has ten polyomino pieces that could be used to make a 6×6 square in a variety of ways. In this study we define representations and fitness functions for generating polyomino puzzles as well as developing a simple solver to compare the evolved puzzles. The solver can be used to approximate the number of solutions and hence the relative difficulty of the puzzles. Two types of fitness functions are compared, the second of which was developed to deal with scaling issues that arose with the first. A parameter study on the algorithm is performed and it is found that simply penalizing bad results is more effective than parameter tuning. This study concludes by discussing potential puzzle variants.