From: dnk@OMIT.csse.unimelb.edu.au   
      
   In <47f89a14$1@news.unimelb.edu.au> Al  writes:   
      
   > Hi,   
      
   > One way to solve a system of linear equations, which is an instance of   
   > CSP, is to use backtracking as illustrated by Stuart Russel and Peter   
   > Norvig in the book Artificial Intelligence, A Modern Approach.   
      
   > However, another variation of backtracking algorithms that is based on   
   > states and operators can also be used to solve this problem:   
      
   > backtrackSearch(stateList)   
   > {   
   >  state = first(stateList);   
   >  if state is goal, return stateList;   
   >  if state is deadend, return FAIL;   
   >  if state is a member of stateList, return FAIL;   
      
   >  operators = applicable operators for state;   
   >  loop:   
   >   if operators is empty, return FAIL;   
   >   op = first of operators;   
   >   operators = rest of operators;   
   >   newState = op(state);   
   >   newStateList = {newState} union stateList;   
   >   path = backtrackSearch(newStateList);   
   >   if path = FAIL then go to loop;   
   >   return {op, path}   
   > }   
      
   > Now suppose that we want to solve the following simple problem using   
   > this algorithm:   
      
   > x1 + 10 + x2 + x3 = 20;   
   > x1 + 12 + x4 = 20;   
   > x4 + x5 + 5 + x6 = 20;   
   > x3 + 11 + x6 = 20;   
      
   Here there are 4 independent equations in 6 variables, so there are   
   6-4 = 2 independent variables.  Reformulating in terms of x1 and x2 :   
      
   x3 = 10 - x1 - x2   
   x4 = 8 - x1   
   x6 = 9 - x3 = 9 - (10 - x1 - x2) = -1 + x1 + x2   
   x5 = 15 - x4 - x6 = 15 - (8 - x1) - (-1 + x1 + x2) = 8 - x2   
      
   You don't actually need to reformulate, just illustrating the point.   
      
   > And suppose that we are only allowed to fill in x1...x6 with 1, 2, 3,   
   > 4, 5, and 6.   
      
   > The question now is what operators to choose for solving this problem?   
   > One possible set of operators is (x1 <- 1), (x1 <- 2), ... (x1 <-   
   > 6), ... (x6 <- 1), ... (x6 <- 6) that in turn set x1 to 1, x1 to   
   > 2, ... and x6 to 1, and x6 to 6. A total of 36 operators.   
      
   > I am not very much interested in this set of operators. What   
   > alternative set of operators can you think of for solving this   
   > problem?   
      
   You can choose operators that take you to a solution in one step,   
   just try all assignments to x1 and x2 (or any 2 variables you like)   
      
   (x1 <- 1, x2 <- 1), (x1 <- 1, x2 <- 2), ... (x1 <- 1, x2 <- 6),   
   (x1 <- 2, x2 <- 1), (x1 <- 2, x2 <- 2), ... (x1 <- 2, x2 <- 6),   
   ...   
   (x1 <- 6, x2 <- 1), (x1 <- 6, x2 <- 2), ... (x1 <- 6, x2 <- 6),   
      
   When you try one you have to check that constraints on x1 ... x6   
   are satisfied.  So x1 <- 1 and x2 <- 1 is out as x3 = 10 - 2 >6.   
   In fact most of these operators are FAILs for xi in {1,2,3,4,5,6}   
   as x4 = 8 - x1 and x5 = 8 - x2 implies that x1 > 1 and x2 > 1 and   
   x4 > 1 and x5 > 1.  The 8 solutions are:   
      
   x1 <- 2, x2 <- 2, x3 <- 6, x4 <- 6, x5 <- 6, x6 <- 3   
   x1 <- 2, x2 <- 3, x3 <- 5, x4 <- 6, x5 <- 5, x6 <- 4   
   x1 <- 2, x2 <- 4, x3 <- 4, x4 <- 6, x5 <- 4, x6 <- 5   
   x1 <- 2, x2 <- 5, x3 <- 3, x4 <- 6, x5 <- 3, x6 <- 6   
   x1 <- 3, x2 <- 2, x3 <- 5, x4 <- 5, x5 <- 6, x6 <- 4   
   x1 <- 3, x2 <- 3, x3 <- 4, x4 <- 5, x5 <- 5, x6 <- 5   
   x1 <- 3, x2 <- 4, x3 <- 3, x4 <- 5, x5 <- 4, x6 <- 6   
   x1 <- 4, x2 <- 2, x3 <- 4, x4 <- 4, x5 <- 6, x6 <- 5   
   x1 <- 4, x2 <- 3, x3 <- 3, x4 <- 4, x5 <- 5, x6 <- 6   
   x1 <- 5, x2 <- 2, x3 <- 3, x4 <- 3, x5 <- 6, x6 <- 6   
      
   But these operators don't lead to much interesting backtracking.   
   I actually prefer your one_assignment_at_a_time operators!   
      
   David   
      
   [ comp.ai is moderated ... your article may take a while to appear. ]   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)