Instructions
Capturing Regice
Fly to Dewford Town, walking south to the nearest coast to Surf. Open your menu with the "X" button and select the "Items" pocket of your bag before surfing, highlighting the item "Repel." The item Repel wards off low level wild Pokemon, eliminating unnecessary battles while traveling. Press the "B" button to return to the main menu and select "Pokemon." Select the HM, or Hidden Move, Surf from your desired Pokemon's assigned submenu.
Surf southwest into Route 105, avoiding trainers along the way. Disembark your Pokemon at the nearest small island, traveling south and then east to use Surf again. Surf north to reach a small island housing a cave known as "Island Cave."
Enter the cave and walk north to reach a wall inscribed with Braille characters; the message explains you must stop and wait for time to pass "twice." Wait around two minutes for a door to appear. Enter the door to approach Regice; save your game before walking up to the Pokemon and pressing the "A" button to initiate battle. Weaken Regice using Fire, Steel, Rock or Fighting Pokemon for an extra advantage against its weaknesses.
Capturing Regirock
Exit the eastern part of Lavaridge Town, continuing into Route 112 over a few ledges. Walk or run east into Route 111, heading northeast into the sandstorm ravaged desert. The Key Item "Go-Goggles" allows all trainers to enter the sandstorm; your rival gives you the "Go-Goggles" after you clear the fourth gym. Head south, avoiding any wild Pokemon or trainers, until you reach a small cave. Enter the cave known as the "Desert Ruins."
Walk north to reach another wall inscribed with Braille characters; the characters explain to walk east twice and south twice before using "Strength." Walk two steps right and then two steps down; open your menu with the "X" button and select "Pokemon," choosing HM Strength from your selected Pokemon's submenu. A door opens at the Braille inscribed wall if you've followed its directions.
Go through the door to approach Regirock; save your game before approaching the Pokemon, pressing the "A" button to start the battle. Use Water, Grass, Steel, Ground or Fighting Pokemon to have a type advantage against Regirock.
Capturing Registeel
Walk west from Lilycove City to Route 121, heading south once you reach the fences. Open your menu with the "A" button, selecting your Items pocket to activate the item Repel to ward off wild Pokemon. Exit the menu and continue west, past the fences and trainers, to reach a set of stairs.
Ascend the stairs and keep going west into Route 120. Head west and then north to reach a set of stairs; go up the stairs into the tall, wild grass. Walk through the wild grass to reach another set of stairs. Head north into a rainy area, where a small cave sits up ahead. Enter the cave known as "Ancient Tomb."
Walk north to reach a wall inscribed with Braille characters, similar to the other walls in the last two caves. The text explains you must "aim for the sky in the middle." Walk to the room's center and open your menu, selecting the Pokemon option; choose the Hidden Move Fly on your selected Pokemon's submenu to make a door appear.
Walk through the door to approach Registeel; save your game before approaching the Pokemon and pressing the "A" button to begin battle. Fire, Ground and Fighting Pokemon effectively weaken Registeel due to their type advantage against it.