How do I solve a constraint satisfaction problem via backtracking

See more:

C++

programming

algorithm

I have n sets of two items:

["a", "b"]
["c", "d"]
["d", "a"]
["b", "c"]

And I want to find at least one item from this set (if it exists), that passes the following constraints:

The first constraints is a sort of exclusion check (= we are given a list of sets of items that cannot exist together), this set may look something like this:

["c", "d"] // items "c" and "d" cannot exist together
...

The second constraint specifies which items need which items to exist (= we are given list of sets of items that have to exist together), this set may look something like this:

["b", "c"] // item "b" needs item "c" and vice versa
...

To solve for these constraints we can use items from other sets from the original set (= the first set in this question).

The solution for the example sets is as follows (note that there may exist more that one solution, we just need a valid one):

Passed checks with items: 
a
b
c

Some of the caveats I've found out while working on this problem:
- The solution has to be recursive
- We need to consider that an item may be "locked" because of an exclusion created by other items, which may be worked around if we were to use a different combination of items.

Any ideas about how to get this working are very much appreciated.

What I have tried:

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

class Set {
public:
    std::string item1;
    std::string item2;

    Set(std::string i1, std::string i2) : item1(i1), item2(i2) {}
};

// Define a function to check if a given pair of items violates a constraint
bool ViolatesConstraints(std::string item1, std::string item2, const vector<pair<std::string, std::string>>& constraints) {
    for (const auto& constraint : constraints) {
        if ((constraint.first == item1 && constraint.second == item2) ||
            (constraint.first == item2 && constraint.second == item1)) {
            return true;
        }
    }
    return false;
}

// Define a function to recursively find all required items
void FindRequiredItems(std::string item, const vector<pair<std::string, std::string>>& inclusions, unordered_set<std::string>& requiredItems) {
    for (const auto& inclusion : inclusions) {
        if (inclusion.first == item) {
            requiredItems.insert(inclusion.second);
            FindRequiredItems(inclusion.second, inclusions, requiredItems);
        }
    }
}

int main() {
    // Define the list of sets and their items
    vector<Set> sets = { ... };

    // Define the list of constraint pairs
    vector<pair<std::string, std::string>> constraints = { ... };

    // Define the list of inclusion pairs
    vector<pair<std::string, std::string>> inclusions = { ... };

    // Initialize the best solution found so far
    bool passedChecks = false;
    unordered_set<std::string> usedItems;

    // Iterate over all sets to search for a solution
    for (const auto& set : sets) {
        // Check if the set's items violate any constraints
        if (ViolatesConstraints(set.item1, set.item2, constraints)) {
            continue;
        }

        // Check if the set's items satisfy all inclusions recursively
        unordered_set<std::string> requiredItems = { set.item1, set.item2 };
        for (const auto& requiredItem : requiredItems) {
            FindRequiredItems(requiredItem, inclusions, requiredItems);
        }
        if (requiredItems.size() == 5) {
            // Found a solution, update the best solution found so far
            passedChecks = true;
            usedItems.clear();
            usedItems.insert(set.item1);
            usedItems.insert(set.item2);
        }
        else {
            // Current solution doesn't satisfy all inclusions, continue searching
            continue;
        }

        // Search for a better solution
        for (const auto& nextSet : sets) {
            if (nextSet.item1 == set.item1 && nextSet.item2 == set.item2) {
                continue;  // skip current set
            }

            if (ViolatesConstraints(nextSet.item1, nextSet.item2, constraints)) {
                continue; // skip set whose items violate constraints
            }

            unordered_set<std::string> requiredItems = { nextSet.item1, nextSet.item2 };
            for (const auto& requiredItem : requiredItems) {
                FindRequiredItems(requiredItem, inclusions, requiredItems);
            }

            if (requiredItems.size() == 5) {
                // Found a better solution, update the best solution found so far
                passedChecks = true;
                    usedItems.clear();
                    usedItems.insert(nextSet.item1);
                usedItems.insert(nextSet.item2);
            }
        }
    }

    // Print the result
    if (passedChecks) {
        cout << "Passed checks with items:";
        for (const auto& item : usedItems) {
            cout << " " << item;
        }
        cout << endl;
    }
    else {
        cout << "Failed checks" << endl;
    }

    return 0;
}