# Backward Chaining implementation as State Space Search problem

To me, Backward Chaining implementation can be viewed as a state space search problem.

In this problem, a state consists two components:

**(Path, Goals)**

- Path is the list of ordered rules that are used.
- Goals is the set of facts that currently need to be deduced.

An available action at a state is a applicable rule for that state.

The below example will clarify the idea.

Suppose that you have a set of rules:

Also suppose that we are facing a problem in which we have already known , and we want to know if can be deduced (if yes, then how?).

By this insight, now you know that you can implement Backward Chaining in various ways. Two path-finding algorithms that I suggest are A* and Depth-First Search. At first, I thought that Breadth-First Search might be good in finding shortest solution, however after an inspection, I find that a tuned Depth-First Search is still better than Breadth-First Search in such case.

By the way, if you exclude the Path component from a state (or at least do not let the Path component decides the unique of a state), you will have a more flexible state space search problem for backward chaining implementation.

MAPLE implementation using Depth-First Search:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
BackwardChaining := proc (GT, KL, Rules) local StateStack, NewHint, Hint, State, r; StateStack := [[[], KL]]; NewHint := {}; Hint := {}; while StateStack <> [] do State := StateStack[1]; StateStack := subsop(1 = NULL, StateStack); if `subset`(State[2], GT) then return State[1]; break elif `subset`(GT, State[2]) and `intersect`(KL, State[2]) = {} then NewHint := `minus`(State[2], GT); if Hint = {} or nops(NewHint) < nops(Hint) then Hint := NewHint end if end if; for r in `minus`(Rules, {op(State[1])}) do if `intersect`(r[2], State[2]) <> {} then StateStack := [[[r, op(State[1])], `union`(`minus`(State[2], r[2]), r[1])], op(StateStack)] end if end do end do; return Hint end proc |

1 |
Rules := {[{A}, {E}], [{B}, {D}], [{H}, {A}], [{E, G}, {C}], [{E, K}, {B}], [{D, E, K}, {C}], [{F, G, K}, {A}]} |

1 |
BackwardChaining({H, K}, {C, D}, Rules) |