Yes, can be done in Solr. Most likely adding the herd attributes to the sheep would be the better way, so you could do this in a single query. You have some overhead anyway to get the data into Solr, so you can as well put everything in a single index. I have used Solr faceting for far more complex problems.
Sphinx too has facets, though I didn't use it, so can't say exactly if they would work, but from the documents it seems there are no big differences to Solr.
Another option would be ElasticSearch. As Solr it's built on the Apache Lucene engine. When I decided for Solr Elastic wasn't fully featured, but by now they have caught up and I read very good things about it in blogs. Actually considering to switch the project.
There are some NoSQL solutions that work similar to facets. Though they may lack some other features of those full text search engines.