Depends on the version of the game you play. Daughters of the Emperor were added in 0.30-0.35 version, Katalina can be found on the global map, Naoki in the throne room.
