AI: Backward chaining with a proof

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: fact or GOAL: rule K (rules numbered from 1). Then print proved; or print only not 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

Example 1 · Input
2
A B -> C
C -> D
A B
D
Expected output
A: fact
B: fact
C: rule 1
D: rule 2
proved
Example 2 · Input
1
A -> B

B
Expected output
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")

Lesson: Inference: chaining, resolution and unification →