18C5T13 Lecture Notes - Lecture 3: Backtracking, Tuple, Solution Set
Document Summary
Implicit: explicit const raint s are rules t hat rest rict each xi t o t ake on values only from a given set. Implicit const raint s describe t he w ay in w hich t he xi must relat e t o each ot her. In 8-queens problem t he solut ion space cont ains 88 t uples 8-tuples. No t w o xi"s can be t he same (all queens are in different columns) No t w o queens can be on t he same diagonal: solut ion space is facilit at ed by tree organizat ion called st at e space tree. Give numbers t o nodes in t he above t r ee using dfs. Searching of t he st at e space t ree for t he solut ion (vect or) can be perfor m ed as begin w it h t he r oot node and generat e ot her nodes.