質問

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?

正しい解決策はありません

ライセンス: CC-BY-SA帰属
所属していません cs.stackexchange
scroll top