Regex to find 3 out of 4 conditions

It's not much of a better solution, but you can reduce [^a-zA-Z0-9] to [\W_], since a word character is all letters, digits and the underscore character. I don't think you can avoid the alternation when trying to do this in a single regex. I think you have pretty much have the best solution.

One slight optimization is that \d*[a-z]\w_*|\d*[A-Z]\w_* ~> \d*[a-zA-Z]\w_*, so I could remove one of the alternation sets. If you only allowed 3 out of 4 this wouldn't work, but since \d*[A-Z][a-z]\w_* was implicitly allowed it works.

(?=.{8,})((?=.*\d)(?=.*[a-z])(?=.*[A-Z])|(?=.*\d)(?=.*[a-zA-Z])(?=.*[\W_])|(?=.*[a-z])(?=.*[A-Z])(?=.*[\W_])).*

Extended version:

(?=.{8,})(
  (?=.*\d)(?=.*[a-z])(?=.*[A-Z])|
  (?=.*\d)(?=.*[a-zA-Z])(?=.*[\W_])|
  (?=.*[a-z])(?=.*[A-Z])(?=.*[\W_])
).*

Because of the fourth condition specified by the OP, this regular expression will match even unprintable characters such as new lines. If this is unacceptable then modify the set that contains \W to allow for more specific set of special characters.

I'd like to improve the accepted solution with this one

^(?=.{8,})(
    (?=.*[^a-zA-Z\s])(?=.*[a-z])(?=.*[A-Z])|
    (?=.*[^a-zA-Z0-9\s])(?=.*\d)(?=.*[a-zA-Z])
).*$