Human adults think of the natural world as orchestrated by rules, yet many of them are neither equally rigid nor clearly evident. Some are beset by exceptions, and others are not intuitive. The problem of rule learning is especially salient in development, as children are continuously learning how the world works. What cognitive mechanisms underpin this rule learning? We propose a computational model for formulating and testing hypotheses in naturalistic contexts, that combines Bayesian inference under uncertainty over self-generated and social evidence with formal rules and optimistic information-seeking heuristics. We validate our model experimentally, showing that it explains 7- to 10-year-olds' behavior in a rule-based, physical task, including the distribution and the types of evidence children sampled. The proposed model outperforms both a purely rule-based Bayesian hypothesis search and a resource-rational random sampling approach. Our results suggest that children implement an internal mechanism for generating and testing a limited number of hypotheses, including formal programmatic rules and heuristics generated from salient problem features to seek more evidence when formal rule generation fails.