Efficient sorting into categories with choices

So here's the problem.

I have 8 categories, and about a hundred items. Each item can fit into 1, 2, 3 or 4 of these categories (and we know which ones each item can fit into). The task is to have 'the most even distribution' of the items among the categories, i.e. it is best if all the categories have something in them before putting more than one into a category. Once an item has been placed in a category, it cannot be repeated in another.

Example 1, with eight items
Categories labelled, A to H. Items are represented by X's.

In the above case (with eight items), 1 is better than 2 or 3. Basically, to fill a row as quickly as possible is the task, given that some items will only fit into some categories, and that you can't put the same item into two categories in the end!

Example 2, with ten items
Categories labelled, A to H. Items are represented by X's.

Again, 1 is better than 2 or 3.

Example data:


The second stage after this is filling the next row up as quickly as possible, but I'm not too concerned about this at the moment (one step at a time, right!)

I'm having some difficulty thinking of an algorithm for this, and I don't know what to search for in my favourite search engine (which may or may not begin with a G), so help, please!

PS I'll be using PHP/MySQL, not that that really matters at this stage!

My first thought is to treat it as a hash table, where each row is a bucket. Just like a hash table, you want the buckets to be fairly even and can modify closed hashing to rehash as needed. If you weaken the constraints by allowing less than perfect distribution, you can use a hashtable using open-hashing. This would avoid the complexities of rehashing for a row and when the item appears again, trying to figure out if it was hashed somewhere else. If you can do post processing after all the data has been added, you could try to make minor improvements to the balancing.

Basically, I'd see how strict the requirements are and whether it must be done row-oriented (versus column-oriented) and be an online algorithm. If you're just making it overly complex by wanting perfect results, then a simply hashing algorithm is fast and simple. If the requirements are strict, then hashing may not be the best approach but can help you flush out ideas.