I mean when you beat the league or whatever (I don't have the games) and you can rematch the gym leaders. Will the gym trainers have higher level Pokemon, and if so, do you have to redo puzzles like Gardenia?
In order to fight the gym leaders and their stronger teams, you will need to beat them all at least once. After you take down all the gym leaders you will need to challenge the elite four. With the elite four taken down, Roark will tell you that the gym leaders have a new challenge for you. Now you can fight any of the gym leaders again by returning to their gym and talking to them. Be carful though as the new challenge the gym leaders have in store is no understatement.
Source
You don't have to redo the puzzles.
