Changing Permalinks

How can I change the permalinks of my website? My website is www.rotas-alegres.pt and when i set the permanlink setting to generic (showing www.rotas-alegres.pt/?i=123) the website works but when I change the permalinks to postname or to any other option it only opens the front page the other pages won’t open with the followuing error:

The resquested URL was not found on this surver.

Problemalready solved.