Brute-force compute hasn't been an option for most of the history of science.

Very true. Humans have historically tried to systematically reduce the search space and only dedicate their "compute" to things that seem highly likely to yield results.