Sudoku als CSP (Bogenkonsistenz)

Question

Für eine Studienaufgabe habe ich Norvigs Algorithmus in C# neu erstellt, um Sudokus als Constraint Satisfaction Problem (CSP) kombiniert mit lokaler Suche zu lösen, wobei die Anzahl möglicher Werte für ein Quadrat heuristisch ist. Jetzt muss ich eine Erweiterung oder Variante davon erstellen, und ich bin irgendwie verwirrt, bis zu welchem ​​Grad der Algorithmus die Bogenkonsistenz gewährleistet. Was der aktuelle Algorithmus im Grunde dafür tut, ist:

Initialisieren Sie die möglichen Werte (Domänen) jedes Quadrats als [1, ..., n * n].

Jede Zuweisung eines Werts an ein Quadrat erfolgt durch Eliminieren aller möglichen Werte aus der Domäne und Aktualisieren jedes Peers (Quadrat in demselben Untergitter/Zeile/Spalte) durch Entfernen des zugewiesenen Werts aus ihren Domänen. (Gewährleistet dies nicht vollständig die Bogenkonsistenz, da dies die einzigen Einschränkungen zwischen den Peers sind, dass sie möglicherweise nicht den gleichen Wert haben?)

Wenn ein Wert aus der Domäne eines Quadrats eliminiert wird, wird auch geprüft, ob nur noch 1 Quadrat übrig ist Wert in seiner Einheit. Wenn ja, wird es diesem Quadrat zugewiesen (auch indem mögliche Werte eliminiert und auf genau diesen Wert reduziert werden).

Jetzt ist meine Frage: stellt dieser Algorithmus vollständige Bogenkonsistenz sicher? Und wenn nicht, wie könnte ich meinen CPS-Algorithmus dafür verbessern?

Wenn mir jemand dabei helfen könnte, wäre es sehr geschätzt!

Vielen Dank im Voraus.

Mit freundlichen Grüßen.

Answer 1

Ich bin überrascht, dass Sie lokale Suche hinzufügen, da das Sudoku in CP wirklich trivial gelöst wird (normalerweise ohne jede Verzweigung). Wie auch immer, kann Arc Konsistenz drei verschiedene Bedeutungen hat:

• Bogen Konsistenz über ein Constraint-Netzwerk aufbauen: etwa bedeutet, dass Sie bis zum Erreichen eines festen Punktes des Filteralgorithmus Ihrer Zwänge nennen. Dies wird standardmäßig von allen Solvern durchgeführt. Leute, die diesen Begriff verwenden, nehmen normalerweise an, dass jede Bedingung ihren eigenen Algorithmus für die Bogenkonsistenz hat (siehe nächster Punkt), was für binäre Bedingungen durchaus richtig ist, aber im allgemeinen Fall (und realen Problemen) falsch ist.

• Etablierung der Bogenkonsistenz für eine Abhängigkeit: Grob bedeutet, dass von jeder Variablen alle Werte entfernt werden, die zu keiner Lösung DIESER KONSTRAINT gehören (unabhängig vom Rest des Modells). Es hängt vom Filteralgorithmus ab, den Sie für die Einschränkung verwenden (Sie können viele mit unterschiedlichem Kompromiss zwischen Filterleistung und Laufzeit haben).

• Festlegen der Bogenkonsistenz für ein Problem: Stellen Sie sich vor, Sie modellieren Ihr gesamtes Problem mit einer benutzerdefinierten globalen Integritätsbedingung und wenden dann die vorherige Definition an.

Also etablieren Sie AC auf das gesamte Problem? Das heißt, gehören alle ungefilterten Variablen/Wertvorgaben zu einer Lösung? Von dem, was du beschreibst, ist die Antwort nein.

Haben Sie AC für jede Ihrer Bedingungen festgelegt? Nun, das hängt von deinem Modell ab. Wenn Sie nur binäre Einschränkungen verwenden, um Ihr Problem anzugeben, würde ich ja sagen. Wenn Sie die Filterung verbessern möchten, sollten Sie globale Einschränkungen wie AllDifferent verwenden. Der Arc-konsistente Filteralgorithmus dieser Einschränkung ist komplexer als das, was Sie beschreiben, ist aber auch leistungsfähiger!

Sie können einen Blick auf diese example werfen, die Choco Solver verwendet. Sie können auch verschiedene Konsistenzstufen verwenden (z. B. gebundene Konsistenz).