Backward-chain (depth-first) to prove "playground_empty" from the exam Q6 rules, printing each rule in its order of trial — including the rule-1 dead end — then the rules that made up the proof.

Answer

RULES = [ (1, ["raining", "cold"], "playground_empty"), (2, ["playing_videogame"], "kids_not_outside"), (3, ["kids_not_outside"], "kids_videogame_or_school"), (4, ["not_school_day"], "kids_outside_or_videogame"), (5, ["kids_not_outside"], "playground_empty"), ] FACTS = {"not_school_day", "playing_videogame"} def prove(goal, depth, trace, used): if goal in FACTS: return True for num, premises, concl in RULES: # rules tried in number order (DFS) if concl == goal: trace.append((depth, num, premises, concl)) if all(prove(p, depth + 1, trace, used) for p in premises): used.append(num) return True return False trace, used = [], [] ok = prove("playground_empty", 0, trace, used) print("goal: playground_empty") for depth, num, premises, concl in trace: indent = " " * (depth + 1) print(f"{indent}try rule {num}: {' AND '.join(premises)} -> {concl}") print(f"PROVED via rules {used}" if ok else "FAILED")