Distribute items evenly into buckets

Question

I’m trying to figure out an algorithm to distribute a set of 20 to 5000 items into a variable number of boxes (2 to 50). Items are identified by a number of properties, and we need to distribute them into the boxes as evenly as possible by their properties (evenly, not randomly).

Each item has (in order of priority):

1. Color: red, blue, green, yellow
2. Shape: round, square, or triangle
3. Size: small, medium, large
4. New or Used

The goal is for each box to end up with the same total number of items, the same number of each color, same number of each shape, etc. The property values of the incoming items are effectively random (or at least unpredictable). There can also be a variable number of properties, so maybe weight, material, or other criteria may be added later on. If the number of items is not evenly divisible by the number of boxes, then some boxes will have 1 more item than the others (whole units only).

We want the contents of the boxes to end up as close to identical as possible – no box should be different or better than any other box (aside from issues where whole units cannot be divided).

If it were just 1 property, that is easy enough – just loop through each color and split them between the boxes – similar to dealing cards. But then add the subsequent criteria, and then… well then short of brute force, I’m stuck. So I’m hoping somebody here has some advice on how to accomplish this in a reasonably efficient way.

Scoring the quality of a solution is based on the priority of each property. So in the example, even color distribution is most important, then shape, etc. The score for a particular property could be a simple sum of the max difference of the counts of each value between boxes. So say there are 2 boxes. If each has 5 of each color, the score for the color property is 0. If one box had 3 blue, and the other had 7 blue, the score would be 4. Lowest score wins.

For the total score of a solution, maybe an appended string of all the property scores would work. With the 4 properties of the example, a perfect total score would be 00-00-00-00. And 00-99-99-99 beats 01-00-00-00.