1
$\begingroup$

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 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?
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – D.W. Feb 28 '14 at 2:42
2
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.