Prove a goal by working back from it to the facts.
What to build
A program that proves a goal with backward chaining and prints the proof.
Requirements
- Rules use the format of the forward-chaining exercise. A goal is proved if it is a fact, or if some rule concludes it and all its premises can be proved. Rules are tried in the order given, premises from left to right, and a goal that is already being proved further up the current chain fails.
- Print the proof, each goal on its own line in the order it is established:
GOAL: factorGOAL: rule K(rules numbered from 1). Then printproved; or print onlynot proved.
Input
Line 1: r. Then r rules. Then a line of facts. Last line: the goal.
Output
The proof and proved, or not proved.
Constraints
r ≤ 100.
Example
Input:
2
A B -> C
C -> D
A B
D
Output:
A: fact
B: fact
C: rule 1
D: rule 2
proved
Why it works
Working backwards only touches the rules and facts the goal actually depends on, and the loop check stops circular rules from recursing forever.
Examples
2 A B -> C C -> D A B D
A: fact B: fact C: rule 1 D: rule 2 proved
1 A -> B B
not proved
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
To prove a goal: if it is a fact, it is proved; otherwise try each rule that concludes it, in order, proving its premises from left to right.
Hint 2
Return the list of proof lines from a successful attempt, and nothing from a failed one, so only the real proof is printed.
Solution
Show one correct solution (try it yourself first)
rules = []
for _ in range(int(input())):
left, right = input().split("->")
rules.append((left.split(), right.strip()))
facts = set(input().split())
goal = input().strip()
def prove(g, path):
if g in facts:
return [f"{g}: fact"]
if g in path:
return None
for number, (premises, conclusion) in enumerate(rules, start=1):
if conclusion == g:
lines = []
for p in premises:
sub = prove(p, path | {g})
if sub is None:
break
lines += sub
else:
return lines + [f"{g}: rule {number}"]
return None
proof = prove(goal, frozenset())
if proof is None:
print("not proved")
else:
print("\n".join(proof))
print("proved")