C++: backward chaining from a goal
Backward chaining is goal-directed reasoning. To prove a goal, the system first checks whether it is a known fact. If not, it looks for a rule whose conclusion is that goal and tries to prove every condition of the rule, recursively. This is how Prolog answers queries.
C++
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
std::set<std::string> facts = {"rain", "cold"};
std::map<std::string, std::vector<std::string>> rules = {
{"wet", {"rain"}},
{"ice", {"wet", "cold"}},
{"slippery", {"ice"}},
};
bool prove(const std::string& goal, int depth) {
std::cout << std::string(depth * 2, ' ') << "goal " << goal;
if (facts.count(goal)) {
std::cout << " -> fact\n";
return true;
}
auto rule = rules.find(goal);
if (rule == rules.end()) {
std::cout << " -> no rule\n";
return false;
}
std::cout << "\n";
for (const std::string& condition : rule->second) {
if (!prove(condition, depth + 1)) {
return false;
}
}
return true;
}
int main() {
std::cout << (prove("slippery", 0) ? "proved" : "not proved") << "\n";
std::cout << (prove("sunny", 0) ? "proved" : "not proved") << "\n";
}