My Lab only had one accident in the house as a pup and it was my fault. I took her out ALL the time. At least every few hours and after eating, drinking, playing and through the night I would wake up and make her go out.

Another option may be to let the puppy be around another dog and watch that dog do it's business outside. I think dogs learn best from other dogs anyway.