what puzzles?
if you're already at the underwater cave, just dig infront of the braille sign...
then go straight ahead and, having a relicanth and wailord in your party (one lead and tail; swap around if it doesn't work) and talk to the sign at the end of the room, and you'll hear 3 doors opening
... now go find the 3 tombs, one's in d dessert, one's at the end of the route that brings you to lillycove from fortress city (you know, that route that always rains) alternative directions = go straight left from lillycove, and finali the last cave is half from from rustboro and dewford... grats, you now have the regis, now chuck em in the PC and go catch absol...