In che modo la coerenza dell'arco non è fatta dopo una condizione di guasto ricorsiva?
Domanda
Prendendo questo come esempio:
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
}
Dato l'algoritmo di backtracking con i CSP, vorrei aggiungere coerenza per renderlo più intelligente.
"Quando vogliamo assegnare la cifra" D "alla cella S1, usiamo Assegna (celle, S, D). ... Ma voglio anche eliminare questa possibilità dai suoi colleghi (come lo fa il controllo in avanti, dimmi qualcosa di nuovo !). Se l'eliminazione provoca uno (o alcuni) dei coetanei che scendono a una sola possibilità, che chiamiamo D2, vogliamo assegnare D2 ad esso e, facendo ciò, eliminiamo D2 da tutti i coetanei dei suoi pari e Ciò potrebbe fare un'altra reazione a catena. Questa reazione a catena è semplicemente chiamata propagazione del vincolo: posizionare un vincolo su una cellula può causare ulteriori vincoli su altre cellule. "
- Il processo di propagazione dell'arco può finire portando a una soluzione da sola o addirittura a una soluzione falsa? Cosa viene fatto in quei casi?
- Nel probabile evento la prossima chiamata ricorsiva alla variabile successiva restituisce false (nessun valori elaborato per quella variabile), Come faccio a annullare tutte le modifiche che la coerenza dell'arco ha fatto?
Nessuna soluzione corretta