Per far evolvere i pokémon devi fare in modo che il loro livello di amicizia sia elevato. Contribuiscono in tal senso: camminare molto tenendoli in squadra, farli combattere spesso senza mai perdere (altrimenti si ha un forte calo), tagliare loro i capelli e farli spazzolare dalla sorella dell'avversario, nella città di partenza. Raggiunto un alto livello di amicizia, falli salire di livello così avverrà l'evoluzione. In più per Umbreon devi fare in modo che Eevee salga di livello di notte.
Per la storia del puzzle non ricordo, ma ora cerco qualcosa.
EDIT: Per risolvere il puzzle ti serve una pietra idrica. Portala con te o, ancora meglio, assegnala al primo pokémon in squadra. Ora dovresti essere in grado di proseguire.