The brain can still use other means of working in addition to brute forcing solutions. For example, how would you go about solving the chess puzzle of eight queens that doesn't involve going through the potential positions and then filtering out the options that don't match the criteria for the solution?

Prolog can also evaluate mathematical expressions directly as well.

There's a whole lot of undecidable (or effectively undecidable) edge cases that can be adequately covered. As a matter of fact, Decidability Logic is compatible with Prolog.