Regice was pretty awesome and so was registeel but I found regirock to be of not much help. I can actually remember how to solve quite a bit of it. Just off the top of my head, I think you had to approach this underwater rock and go to the surface to enter this cavern. Then, you use the move dig to make it past the initial chamber. After that, you had to do something with wailord an another pokémon (It was this ancient fish pokémon that I can't remember the name of) to open the individual chambers. I can't remember but I would imagine regirock would be impossible to catch because of all these weaknesses you would have to be careful of.