Algorithm to satisfy given constraints - assigning values from a 2D array

Question

So me and my friend came up with a rather interesting (maybe?) algorithm question but ironically, we are having a hard time solving it. The question goes like this:

There is a sale of precious stones going on in a city of the Rich. Each stone on sale has one or more variants of it. For example, a diamond can be round, Oval, Cushion, etc. Each variant must be counted as a separate stone.

The stones are placed like this (example):

Diamond    Ruby     Emerald    Sapphire

round               red        colorless
oval                green      
cushion

This kind of placement prevents forming a perfect 2D array, since the number of types of each stone may vary.

Now rich customers come to buy the stones, and each customer has a set of stones that they like. A customer will be satisfied if they are able to purchase at least one of the stones that they like.

Given the number of customers, number of stones and associated variants, find out whether it is possible to satisfy all customers.

Bonus: If possible, find out the stones purchased by each customer.

Note: Customer preferences cannot be empty, i.e., each customer likes at least one stone.

What I have tried

(For finding out if it is possible to satisfy all customers)

Backtracking:

We have a list of preferences for each customer. So, just assign the first possible stone to the customer (from his/her list) and move on to the next customer. Keep doing it for all customers.

If, for a customer, it is not possible to assign a stone, go to the previous customer and change the assigned stone.

Repeat till at least one stone is assigned for each customer.

If you reach back to the first customer, and assigning no stone can lead to the solution, print "Impossible".

I have following concerns about this algorithm (assuming it is correct):

• It is hard to implement. I encountered too many temporary variables while trying to implement it. (I left it midway).
• It kind of feels like brute force, because I am actually trying every possible combination.

Is this algorithm correct? Can it be made better? Is there an alternative which is easy to implement?

Answer 1

I'd say it's a 1D array, given that a stone and its variant make a single item. Is it a wrong assumption?

Your algorithm should be correct, however it is truly a brute-force solution.

My simple suggestion: sort these items by the amount of people, who have them in their "favourites". Assign the items to people in this order, expanding a tree bounded by the amount of items.

E.g. 2 people like stone A, 3 people like stone B, first assign the stone A, so that you get rid of the less perspective as soon as possible.

This is probably not an optimal solution, however, some dynamic programming might be used, given that the state space is discrete.

Answer 2

Backtracking is a good approach. If your implementation gets to complicated you should read some example implementations of backtracking.

Remark: Backtracking is not 'trying every possible combination' because you do not try any combination, where already after a few assignments there could no longer be a valid over all assignment.
See Early stopping variants for a detailed description. (The Sodoku solving animation shows quite nice that you are far from trying each combination)