title: Backtracking recursively with multiple solutions
body: <pre><code>function BACKTRACKING-SEARCH(csp) returns a solution, or failure 
         return RECURSIVE-  BACKTRACKING({ }, csp)
  function RECURSIVE-BACKTRACKING(assignment,csp) returns a solution, or failure 
         if assignment is complete then 
                   return assignment
         var ←SELECT-UNASSIGNED-VARIABLE(VARIABLES[csp],assignment,csp)
         for each value in ORDER-DOMAIN-VALUES(var,assignment,csp) do
                   if value is consistent with assignment according to CONSTRAINTS[csp] then
                             add {var = value} to assignment
                             result ← RECURSIVE-BACKTRACKING(assignment, csp)
                             if result ̸= failure then 
                                              return result
                             remove {var = value} from assignment 
         return failure
  </code></pre>
  
  <p>This is a backtracking recursion algorythm pseudocode from AIMA. However, I don't understand if it returns ALL possible solutions or just first one found. In case it is the last option, could you please help me modify it to return a list of possible solutions instead (or at least updating some global list).</p>
  
  <p>EDIT: I implemented this algorithm in Java. However, there is one problem: </p>
  
  <p>if I don't return assignment, but save it in <strong>result</strong> instead, the recursion stop condition fails (i.e. it doesn't exist anymore). How can I implement another stop-condition? Maybe I should return <strong>true</strong> in the end?</p>
  
  <p>Here is my code :</p>
  
  <pre><code>/**
   * The actual backtracking. Unfortunately, I don't have time to implement LCV or MCV,
   * therefore it will be just ordinary variable-by-variable search.
   * @param line
   * @param onePossibleSituation
   * @param result
   */
  public static boolean recursiveBacktrack(Line line, ArrayList&lt;Integer&gt; onePossibleSituation, ArrayList&lt;ArrayList&lt;Integer&gt;&gt; result){
  
  
  if (onePossibleSituation.size() == line.getNumOfVars()){
      // instead of return(assignment)
      ArrayList&lt;Integer&gt; situationCopy = new ArrayList&lt;Integer&gt;();
      situationCopy.addAll(onePossibleSituation);
      result.add(situationCopy);
      onePossibleSituation.clear();
  }
  
  Block variableToAssign = null;
  // iterate through all variables and choose one unassigned
  for(int i = 0; i &lt; line.getNumOfVars(); i++){
       if(!line.getCspMiniTaskVariables().get(i).isAssigned()){
           variableToAssign = line.getCspMiniTaskVariables().get(i);
           break;
       }
  }
  
  // for each domain value for given block   
  for (int i = line.getCspMiniTaskDomains().get(variableToAssign.getID())[0]; 
          i &lt;= line.getCspMiniTaskDomains().get(variableToAssign.getID())[0]; i++){
  
      if(!areThereConflicts(line, onePossibleSituation)){
          //complete the assignment
          variableToAssign.setStartPositionTemporary(i);
          variableToAssign.setAssigned(true);
          onePossibleSituation.add(i);
          //do backtracking
          boolean isPossibleToPlaceIt = recursiveBacktrack(line,onePossibleSituation,result);
          if(!isPossibleToPlaceIt){
              return(false);
          }
      }
  
      // unassign
      variableToAssign.setStartPositionTemporary(-1);
      variableToAssign.setAssigned(false);
      onePossibleSituation.remove(i);
  
  }
  
  // end of backtracking
  return(false);
  
  }
  </code></pre>