Prehistoric man dotted the island with his mysterious cone-shaped nuraghi houses and watchtowers before it was colonized by Cretans , Phoenicians , Carthaginians , and Romans .
Prehistoric men built houses out of leaves .