Backtracking

Question

Here , Number of backtracks are 3 or 4 ? I am getting 3 but given answer is 4. Please explain.

Answer 1

First S --> rAd is chosen

then A-->y is chosen which is false So backtrack to A and verify other options (1st backtrack).

then A-->z is chosen which is false So backtrack to A and verify other options (2nd backtrack).

Since all options of A are verified  now backtrack to S and choose S-->rB. (3rd backtrack )

then B-->zzd is chosen which is false So backtrack to B and verify other options (4th backtrack).

then B--ddz is chosen which we want.

So total 4 backtracks I think.

Comments

In 3rd Backtrack , I think when we replace 'B' with 'zzd' then we get the dead end . and after this when we replace 'B' with 'ddz' then we successfully get the string without any dead end. So I think only 3 backtracks are needed. Please  correct me..

---

after 3rd backtrack we choose 'zzd', so we have to backtrack again to choose 'ddz'

---

yes , u r right !