# How is ARC consistency un-done after a recursive failure condition?

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.

"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 by itself 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 I undo all the changes the arc consistency did?
• Are you asking for an algorithm or for code? If you're asking for an algorithm, I suggest removing the lengthy code sample and replacing it with the bare-minimum pseudocode necessary to understand the idea. Also, tell us what you have considered. Have you considered making a copy/snapshot of the relevant parts of the state, so you can restore the old state if you want to undo your guess? – D.W. Feb 28 '14 at 2:42