Programmation par contraintes en Java
introduction
Programmation par contraintes (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) est l'un des paradigmes de programmation. En programmation par contraintes, le programme s'écrit en décrivant les relations entre les variables sous forme de contraintes. De nos jours, on dit souvent que l'IA est synonyme d'apprentissage en profondeur, mais dans le passé, cette programmation par contraintes et ce traitement mathématique étaient également appelés IA. Implémentez une bibliothèque de programmation de contraintes en Java et essayez de résoudre des problèmes tels que huit reines, des calculs masqués et des mathématiques.
Problème de cible
Ciblez les problèmes les plus simples. Plus précisément, les problèmes sont les suivants.
- La plage de définition des variables est uniquement des entiers.
- On suppose que la plage de définition de la variable est finie et la plage est définie dans le problème.
Exemple simple
Prenons un exemple simple à titre d'illustration.
- Trouvez les valeurs des variables a, b, c qui satisfont l'expression a + b = c.
- Cependant, a <b.
- La zone de définition des variables a, b et c est {1, 2, 3}.
approche
Considérons un simple programme triple boucle car il suffit de trouver une combinaison qui satisfait la contrainte pour chaque valeur dans la zone de définition de chaque variable. Exprimé en Java, cela ressemble à ceci.
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` est une fonction de rappel qui est appelée lorsqu'une solution est trouvée. Dans ce programme, la partie la plus interne de la boucle for imbriquée est exécutée 3 x 3 x 3 = 27 fois. Compte tenu de l'efficacité du traitement, cela peut être légèrement amélioré. La contrainte «a <b» peut être vérifiée lorsque les valeurs des variables «a» et «b» sont fixées, donc elle peut être réécrite comme suit.
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);
Il n'y a que trois combinaisons de «(a, b)» qui satisfont «a <b»: «(1, 2), (1, 3), (2, 3)». Puisque for (int c: List.of (1, 2, 3)) est exécuté pour chacune de ces trois manières, la partie la plus interne de la boucle for imbriquée devrait être 3 x 3 = 9 fois. Sera. Vous pouvez vous attendre à environ 3 fois les performances de traitement par rapport au code ci-dessus. Cela peut être plus rapide car cela réduit également le nombre de vérifications de contraintes.
Configurons le programme avec cette approche.
En résumé, ça ressemble à ça.
- Boucles étroites qui attribuent séquentiellement les valeurs de la zone de définition à chaque variable.
- Les contraintes sont vérifiées dans la boucle externe autant que possible pour améliorer l'efficacité.
- Appelez la fonction de rappel lorsqu'une solution est trouvée.
modèle
Voici des candidats possibles pour la classe.
- Problème
Une classe de problèmes à résoudre. - Variable
La variable qui apparaît en question. - Domaine
La zone de définition de chaque variable. - Contrainte
Expression de contrainte que la variable doit satisfaire. - Prédicat
Une interface fonctionnelle pour exprimer des expressions de contrainte sous forme d'expressions lambda. - Résolution de problèmes (Solver)
Résoudre le problème. - Réponse
Un rappel qui sera appelé lorsqu'une solution est trouvée.
Il ressemble à ceci lorsqu'il est exprimé sous forme de diagramme de classes UML.
code
Le domaine est une liste d'entiers immuables.
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; }
}
Une variable est une classe qui a un nom et un domaine. Contient des références à toutes les contraintes pour cette variable. Puisque l'instance est créée par la méthode de fabrique du problème (problème), le constructeur est la portée du package.
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;
}
}
Predicate est une interface de fonction pour exprimer des contraintes dans des expressions.
Seule la méthode test (int ...), qui est appelée avec la valeur de chaque variable comme argument lorsque les valeurs de toutes les variables liées à la contrainte sont liées, est définie.
Vous pouvez l'utiliser pour exprimer une expression de contrainte en tant qu'expression lambda.
Predicate.java
@FunctionalInterface
public interface Predicate {
boolean test(int... values);
}
Une contrainte est une classe immuable qui a une expression de contrainte (Predicate) et une référence à la variable associée à la contrainte. Puisque l'instance est créée par la méthode de fabrique du problème (problème), le constructeur est la portée du package.
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 "Contrainte" + variables;
}
}
Un problème est une classe avec toutes les variables et contraintes pertinentes.
Les variables sont définies par variable (String, Domain).
Les contraintes sont définies avec contrainte (Predicate, Variable ...).
Pour plusieurs variables, il existe une méthode ʻallDifferent (Variable ...) `pour exprimer facilement la contrainte que chacune des deux variables a des valeurs différentes.
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("Nom de variable en double: " + 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]);
}
}
La réponse est une fonction de rappel pour recevoir la solution trouvée. Reçoit une paire variable-valeur sous forme de carte Puisqu'il s'agit en fait d'une interface de fonction, vous pouvez écrire une fonction de rappel avec une expression lambda.
Answer.java
public interface Answer {
void answer(Map<Variable, Integer> result);
}
Solver (Solver) a une méthode résoudre (problème, réponse) qui trouve une solution à un problème (problème).
Comme le nombre de variables est variable, il n'est pas possible de réaliser la liaison en imbriquant les instructions comme décrit au début, la liaison est donc effectuée par un appel de récurrence.
La méthode surchargée résoudre (Problème, Liste <Variable>, Réponse) vous permet de spécifier l'ordre dans lequel les variables sont liées lors de la résolution du problème avec Liste <Variable>.
La méthode statique interne constraintOrder (List <Variable>, List <Constraint>) trouve l'ordre des contraintes applicables (Constraint) à partir de l'ordre de liaison des variables.
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);
}
}
tester
Résolvons en fait l'exemple simple au début.
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));
Le résultat est comme ça.
{A=1, B=2, C=3}
L'ordre de liaison des variables et l'ordre d'application des contraintes sont les suivants.
0: A [] 1: B [contrainte [A, B]] 2: C [contraintes [A, B, C]]
Huit Reine
[Huit reine-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) est le problème de placer huit reines sur l'échiquier. À ce stade, aucune des pièces ne doit être dans une position où elles peuvent être prises par d'autres pièces. La reine se déplace dans huit directions, haut, bas, gauche, droite et diagonale, tant qu'il n'y a pas d'obstacles. C'est un mouvement qui combine la voiture volante de Shogi et la ligne de coin. Une version modifiée avec un carré comme n est appelée un puzzle «n-queen». Préparez n variables dont la zone de définition est $ \ {1..n \} $, et résolvez-les comme un problème afin qu'elles soient différentes les unes des autres et ne se chevauchent pas en diagonale. Ici, trouvons le nombre de solutions pour $ 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));
}
}
Le résultat ressemble à ceci. Cela correspondait à la description sur Wikipedia.
2020-05-19T16:31:06.863 Informations n=1 : answers=1 : elapse=27ms.
2020-05-19T16:31:06.941 Informations n=2 : answers=0 : elapse=3ms.
2020-05-19T16:31:06.942 Informations n=3 : answers=0 : elapse=0ms.
2020-05-19T16:31:06.944 Informations n=4 : answers=2 : elapse=0ms.
2020-05-19T16:31:06.947 Informations n=5 : answers=10 : elapse=2ms.
2020-05-19T16:31:06.953 Informations n=6 : answers=4 : elapse=5ms.
2020-05-19T16:31:06.963 Informations n=7 : answers=40 : elapse=10ms.
2020-05-19T16:31:06.984 Informations n=8 : answers=92 : elapse=20ms.
2020-05-19T16:31:07.031 Informations n=9 : answers=352 : elapse=45ms.
2020-05-19T16:31:07.118 Informations n=10 : answers=724 : elapse=87ms.
Calcul masqué
Ensuite, résolvons le calcul du masque. C'est le fameux ENVOYER PLUS D'ARGENT. Attribuez un nombre à un chiffre à chaque lettre pour que la formule soit valable. Le même alphabet est le même nombre, différents alphabets sont des nombres différents et le premier nombre est différent de zéro.
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
contrainte unique de test public void() {
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()));
}
Le résultat est comme ça.
{S=9, E=5, N=6, D=7, M=1, O=0, R=8, Y=2}
Cette solution n'a qu'une seule contrainte et est vérifiée une fois que toutes les variables ont été liées. En d'autres termes, ce n'est pas très efficace car le contrôle des contraintes se fait dans la boucle la plus interne. Cela a pris moins de 2 secondes dans mon environnement. C'est un peu plus rapide si vous ajoutez une variable de retenue et définissez une contrainte pour chaque chiffre.
@Test
public void test Contraintes chiffre par chiffre() {
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()));
}
Il peut être résolu en environ 0,3 seconde.
Sudoku
Résolvons le premier problème dans Sugoku-Wikipedia.
static Logger logger = Logger.getLogger(Tester.class.toString());
longueur de côté statique int= 9;
static int Longueur du côté du petit carré= 3;
zone de définition de domaine statique= Domain.rangeClosed(1, 9);
nom de chaîne statique(int r, int c) {
return r + "@" + c;
}
static Variable[][]Définition variable(Problème problème, int[][]contribution) {
Variable[][]variable= new Variable[Longueur du côté][Longueur du côté];
for (int r = 0; r <Longueur du côté; ++r)
for (int c = 0; c <Longueur du côté; ++c)
variable[r][c] =problème.variable(Nom(r, c),
contribution[r][c] == 0 ?Zone de définition: Domain.of(contribution[r][c]));
variable de retour;
}
static List<Variable[]>Définition de la contrainte(Problème problème, Variable[][]variable) {
List<Variable[]>Variable de contrainte= new ArrayList<>();
for (int r = 0; r <Longueur du côté; ++r)
Variable de contrainte.add(variable[r]);
for (int c = 0; c <Longueur du côté; ++c) {
Variable[] va = new Variable[Longueur du côté];
Variable de contrainte.add(va);
for (int r = 0; r <Longueur du côté; ++r)
va[r] =variable[r][c];
}
for (int r = 0; r <Longueur du côté; r +=Longueur de côté du petit carré)
for (int c = 0; c <Longueur du côté; c +=Longueur de côté du petit carré) {
Variable[] va = new Variable[Longueur du côté];
Variable de contrainte.add(va);
for (int i = 0, p = 0; i <Longueur de côté du petit carré; ++i)
for (int j = 0; j <Longueur de côté du petit carré; ++j, ++p)
va[p] =variable[r + i][c + j];
}
for (Variable[] va :Variable de contrainte)
problème.allDifferent(va);
variable de contrainte de retour;
}
réponse vide statique(Variable[][]variable, Map<Variable, Integer>répondre) {
for (int r = 0; r <Longueur du côté; ++r) {
StringBuilder sb = new StringBuilder();
for (int c = 0; c <Longueur du côté; ++c)
sb.append(String.format("%2d",répondre.get(variable[r][c])));
logger.info(sb.toString());
}
}
numéro vide statique ordre de liaison unique non spécifié(int[][]contribution) {
Problème problème= new Problem();
Variable[][]variable=Définition variable(problème,contribution);
Définition de la contrainte(problème,variable);
Solveur Solveur= new Solver();
Solution.solve(problème, m ->Répondre(variable, m));
}
@Test
void testWikipedia Aucune commande obligatoire spécifiée() {
//Exemple numérique Wikipedia
// https://ja.wikipedia.org/wiki/%E6%95%B0%E7%8B%AC
int[][]contribution= {
{ 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");
Aucun numéro d'ordre contraignant spécifié(contribution);
}
Je l'ai résolu pour le moment, mais cela a pris plus de 20 secondes.
2020-05-16T21:01:31.789 info test wikipedia
2020-05-16T21:01:52.360 Informations 5 3 4 6 7 8 9 1 2
2020-05-16T21:01:52.361 Informations 6 7 2 1 9 5 3 4 8
2020-05-16T21:01:52.361 Informations 1 9 8 3 4 2 5 6 7
2020-05-16T21:01:52.362 Informations 8 5 9 7 6 1 4 2 3
2020-05-16T21:01:52.363 Informations 4 2 6 8 5 3 7 9 1
2020-05-16T21:01:52.363 Informations 7 1 3 9 2 4 8 5 6
2020-05-16T21:01:52.363 Informations 9 6 1 5 3 7 2 8 4
2020-05-16T21:01:52.364 Informations 2 8 7 4 1 9 6 3 5
2020-05-16T21:01:52.365 Informations 3 4 5 2 8 6 1 7 9
L'ordre de liaison des variables est simplement de haut en bas et de gauche à droite, alors imaginons un peu. L'ordre de liaison est défini par la politique suivante.
- Liez les carrés dont les nombres sont déterminés en premier. Ces carrés n'ont aucune détermination de valeur de retour arrière.
- Examinez chaque ligne, colonne et zone 3x3 et liez-les dans l'ordre à partir de celle avec les carrés les plus numérotés. Comme le montre la figure ci-dessous, la zone représentée en bleu a 6 valeurs fixes. Cinq valeurs sont fixées pour les quatre zones indiquées en rouge. Liez les variables dans la zone bleue → les variables dans la zone rouge → ...
Le code suivant modifie l'ordre de liaison des variables conformément à cette stratégie.
static List<Variable>Définition de l'ordre contraignant(List<Variable>variable, List<Variable[]>Variable de contrainte) {
Set<Variable>Ordre contraignant= new LinkedHashSet<>();
for (Variable v :variable)
if (v.domain.size() == 1)
Ordre contraignant.add(v);
Collections.sort(Variable de contrainte,
Comparator.comparingInt(a -> Arrays.stream(a).mapToInt(v -> v.domain.size()).sum()));
for (Variable[] a :Variable de contrainte)
for (Variable v : a)
Ordre contraignant.add(v);
return new ArrayList<>(Ordre contraignant);
}
static void Numéro d'ordre de liaison unique spécifié(int[][]contribution) {
Problème problème= new Problem();
Variable[][]variable=Définition variable(problème,contribution);
List<Variable[]>Variable de contrainte=Définition de la contrainte(problème,variable);
List<Variable>Ordre contraignant=Définition de l'ordre contraignant(problème.variables,Variable de contrainte);
Solveur Solveur= new Solver();
Solution.solve(problème,Ordre contraignant, m ->Répondre(variable, m));
}
En conséquence, il peut être résolu en environ 0,02 seconde. Cet exemple est trop simple, j'ai donc essayé un problème plus difficile. Selon Wikipedia, il est nécessaire d'avoir 17 carrés ou plus avec des nombres fixes pour que la solution allemande soit unique. J'ai cherché sur le net et j'ai relevé exactement 17 problèmes difficiles avec des numéros fixes.
@Test
void testGood_at_Sudoku_Heres_some_youll_never_complete() {
// http://theconversation.com/good-at-sudoku-heres-some-youll-never-complete-5234
int[][]contribution= {
{ 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");
Numéro d'ordre de liaison unique spécifié(contribution);
}
J'ai pu le résoudre en 1 seconde.
2020-05-16T21:22:26.176 Information Bon au Sudoku Voici certains que vous ne terminerez jamais
2020-05-16T21:22:26.310 Informations 2 6 4 7 1 5 8 3 9
2020-05-16T21:22:26.311 Informations 1 3 7 8 9 2 6 4 5
2020-05-16T21:22:26.312 Informations 5 9 8 4 3 6 2 7 1
2020-05-16T21:22:26.313 Informations 4 2 3 1 7 8 5 9 6
2020-05-16T21:22:26.315 Informations 8 1 6 5 4 9 7 2 3
2020-05-16T21:22:26.316 Informations 7 5 9 6 2 3 4 1 8
2020-05-16T21:22:26.317 Informations 3 7 5 2 8 1 9 6 4
2020-05-16T21:22:26.318 Informations 9 8 2 3 6 4 1 5 7
2020-05-16T21:22:26.320 Informations 6 4 1 9 5 7 3 8 2
Si vous n'avez pas spécifié l'ordre de liaison des variables, il n'a pas pu être résolu même après 10 minutes.
Amélioration de l'expression des contraintes
Lors de la définition d'une contrainte, spécifiez les variables associées à l'expression lambda. C'est ainsi que cela s'écrit car le nombre de variables soumises à des contraintes est variable.
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);
Il existe une correspondance entre ʻa [0] et S, ʻa [1] et ʻE`, ..., mais l'expression est difficile à comprendre. Pour améliorer cela, ajoutez une méthode d'argument de longueur fixe. Tout d'abord, ajoutez l'interface suivante.
@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);
}
.....
Ajoutez ensuite une méthode de fabrique de contraintes qui l'utilise à la classe Problem.
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);
}
.....
Ensuite, vous pourrez écrire comme ça. Une erreur de compilation se produira si le nombre de «Variable» passé à la méthode «constraint ()» ne correspond pas au nombre d'arguments dans l'expression lambda.
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);
Résumé
Nous avons constaté que les points suivants affectent les performances.
- ** Comment donner des contraintes **
Des contraintes plus fines afin que vous puissiez vérifier tôt les liaisons de variables accéléreront vos choix. - ** Ordre de liaison des variables **
Ce sera plus rapide si vous liez d'abord les variables avec peu de choix.
Recommended Posts