what happens when backtracking?

  • nrike6

    nrike6 - 2013-04-04

    is backtracking always removing levels from the store? what is the difference between backtracks and wrong decisions? is it possible that the solver backtracks and the store-level is increased?

  • kris

    kris - 2013-04-04

    First, the store level is NEVER increased when solver backtracks. It is in fact decreased. The store level is decreased and all data generated by the annulated decision are removed.

    The difference between number of wrong decisions and a number of backtracks is very subtle. The wrong decisions are are increased when the solver makes a new decision on setting a value to a variable and this decision fails. Backtracks are counted when the solver returns from the next node in the search tree with fail result. This fail might depend on a wrong decision or a new decision that basically says that variable cannot be equal a given value (the one that failed recently).


  • nrike6

    nrike6 - 2013-04-10

    hi kris. thanx for your explanations.

    i am currently creating a custom selector which, at each step when an unbound variable is selected, restricts search to only a part of the variables domain (depending on the values of the previous variables). I try to do this by adding new constraints. E.g: Var_X::{1..4} -> Var_X = 1 OR Var_X = 2, thus forbidding the values 3 and 4.

    In order to remove values form the domain i call the consistency() method. Now, here is the problem:
    When there is no value possible due to the new constraint and the domain should be empty, a FailException occurs.
    In this case i would like to backtrack.

    Is there an easy way of coping with this?


  • kris

    kris - 2013-04-10


    I have to say that I do not really understand what you are doing and how you interface with existing search but the search does backtrack when a domain becomes empty. This is achieved by checking the return value from consistency method. If consistency returns false the backtrack occurs. Basically the search removes all variables created on the current level and decreases the level for search.

    Another important thing in search. Each search decision has always negated decision that is taken if the first decision is wrong. For example, x = constant and x != constant in a standard search. In your case you can try, so called split search, implemented by SplitSelect and and IndomainMiddle. In this case the decision will be x <= middle_value and x > middle_value.

    Hope this can help.

  • nrike6

    nrike6 - 2013-04-11

    Thanx Kris.

    I have another question concerning the counting of backtracks in DepthFirstSearch (lines 711-786).

    When assigning the current variable resulted in non-consistency DepthFirstSearch tries the complement/negation. If this also returns false (i.e. non-consistency) this should be counted as a backtrack as there are no possibilities left.

    Here, the code differentiates between three cases:
    1. (line 726) The choice point was based on a constraint: If the negated constraint also leads to inconsistency -> backtrack++
    2. (line 746) The choice point was based on a variable and a domain value && variable not singleton: Try complemented domain. If this leads to inconsistency -> backtrack++
    3. (line 772) Variable is singleton: The single value has already been tried and lead to inconsistency before. Here, no backtrack is counted!

    Why is there no backtrack counted when the variable was singleton and this single value lead to inconsistency?

    Many thanx,

  • Radoslaw Szymanek


    I apologize for late answer. I missed your last question.

    The measurements in JaCoP are done as proposed in the following paper -

    Bessiere, C., Zanuttini, B., Fernandez, C.: Measuring search trees. In: Proceedings
    of ECAI’04 workshop on Modelling and Solving Problems with Constraints. (2004), 31–40

    Thus, if there was a singleton then there was no decision to be taken, so reverting this decision is not a backtrack. Hope that helps.

    best regards,


Log in to post a comment.

Get latest updates about Open Source Projects, Conferences and News.

Sign up for the SourceForge newsletter:

No, thanks