title: How do I perform branching combinatorial search without copying state at each recursive call?
body: <p>In most branching combinatorial search algorithms I've seen, each recursive call in the depth-first search is made with a copy of the current solution state (to ensure that the branching can always recover to the given solution state if a branch turns out to be fruitless).</p>
  
  <p>For example, take Peter Norvig's Sudoku solver search function:</p>
  
  <pre><code>def search(values):
      "Using depth-first search and propagation, try all possible values."
      if values is False:
          return False ## Failed earlier
      if all(len(values[s]) == 1 for s in squares): 
          return values ## Solved!
      ## Chose the unfilled square s with the fewest possibilities
      n, s = min((len(values[s]), s) for s in squares if len(values[s]) &gt; 1)
      return some(search(assign(values.copy(), s, d)) 
          for d in values[s])
  </code></pre>
  
  <p>Question: is there a standard way to avoid having to perform a copy of the entire solution/constraint space each time a recursive call is made? Concretely, Is it possible to implement Norvig's Sudoku solver without copying <code>values</code> at each recursive call?</p>
  
  <p><strong>What have I tried?</strong></p>
  
  <p>1) Implement search iteratively on a global solution object. Carefully manage both constructive additions and destructive removals of propagated constraints to the global solution object so that prior branch decisions are recoverable.</p>
  
  <p>2) Use a persistent tree structure to represent my solution state. I haven't been able to implement this yet, and I'm not even sure it makes sense.</p>