Backjumping

<p>In <a href="/facts/Constraint_programming/rgkCK5bD">constraint programming</a> and <a href="/facts/Boolean_satisfiability_problem/wBVRjWoy">SAT solving</a>, backjumping (also known as non-chronological backtracking or intelligent backtracking) is an enhancement for <a href="/facts/Backtracking/Jm9vDUk8">backtracking</a> <a href="/facts/Algorithm/fnl5NmRt">algorithms</a> which reduces the <a href="/facts/Candidate_solution/cJUKNCmM">search space</a>. While backtracking always goes up one level in the <a href="/facts/Search_tree/zJIIMEH8">search tree</a> when all values for a variable have been tested, backjumping may go up more levels. In this article, a fixed order of evaluation of variables 
  
    
      
        
          x
          
            1
          
        
        ,
        …
        ,
        
          x
          
            n
          
        
      
    
    {\displaystyle x_{1},\ldots ,x_{n}}
  
 is used, but the same considerations apply to a dynamic order of evaluation. 
</p>

Backjumping open-in-new

Backjumping