Cluster algorithm which minimizes a distance while fulfilling a constraint I have data of 90 persons.

Data of a person:
- x coordinate
- y coordinate
- score (1 to 6)  

I want to form groups of 9 people each so that:
- the distance between people in one group is as small as possible
- people with the same coordinates are in different groups
- people within a group should have different scores  

I am not expecting a full-fledged algorithm but rather hints in the right direction. So far I am using a simple k-means algorithm which forms groups so that the distance between people gets minimized however the two other constraints are not considered, unfortunately.
I found this article on "Clustering with Constraints" to be a helpful resource to what you're talking about:

Credit:
Clustering with Constraints
Incorporating Prior Knowledge
into Clustering
Adapted from a Tutorial of Sugato Basu and Ian Davidson (SDM 2005)