good structure, but the list of acceptable eyes, noses and mouths is created again and again every time a validation method is called.
Creating and storing them once for all in a constant will improve the performances.

Also, if you plan to use the "contains" method I would advise to consider HashSets which answers that question faster than ArrayLists. But in this case it doesn't matter much given the size of the collection is 2 in all the cases.

Too much unnecessary code

Achei muito bom os pontos detalhados que voce trouxe na sua resolucao, e estou evoluindo para se ter este tipo completo de escrever codigo, mas achei o tipo de codigo tradicional, com muitas linhas.
Acho q nao é assim que deve ser feito, mas é o jeito mais certo de se abstrair.
Parabens pelo codigo =)