Einschränkungsprogrammierung in Java
Einführung
Einschränkungsprogrammierung (https://ja.wikipedia.org/wiki/%E5%88%B6%E7%B4%84%E3%83%97%E3%83%AD%E3%82% B0% E3% 83% A9% E3% 83% 9F% E3% 83% B3% E3% 82% B0) ist eines der Programmierparadigmen. Bei der Einschränkungsprogrammierung wird das Programm geschrieben, indem die Beziehungen zwischen Variablen in Form von Einschränkungen beschrieben werden. Heutzutage wird KI oft als Synonym für tiefes Lernen bezeichnet, aber in der Vergangenheit wurden diese Einschränkungsprogrammierung und mathematische Verarbeitung auch als KI bezeichnet. Implementieren Sie eine Constraint-Programmierbibliothek in Java und versuchen Sie, Probleme wie acht Königinnen, maskierte Berechnungen und Mathematik zu lösen.
Zielproblem
Zielen Sie auf die einfachsten Probleme ab. Insbesondere sind die Probleme wie folgt.
- Der Definitionsbereich von Variablen besteht nur aus ganzen Zahlen.
- Es wird angenommen, dass der Definitionsbereich der Variablen endlich ist und der Bereich im Problem definiert ist.
Einfaches Beispiel
Betrachten Sie zur Veranschaulichung ein einfaches Beispiel.
- Finden Sie die Werte der Variablen a, b, c, die den Ausdruck a + b = c erfüllen.
- A <b.
- Der Definitionsbereich der Variablen a, b und c ist {1, 2, 3}.
Ansatz
Betrachten wir ein einfaches Triple-Loop-Programm, da wir nur eine Kombination finden müssen, die die Einschränkung für jeden Wert im Definitionsbereich jeder Variablen erfüllt. In Java ausgedrückt sieht es so aus.
for (int a : List.of(1, 2, 3))
for (int b : List.of(1, 2, 3))
for (int c : List.of(1, 2, 3))
if (a < b)
if (a + b == c)
answer(a, b, c);
answer ist eine Rückruffunktion, die aufgerufen wird, wenn eine Lösung gefunden wird.
In diesem Programm wird der innerste Teil der verschachtelten for-Schleife 3 x 3 x 3 = 27 Mal ausgeführt.
In Anbetracht der Verarbeitungseffizienz kann dies ein wenig verbessert werden. Die Einschränkung "a <b" kann überprüft werden, wenn die Werte der Variablen "a" und "b" fest sind, so dass sie wie folgt umgeschrieben werden kann.
for (int a : List.of(1, 2, 3))
for (int b : List.of(1, 2, 3))
if (a < b)
for (int c : List.of(1, 2, 3))
if (a + b == c)
answer(a, b, c);
Es gibt nur drei Kombinationen von "(a, b)", die "a <b" erfüllen: "(1, 2), (1, 3), (2, 3)". Da "for (int c: List.of (1, 2, 3))" für jede dieser drei Möglichkeiten ausgeführt wird, sollte der innerste Teil der verschachtelten for-Schleife 3 x 3 = 9 mal sein. Wird sein. Sie können mit der dreifachen Verarbeitungsleistung im Vergleich zum obigen Code rechnen. Es kann schneller sein, da es auch die Anzahl der Einschränkungsprüfungen verringert. Lassen Sie uns das Programm mit diesem Ansatz konfigurieren. Zusammenfassend sieht es so aus.
- Schmale Schleifen, die jeder Variablen nacheinander die Werte des Definitionsbereichs zuweisen.
- Einschränkungen werden in der äußeren Schleife so weit wie möglich überprüft, um die Effizienz zu verbessern.
- Rufen Sie die Rückruffunktion auf, wenn eine Lösung gefunden wurde.
Modell-
Das Folgende sind mögliche Klassenkandidaten.
- Problem
Eine Klasse von Problemen, die es zu lösen gilt. - Variable
Die Variable, die in Frage kommt. - Domain
Der Definitionsbereich für jede Variable. - Einschränkung
Der Einschränkungsausdruck, den die Variable erfüllen muss. - Prädikat
Eine funktionale Schnittstelle zum Ausdrücken von Einschränkungsausdrücken als Lambda-Ausdrücke. - Problemlösung (Solver)
Das Problem lösen. - Antwort
Ein Rückruf, der aufgerufen wird, wenn eine Lösung gefunden wird.
Es sieht so aus, wenn es als UML-Klassendiagramm ausgedrückt wird.
Code
Domain ist eine Liste unveränderlicher Ganzzahlen.
Domain.java
public class Domain extends AbstractList<Integer> {
private final int[] elements;
private Domain(int... elements) {
this.elements = elements;
}
public static Domain of(int... elements) {
return new Domain(Arrays.copyOf(elements, elements.length));
}
public static Domain range(int startInclusive, int endExclusive) {
return new Domain(IntStream.range(startInclusive, endExclusive).toArray());
}
public static Domain rangeClosed(int startInclusive, int endInclusive) {
return range(startInclusive, endInclusive + 1);
}
@Override public Integer get(int index) { return elements[index]; }
@Override public int size() { return elements.length; }
}
Eine Variable ist eine Klasse mit einem Namen und einer Domäne. Enthält Verweise auf alle Einschränkungen für diese Variable. Da die Instanz von der Factory-Methode des Problems (Problem) erstellt wird, ist der Konstruktor der Paketbereich.
Variable.java
public class Variable {
public final String name;
public final Domain domain;
private final List<Constraint> _constraints = new ArrayList<Constraint>();
public final List<Constraint> constraints = Collections.unmodifiableList(_constraints);
Variable(String name, Domain domain) {
this.name = name;
this.domain = domain;
}
void add(Constraint constraint) {
this._constraints.add(constraint);
}
@Override
public String toString() {
return name;
}
}
Prädikat ist eine Funktionsschnittstelle zum Ausdrücken von Einschränkungen in Ausdrücken.
Es wird nur die Methode test (int ...) definiert, die mit dem Wert jeder Variablen als Argument aufgerufen wird, wenn die Werte aller Variablen, die sich auf die Einschränkung beziehen, gebunden sind.
Sie können dies verwenden, um einen Einschränkungsausdruck als Lambda-Ausdruck auszudrücken.
Predicate.java
@FunctionalInterface
public interface Predicate {
boolean test(int... values);
}
Eine Einschränkung ist eine unveränderliche Klasse, die einen Einschränkungsausdruck (Prädikat) und einen Verweis auf die der Einschränkung zugeordnete Variable enthält. Da die Instanz von der Factory-Methode des Problems (Problem) erstellt wird, ist der Konstruktor der Paketbereich.
Constraint.java
public class Constraint {
public final Predicate predicate;
public final List<Variable> variables;
Constraint(Predicate predicate, Variable... variables) {
this.predicate = predicate;
this.variables = List.of(variables);
}
@Override
public String toString() {
return "Zwang" + variables;
}
}
Problem ist eine Klasse mit allen relevanten Variablen und Einschränkungen. Variablen werden durch "Variable (String, Domain)" definiert. Einschränkungen werden mit "Einschränkung (Prädikat, Variable ...)" definiert. Für mehrere Variablen gibt es eine Methode "allDifferent (Variable ...)", um die Einschränkung, dass jeweils zwei Variablen unterschiedliche Werte haben, einfach auszudrücken.
Problem.java
public class Problem {
private List<Variable> _variables = new ArrayList<>();
public List<Variable> variables = Collections.unmodifiableList(_variables);
private Map<String, Variable> variableMap = new HashMap<>();
private List<Constraint> _constraints = new ArrayList<>();
public List<Constraint> constraints = Collections.unmodifiableList(_constraints);
public Variable variable(String name, Domain domain) {
if (variableMap.containsKey(name))
throw new IllegalArgumentException("Name der Variablen duplizieren: " + name);
Variable v = new Variable(name, domain);
this._variables.add(v);
this.variableMap.put(name, v);
return v;
}
public Variable variable(String name) {
return variableMap.get(name);
}
public Constraint constraint(Predicate predicate, Variable... variables) {
Constraint c = new Constraint(predicate, variables);
for (Variable v : variables)
v.add(c);
this._constraints.add(c);
return c;
}
public void allDifferent(Variable... variables) {
for (int i = 0, size = variables.length; i < size; ++i)
for (int j = i + 1; j < size; ++j)
constraint(a -> a[0] != a[1], variables[i], variables[j]);
}
}
Antwort ist eine Rückruffunktion, um die gefundene Lösung zu erhalten. Erhält ein Variablenwertpaar als Map. Da es sich effektiv um eine Funktionsschnittstelle handelt, können Sie eine Rückruffunktion mit einem Lambda-Ausdruck schreiben.
Answer.java
public interface Answer {
void answer(Map<Variable, Integer> result);
}
Solver (Solver) hat eine Methode zum Lösen (Problem, Antwort), die eine Lösung aus einem Problem (Problem) findet.
Da die Anzahl der Variablen variabel ist, ist es nicht möglich, eine Bindung durch Verschachteln für Anweisungen zu realisieren, wie zu Beginn beschrieben. Daher wird die Bindung durch einen Wiederholungsaufruf ausgeführt.
Mit der überladenen Methode "lösen (Problem, Liste ConstraintOrder (List <Variable>, List <Constraint>) ermittelt die Reihenfolge der anwendbaren Constraints (Constraint) aus der Bindungsreihenfolge der Variablen.
Solver.java
public class Solver {
static final Logger logger = Logger.getLogger(Solver.class.getName());
static List<List<Constraint>> constraintOrder(List<Variable> bindingOrder, List<Constraint> constraints) {
int variableSize = bindingOrder.size();
int constraintSize = constraints.size();
List<List<Constraint>> result = new ArrayList<>(variableSize);
Set<Constraint> done = new HashSet<>(constraintSize);
Set<Variable> bound = new HashSet<>(variableSize);
for (Variable v : bindingOrder) {
bound.add(v);
List<Constraint> list = new ArrayList<>();
result.add(list);
for (Constraint c : constraints)
if (!done.contains(c) && bound.containsAll(c.variables)) {
list.add(c);
done.add(c);
}
}
return result;
}
public void solve(Problem problem, List<Variable> bindingOrder, Answer answer) {
int variableSize = problem.variables.size();
List<List<Constraint>> constraintOrder = constraintOrder(bindingOrder, problem.constraints);
int[] arguments = new int[variableSize];
Map<Variable, Integer> result = new LinkedHashMap<>(variableSize);
new Object() {
boolean test(int i) {
for (Constraint c : constraintOrder.get(i)) {
int p = 0;
for (Variable v : c.variables)
arguments[p++] = result.get(v);
if (!c.predicate.test(arguments))
return false;
}
return true;
}
void solve(int i) {
if (i >= variableSize)
answer.answer(result);
else {
Variable v = bindingOrder.get(i);
Domain d = v.domain;
for (int value : d) {
result.put(v, value);
if (test(i))
solve(i + 1);
}
}
}
}.solve(0);
}
public void solve(Problem problem, Answer answer) {
solve(problem, problem.variables, answer);
}
}
Prüfung
Lassen Sie uns das einfache Beispiel am Anfang lösen.
Problem problem = new Problem();
Domain domain = Domain.of(1, 2, 3);
Variable A = problem.variable("A", domain);
Variable B = problem.variable("B", domain);
Variable C = problem.variable("C", domain);
Constraint X = problem.constraint(a -> a[0] + a[1] == a[2], A, B, C);
Constraint Y = problem.constraint(a -> a[0] < a[1], A, B);
Solver solver = new Solver();
solver.solve(problem, result -> System.out.println(result));
Das Ergebnis ist so.
{A=1, B=2, C=3}
Die Bindungsreihenfolge von Variablen und die Anwendungsreihenfolge von Einschränkungen sind wie folgt.
0: A [] 1: B [Einschränkung [A, B]] 2: C [Einschränkungen [A, B, C]]
Acht Königin
[Eight Queen-Wikipedia](https://ja.wikipedia.org/wiki/%E3%82%A8%E3%82%A4%E3%83%88%E3%83%BB%E3%82%AF % E3% 82% A4% E3% 83% BC% E3% 83% B3) ist das Problem, acht Königinnen auf das Schachbrett zu setzen. Zu diesem Zeitpunkt sollte sich keines der Teile in einer Position befinden, in der sie von anderen Teilen übernommen werden können. Die Königin bewegt sich in acht Richtungen, nach oben, unten, links, rechts und diagonal, solange es keine Hindernisse gibt. Es ist eine Bewegung, die das fliegende Auto von Shogi und die Ecklinie kombiniert. Eine modifizierte Version mit einem Quadrat als n wird als "n-Königin" -Puzzle bezeichnet. Bereiten Sie n Variablen vor, deren Definitionsbereich $ \ {1..n \} $ ist, und lösen Sie sie als Problem, sodass sie sich voneinander unterscheiden und sich nicht diagonal überlappen. Hier finden Sie die Anzahl der Lösungen für $ n ∊ \ {1, 2, 3, 4, 5, 6, 7, 8, 9, 10 \} $.
class TestNQueens {
static Logger logger = Logger.getLogger(TestNQueens.class.getName());
static int nQueens(final int n) {
long start = System.currentTimeMillis();
Problem problem = new Problem();
Domain domain = Domain.range(0, n);
Variable[] rows = IntStream.range(0, n)
.mapToObj(i -> problem.variable("R" + i, domain))
.toArray(Variable[]::new);
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j) {
int distance = j - i;
problem.constraint(
(x, y) -> x != y && Math.abs(x - y) != distance, rows[i], rows[j]);
}
Solver solver = new Solver();
int[] answers = {0};
solver.solve(problem, m -> ++answers[0]);
logger.info("n=" + n + " : answers=" + answers[0]
+ " : elapse=" + (System.currentTimeMillis() - start) + "ms.");
return answers[0];
}
@Test
void test() {
assertEquals(1, nQueens(1));
assertEquals(0, nQueens(2));
assertEquals(0, nQueens(3));
assertEquals(2, nQueens(4));
assertEquals(10, nQueens(5));
assertEquals(4, nQueens(6));
assertEquals(40, nQueens(7));
assertEquals(92, nQueens(8));
assertEquals(352, nQueens(9));
assertEquals(724, nQueens(10));
}
}
Das Ergebnis sieht so aus. Es stimmte mit der Beschreibung auf Wikipedia überein.
2020-05-19T16:31:06.863 Informationen n=1 : answers=1 : elapse=27ms.
2020-05-19T16:31:06.941 Informationen n=2 : answers=0 : elapse=3ms.
2020-05-19T16:31:06.942 Informationen n=3 : answers=0 : elapse=0ms.
2020-05-19T16:31:06.944 Informationen n=4 : answers=2 : elapse=0ms.
2020-05-19T16:31:06.947 Informationen n=5 : answers=10 : elapse=2ms.
2020-05-19T16:31:06.953 Information n=6 : answers=4 : elapse=5ms.
2020-05-19T16:31:06.963 Informationen n=7 : answers=40 : elapse=10ms.
2020-05-19T16:31:06.984 Informationen n=8 : answers=92 : elapse=20ms.
2020-05-19T16:31:07.031 Information n=9 : answers=352 : elapse=45ms.
2020-05-19T16:31:07.118 Informationen n=10 : answers=724 : elapse=87ms.
Maskierte Berechnung
Als nächstes lösen wir die Maskenberechnung. Es ist das berühmte SEND MORE MONEY. Weisen Sie jedem Buchstaben eine einstellige Zahl zu, damit die Formel gilt. Das gleiche Alphabet ist die gleiche Zahl, verschiedene Alphabete sind verschiedene Zahlen und die erste Zahl ist ungleich Null.
SEND
+ MORE
------
MONEY
static Logger logger = Logger.getLogger(TestSendMoreMoney.class.getName());
static int number(int... digits) {
return IntStream.of(digits).reduce(0, (t, d) -> t * 10 + d);
}
@Test
Einzelne Einschränkung des öffentlichen Leertests() {
Problem problem = new Problem();
Domain first = Domain.of(1, 2, 3, 4, 5, 6, 7, 8, 9);
Domain rest = Domain.of(0, 1, 2, 3, 4, 5, 6, 7, 8, 9);
Variable S = problem.variable("S", first);
Variable E = problem.variable("E", rest);
Variable N = problem.variable("N", rest);
Variable D = problem.variable("D", rest);
Variable M = problem.variable("M", first);
Variable O = problem.variable("O", rest);
Variable R = problem.variable("R", rest);
Variable Y = problem.variable("Y", rest);
Variable[] variables = {S, E, N, D, M, O, R, Y};
problem.allDifferent(variables);
problem.constraint(a ->
number(a[0], a[1], a[2], a[3]) + number(a[4], a[5], a[6], a[1])
== number(a[4], a[5], a[2], a[1], a[7]), variables);
Solver solver = new Solver();
solver.solve(problem, m -> logger.info(m.toString()));
}
Das Ergebnis ist so.
{S=9, E=5, N=6, D=7, M=1, O=0, R=8, Y=2}
Diese Lösung hat nur eine Einschränkung und wird überprüft, nachdem alle Variablen gebunden wurden. Mit anderen Worten, es ist nicht sehr effizient, da die Einschränkungsprüfung in der innersten Schleife durchgeführt wird. In meiner Umgebung dauerte es weniger als 2 Sekunden. Es ist etwas schneller, wenn Sie eine Übertragsvariable hinzufügen und für jede Ziffer eine Einschränkung definieren.
@Test
öffentlicher Leertest Ziffernweise Einschränkungen() {
Domain zero = Domain.of(0);
Domain first = Domain.of(1, 2, 3, 4, 5, 6, 7, 8, 9);
Domain rest = Domain.of(0, 1, 2, 3, 4, 5, 6, 7, 8, 9);
Domain carry = Domain.of(0, 1);
Problem problem = new Problem();
Variable Z = problem.variable("Z", zero);
Variable C1 = problem.variable("C1", carry);
Variable C2 = problem.variable("C2", carry);
Variable C3 = problem.variable("C3", carry);
Variable C4 = problem.variable("C4", carry);
Variable S = problem.variable("S", first);
Variable E = problem.variable("E", rest);
Variable N = problem.variable("N", rest);
Variable D = problem.variable("D", rest);
Variable M = problem.variable("M", first);
Variable O = problem.variable("O", rest);
Variable R = problem.variable("R", rest);
Variable Y = problem.variable("Y", rest);
Variable[] variables = {S, E, N, D, M, O, R, Y};
problem.allDifferent(variables);
// C4 C3 C2 C1 Z
// Z S E N D
// + Z M O R E
// ---------------
// M O N E Y
Predicate digitPredicate = a -> a[0] + a[1] + a[2] == a[3] + a[4] * 10;
problem.constraint(digitPredicate, Z, D, E, Y, C1);
problem.constraint(digitPredicate, C1, N, R, E, C2);
problem.constraint(digitPredicate, C2, E, O, N, C3);
problem.constraint(digitPredicate, C3, S, M, O, C4);
problem.constraint(digitPredicate, C4, Z, Z, M, Z);
Solver solver = new Solver();
solver.solve(problem, m -> logger.info(m.toString()));
}
Es kann in ca. 0,3 Sekunden gelöst werden.
Sudoku
Lösen wir das erste Problem in Sugoku-Wikipedia.
static Logger logger = Logger.getLogger(Prüfung.class.toString());
statische int Seitenlänge= 9;
statisch int Seitenlänge des kleinen Quadrats= 3;
statischer Domänendefinitionsbereich= Domain.rangeClosed(1, 9);
statischer Stringname(int r, int c) {
return r + "@" + c;
}
static Variable[][]Variablendefinition(Problem Problem, int[][]Eingang) {
Variable[][]Variable= new Variable[Seitenlänge][Seitenlänge];
for (int r = 0; r <Seitenlänge; ++r)
for (int c = 0; c <Seitenlänge; ++c)
Variable[r][c] =Problem.variable(Name(r, c),
Eingang[r][c] == 0 ?Definitionsbereich: Domain.of(Eingang[r][c]));
Rückgabevariable;
}
static List<Variable[]>Einschränkungsdefinition(Problem Problem, Variable[][]Variable) {
List<Variable[]>Einschränkungsvariable= new ArrayList<>();
for (int r = 0; r <Seitenlänge; ++r)
Einschränkungsvariable.add(Variable[r]);
for (int c = 0; c <Seitenlänge; ++c) {
Variable[] va = new Variable[Seitenlänge];
Einschränkungsvariable.add(va);
for (int r = 0; r <Seitenlänge; ++r)
va[r] =Variable[r][c];
}
for (int r = 0; r <Seitenlänge; r +=Seitenlänge des kleinen Quadrats)
for (int c = 0; c <Seitenlänge; c +=Seitenlänge des kleinen Quadrats) {
Variable[] va = new Variable[Seitenlänge];
Einschränkungsvariable.add(va);
for (int i = 0, p = 0; i <Seitenlänge des kleinen Quadrats; ++i)
for (int j = 0; j <Seitenlänge des kleinen Quadrats; ++j, ++p)
va[p] =Variable[r + i][c + j];
}
for (Variable[] va :Einschränkungsvariable)
Problem.allDifferent(va);
Rückgabeschränkungsvariable;
}
statische leere Antwort(Variable[][]Variable, Map<Variable, Integer>Antworten) {
for (int r = 0; r <Seitenlänge; ++r) {
StringBuilder sb = new StringBuilder();
for (int c = 0; c <Seitenlänge; ++c)
sb.append(String.format("%2d",Antworten.get(Variable[r][c])));
logger.info(sb.toString());
}
}
statische Leerenzahl Einzelbindungsreihenfolge nicht angegeben(int[][]Eingang) {
Problem Problem= new Problem();
Variable[][]Variable=Variablendefinition(Problem,Eingang);
Einschränkungsdefinition(Problem,Variable);
Solver Solver= new Solver();
Lösung.solve(Problem, m ->Antworten(Variable, m));
}
@Test
void testWikipedia Keine verbindliche Reihenfolge angegeben() {
//Wikipedia Numerisches Beispiel
// https://ja.wikipedia.org/wiki/%E6%95%B0%E7%8B%AC
int[][]Eingang= {
{ 5, 3, 0, 0, 7, 0, 0, 0, 0 },
{ 6, 0, 0, 1, 9, 5, 0, 0, 0 },
{ 0, 9, 8, 0, 0, 0, 0, 6, 0 },
{ 8, 0, 0, 0, 6, 0, 0, 0, 3 },
{ 4, 0, 0, 8, 0, 3, 0, 0, 1 },
{ 7, 0, 0, 0, 2, 0, 0, 0, 6 },
{ 0, 6, 0, 0, 0, 0, 2, 8, 0 },
{ 0, 0, 0, 4, 1, 9, 0, 0, 5 },
{ 0, 0, 0, 0, 8, 0, 0, 7, 9 },
};
logger.info("test wikipedia");
Keine Nummer angegeben verbindliche Reihenfolge(Eingang);
}
Ich habe es vorerst gelöst, aber es hat mehr als 20 Sekunden gedauert.
2020-05-16T21:01:31.789 info test wikipedia
2020-05-16T21:01:52.360 Informationen 5 3 4 6 7 8 9 1 2
2020-05-16T21:01:52.361 Informationen 6 7 2 1 9 5 3 4 8
2020-05-16T21:01:52.361 Informationen 1 9 8 3 4 2 5 6 7
2020-05-16T21:01:52.362 Informationen 8 5 9 7 6 1 4 2 3
2020-05-16T21:01:52.363 Informationen 4 2 6 8 5 3 7 9 1
2020-05-16T21:01:52.363 Informationen 7 1 3 9 2 4 8 5 6
2020-05-16T21:01:52.363 Informationen 9 6 1 5 3 7 2 8 4
2020-05-16T21:01:52.364 Informationen 2 8 7 4 1 9 6 3 5
2020-05-16T21:01:52.365 Informationen 3 4 5 2 8 6 1 7 9
Die Bindungsreihenfolge der Variablen ist einfach von oben nach unten und von links nach rechts. Lassen Sie uns also ein wenig darüber nachdenken. Die verbindliche Reihenfolge wird durch die folgende Richtlinie definiert.
- Binden Sie die Quadrate, deren Zahlen zuerst bestimmt werden. Diese Quadrate haben keine Rückverfolgungswertbestimmung.
- Sehen Sie sich jede Zeile, Spalte und jeden 3x3-Bereich an und binden Sie sie in der Reihenfolge von der Stelle mit den am meisten nummerierten Quadraten. Wie in der folgenden Abbildung gezeigt, hat der blau dargestellte Bereich 6 feste Werte. Für die vier rot dargestellten Bereiche sind fünf Werte festgelegt. Binden Sie die Variablen im blauen Bereich → die Variablen im roten Bereich → ...
Der folgende Code ändert die Bindungsreihenfolge von Variablen gemäß dieser Richtlinie.
static List<Variable>Bindungsauftragsdefinition(List<Variable>Variable, List<Variable[]>Einschränkungsvariable) {
Set<Variable>Verbindliche Reihenfolge= new LinkedHashSet<>();
for (Variable v :Variable)
if (v.domain.size() == 1)
Verbindliche Reihenfolge.add(v);
Collections.sort(Einschränkungsvariable,
Comparator.comparingInt(a -> Arrays.stream(a).mapToInt(v -> v.domain.size()).sum()));
for (Variable[] a :Einschränkungsvariable)
for (Variable v : a)
Verbindliche Reihenfolge.add(v);
return new ArrayList<>(Verbindliche Reihenfolge);
}
statische Leere Nummer Einzelbindungsreihenfolge angegeben(int[][]Eingang) {
Problem Problem= new Problem();
Variable[][]Variable=Variablendefinition(Problem,Eingang);
List<Variable[]>Einschränkungsvariable=Einschränkungsdefinition(Problem,Variable);
List<Variable>Verbindliche Reihenfolge=Bindungsauftragsdefinition(Problem.variables,Einschränkungsvariable);
Solver Solver= new Solver();
Lösung.solve(Problem,Verbindliche Reihenfolge, m ->Antworten(Variable, m));
}
Infolgedessen kann es in ungefähr 0,02 Sekunden gelöst werden. Dieses Beispiel ist zu einfach, deshalb habe ich ein schwierigeres Problem versucht. Laut Wikipedia müssen 17 oder mehr Quadrate mit festen Zahlen vorhanden sein, damit die deutsche Lösung eindeutig ist. Ich habe im Internet gesucht und genau 17 schwierige Probleme mit festen Zahlen festgestellt.
@Test
void testGood_at_Sudoku_Heres_some_youll_never_complete() {
// http://theconversation.com/good-at-sudoku-heres-some-youll-never-complete-5234
int[][]Eingang= {
{ 0, 0, 0, 7, 0, 0, 0, 0, 0 },
{ 1, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 4, 3, 0, 2, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 6 },
{ 0, 0, 0, 5, 0, 9, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 4, 1, 8 },
{ 0, 0, 0, 0, 8, 1, 0, 0, 0 },
{ 0, 0, 2, 0, 0, 0, 0, 5, 0 },
{ 0, 4, 0, 0, 0, 0, 3, 0, 0 },
};
logger.info("Good at Sudoku Heres some youll never complete");
Nummer Einzelbindungsreihenfolge angegeben(Eingang);
}
Ich konnte es innerhalb von 1 Sekunde lösen.
2020-05-16T21:22:26.176 Informationen Gut in Sudoku Hier sind einige, die Sie nie vervollständigen werden
2020-05-16T21:22:26.310 Informationen 2 6 4 7 1 5 8 3 9
2020-05-16T21:22:26.311 Informationen 1 3 7 8 9 2 6 4 5
2020-05-16T21:22:26.312 Informationen 5 9 8 4 3 6 2 7 1
2020-05-16T21:22:26.313 Informationen 4 2 3 1 7 8 5 9 6
2020-05-16T21:22:26.315 Informationen 8 1 6 5 4 9 7 2 3
2020-05-16T21:22:26.316 Informationen 7 5 9 6 2 3 4 1 8
2020-05-16T21:22:26.317 Informationen 3 7 5 2 8 1 9 6 4
2020-05-16T21:22:26.318 Informationen 9 8 2 3 6 4 1 5 7
2020-05-16T21:22:26.320 Informationen 6 4 1 9 5 7 3 8 2
Wenn Sie die Bindungsreihenfolge der Variablen nicht angegeben haben, konnte sie auch nach 10 Minuten nicht gelöst werden.
Verbesserung des Einschränkungsausdrucks
Geben Sie beim Definieren einer Einschränkung die Variablen an, die dem Lambda-Ausdruck zugeordnet sind. So wird es geschrieben, weil die Anzahl der Variablen, die Einschränkungen unterliegen, variabel ist.
problem.constraint(a ->
number(a[0], a[1], a[2], a[3])
+ number(a[4], a[5], a[6], a[1])
== number(a[4], a[5], a[2], a[1], a[7]),
S, E, N, D, M, O, R, Y);
Es gibt eine Entsprechung zwischen "a [0]" zu "S", "a [1]" zu "E" usw., aber der Ausdruck ist schwer zu verstehen. Um dies zu verbessern, fügen Sie eine Argumentmethode mit fester Länge hinzu. Fügen Sie zunächst die folgende Schnittstelle hinzu.
@FunctionalInterface
public interface Predicate1 extends Predicate {
default boolean test(int... values) {
return test(values[0]);
}
boolean test(int a);
}
@FunctionalInterface
public interface Predicate2 extends Predicate {
default boolean test(int... values) {
return test(values[0], values[1]);
}
boolean test(int a, int b);
}
.....
Fügen Sie dann der Problemklasse eine Constraint Factory-Methode hinzu, die diese verwendet.
Problem.java
public Constraint constraint(Predicate1 predicate, Variable a) {
return constraint((Predicate)predicate, a);
}
public Constraint constraint(Predicate2 predicate, Variable a, Variable b) {
return constraint((Predicate)predicate, a, b);
}
.....
Dann können Sie so schreiben. Ein Kompilierungsfehler tritt auf, wenn die Anzahl der an die Constraint () -Methode übergebenen Variablen nicht mit der Anzahl der Argumente im Lambda-Ausdruck übereinstimmt.
problem.constraint((s, e, n, d, m, o, r, y) ->
number(s, e, n, d)
+ number(m, o, r, e)
== number(m, o, n, e, y),
S, E, N, D, M, O, R, Y);
Zusammenfassung
Wir haben festgestellt, dass die folgenden Punkte die Leistung beeinflussen.
- ** Wie man Einschränkungen gibt **
Feinere Einschränkungen, damit Sie Variablenbindungen frühzeitig überprüfen können, beschleunigen Ihre Auswahl. - ** Reihenfolge der Variablenbindung **
Es ist schneller, wenn Sie die Variablen zuerst mit wenigen Auswahlmöglichkeiten binden.
Recommended Posts