Algorithm to solve constraint satisfaction problems

Question

I have group of people. Each person can be described by few characteristics:

age, occupation, city, favorite_color

I would like to generate 60 random people and combine them into pairs. With a constrain that no person in a pair can share any characteristic, for example I can't have two people in a pair whose favorite_color is green.

I was thinking about using Backtracking algorithm to solve it.

What other algorithms I could use to solve this particular problem? I would like to research and implement some.