Taking this as an example:bool SolveSudoku(int grid[N][N]){    int row, col;    // If there is no unassigned location, we are done    if (!FindUnassignedLocation(grid, row, col))       return true; // success!    // consider digits 1 to 9    for (int num = 1; num <= 9; num++)    {        // if looks promising        if (isSafe(grid, row, col, num))        {            // make tentative assignment            grid[row][col] = num;            //RUN ARC CONSISTENCY HERE ......?            // return, if success, yay!            if (SolveSudoku(grid))                return true;            // failure, unmake & try again            grid[row][col] = UNASSIGNED;            ////REMOVE ARC CONSISTENCY HERE ......?        }    }    return false; // this triggers backtracking}Given the backtracking algorithm with CSP's, I would like to add ARC consistency to make it smarter.For example:When we want to assign the digit 'd' to cell s1, we use assign(cells,  s, d).  ...but I also want to eliminate this possibility from its  peers  (like Forward Checking does, tell me something new!). If the  elimination causes one (or some) of the peers going down to only one   possibility, which we call d2, we want to assign d2 to it, and by  doing that,  eliminate d2 from all of its peer's peers, and that could  make another chain  reaction. This chain reaction is simply called  constraint propagation:  placing a constraint on one cell can cause  further constraints to be placed on  other cells.Can the process of arc propagation end up leading to a solution byitself or even a false solution? What is done in those cases?In the likely event the next recursive call on the next variable returns false (no values worked out for that variable), how do Iundo all the changes the arc consistency did?
How is ARC consistency un-done after a recursive failure condition?
algorithms;artificial intelligence;recursion;constraint programming;backtracking
The obvious answer is: take a snapshot (checkpoint) of your state before applying the arc consistency inferences; recursively explore that option; and then if it is a failure, restore the state back to your snapshot.Whether this is efficient depends upon the size of the state and the amount of work done during the recursive call.  For this particular application (Sudoko), I suspect you don't have much state, so I expect this will be a perfectly reasonable solution.In more complex situations, you can use more sophisticated data structures that support undo/rollback.  For instance, persistent data structures are one way to make rolling back to a prior version faster, in some cases.  Partial persistence is enough; you don't need full persistence or confluent persistence.  However, for simple cases like this one, the overhead of persistence might outweigh any gain from avoiding copying the state.If you want us to recommend a more efficient solution than the naive copying approach, you'll need to specify in greater detail what sort of data structures you need for this application (e.g., for storing the set of constraints).