在Java中进行约束编程

2 年 ago
雅, 悟
10 minutes

首先

制約编程是一种编程范式。在约束编程中，我们通过使用约束来描述变量之间的关系来编写程序。
目前，当提到人工智能时，往往会被认为是深度学习的同义词，但在过去，约束编程和数值处理等也被称为人工智能。
我们将在Java中实现一个约束编程库，并尝试解决八皇后、填字谜和数独等问题。

针对的问题

我们将针对最简单的问题进行讨论。具体来说，以下是一些例子。

    • 変数の定義域は整数のみとします。

 

    変数の定義域は有限で、その範囲は問題の中で定義されているものとします。

简单的例题

为了解释，我们来考虑一个简单的例子。

    • 式 a + b = c を満たす変数a, b, cの値を求めてください。

 

    • ただし a < b とします。

 

    変数a, b, cの定義域は{1, 2, 3}とします。

方法

我们只需要找到每个变量定义域的值满足约束条件的组合，因此我们可以考虑一个简单的三重循环程序来解决。在Java中表达如下：

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。
在这个程序中，嵌套的for循环的最内部会执行27次，即3 x 3 x 3。
考虑到运行效率，我们可以稍微改进它。约束条件a < b可以在变量a和b的值确定后进行检查，因此可以将其改写为以下形式。

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);

满足条件a < b的组合只有三种：(1, 2), (1, 3), (2, 3)。对于这三种组合，将执行嵌套的for循环最内部的for (int c : List.of(1, 2, 3))，这样总共执行9次。与前述代码相比，性能预计可以提高约3倍。由于约束检查次数也减少了，可能会更快。
让我们用这种方法来构建程序。
总结如下。

    • 各変数に定義域の値を順次代入するループを入れ子にします。

 

    • 制約はなるべく外側のループ内でチェックすることにより効率を上げます。

 

    解が見つかった時点でコールバック関数を呼び出します。

模特儿 (Mó tè ér)

作为候选班级，以下几个可能考虑的选项：

    • 問題 (Problem)

 

    • 解くべき問題のクラスです。

 

    • 変数 (Variable)

 

    • 問題に表れる変数です。

 

    • 定義域 (Domain)

 

    • 各変数の定義域です。

 

    • 制約 (Constraint)

 

    • 変数が満たすべき制約式です。

 

    • 制約式(Predicate)

 

    • 制約式をラムダ式で表現するための関数型インタフェースです。

 

    • 問題解決 (Solver)

 

    • 問題を解きます。

 

    • 解 (Answer)

 

    解が見つかったときに呼び出されるコールバックです。

如果以UML类图表示，将如下所示。

SimpleModel.png

编码

域（Domain）是一个包含不变整数的列表。

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; }
}

变量是一个具有名称和定义域的类。它保存了与该变量相关的所有约束的引用。由于实例的生成是通过问题的工厂方法完成的，因此构造函数具有包作用域。

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）是用于以表达式形式表示约束的函数接口。
只定义了一个test（int …）方法，该方法在所有与约束相关的变量的值被绑定时作为参数调用。
通过使用它，可以使用Lambda表达式表示约束式。

@FunctionalInterface
public interface Predicate {

    boolean test(int... values);

}

制約（Predicate）是一个具有约束式（Predicate）和与约束相关的变量引用的不变类。
由于实例的创建是通过问题（Problem）的工厂方法进行的，因此构造函数具有包范围的可见性。

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 "制約" + variables;
    }
}

问题是一个具有相关变量和约束的类。
变量的定义是通过variable(String, Domain)进行的。
约束的定义是通过constraint(Predicate, Variable…)进行的。
为了简单地表示多个变量之间的约束，有一个方法allDifferent(Variable…)，该方法要求任意两个变量的值都不相同。

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);
        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]);
    }

}

解(Answer)是一个用于接收找到的解的回调函数。
它以变量和值的对作为Map进行接收。
由于实质上是函数接口，因此可以使用Lambda表达式来编写回调函数。

public interface Answer {

    void answer(Map<Variable, Integer> result);

}

问题解决器（Solver）具有一个solve(Problem, Answer)方法，该方法从问题（Problem）中找到解答。

由于变量数量可变，所以无法通过类似于之前所述的嵌套for循环来实现绑定，而是通过递归调用来进行绑定。

重载的solve(Problem, List, Answer)方法可以通过List指定解决问题时的变量绑定顺序。

内部的静态方法constraintOrder(List, List)根据变量绑定顺序来确定可应用的约束（Constraint）顺序。

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);
    }

}

考试

让我们来解决一个简单的实际例子。

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));

结果如下。

{A=1, B=2, C=3}

变量的绑定顺序和约束的应用顺序如下所示。

0: A []
1: B [约束[A, B]]
2: C [约束[A, B, C]]

八皇后

エイト・クイーンはチェスの盤上で8つのクイーンを配置する問題です。クイーンは上下左右斜めの8方向に進むことができますが、他の駒に取られるような位置には配置してはいけません。これは将棋の飛車と角行を合わせた動きと言えます。また、一辺のマスをnとした変形版を「n-クイーン」と呼びます。

n-クイーンパズルでは、n個の変数を定義し、それぞれが異なる値を持ち、斜めにも重ならないように配置する問題として解かれます。ここではnの値が1から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));
    }

}

结果如下。与维基百科的描述相符。

2020-05-19T16:31:06.863 情報 n=1 : answers=1 : elapse=27ms. 
2020-05-19T16:31:06.941 情報 n=2 : answers=0 : elapse=3ms. 
2020-05-19T16:31:06.942 情報 n=3 : answers=0 : elapse=0ms. 
2020-05-19T16:31:06.944 情報 n=4 : answers=2 : elapse=0ms. 
2020-05-19T16:31:06.947 情報 n=5 : answers=10 : elapse=2ms. 
2020-05-19T16:31:06.953 情報 n=6 : answers=4 : elapse=5ms. 
2020-05-19T16:31:06.963 情報 n=7 : answers=40 : elapse=10ms. 
2020-05-19T16:31:06.984 情報 n=8 : answers=92 : elapse=20ms. 
2020-05-19T16:31:07.031 情報 n=9 : answers=352 : elapse=45ms. 
2020-05-19T16:31:07.118 情報 n=10 : answers=724 : elapse=87ms.

匿名数学题

下面我来尝试解答下面的谜题——著名的SEND MORE MONEY。（这道谜题要求为每个字母分配一个数字，使得方程成立。相同的字母要有相同的数字，不同的字母要有不同的数字，首位数字不能为零。）

  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
    public void test単一制約() {
        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()));
    }

事情就是这样了。 .)

{S=9, E=5, N=6, D=7, M=1, O=0, R=8, Y=2}

解决方案只有一个约束条件，所有变量都在约束绑定后进行检查。换句话说，约束检查在最内层循环中进行，因此效率不太高。在我的环境下，需要少于2秒。

如果添加进位变量，并且将约束定义为每个位数，将会稍微提速一些。

    @Test
    public void test桁ごとの制約() {
        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()));
    }

我已经能在大约0.3秒的时间内解决了。

数独可以概括为一种逻辑拼图游戏。

我将尝试解答维基百科上数独页面中的第一个问题。

image.png
    static Logger logger = Logger.getLogger(Test数独.class.toString());

    static int 辺の長さ = 9;
    static int 小四角形の辺の長さ = 3;
    static Domain 定義域 = Domain.rangeClosed(1, 9);

    static String 名前(int r, int c) {
        return r + "@" + c;
    }

    static Variable[][] 変数定義(Problem 問題, int[][] 入力) {
        Variable[][] 変数 = new Variable[辺の長さ][辺の長さ];
        for (int r = 0; r < 辺の長さ; ++r)
            for (int c = 0; c < 辺の長さ; ++c)
                変数[r][c] = 問題.variable(名前(r, c),
                    入力[r][c] == 0 ? 定義域 : Domain.of(入力[r][c]));
        return 変数;
    }

    static List<Variable[]> 制約定義(Problem 問題, Variable[][] 変数) {
        List<Variable[]> 制約変数 = new ArrayList<>();
        for (int r = 0; r < 辺の長さ; ++r)
            制約変数.add(変数[r]);
        for (int c = 0; c < 辺の長さ; ++c) {
            Variable[] va = new Variable[辺の長さ];
            制約変数.add(va);
            for (int r = 0; r < 辺の長さ; ++r)
                va[r] = 変数[r][c];
        }
        for (int r = 0; r < 辺の長さ; r += 小四角形の辺の長さ)
            for (int c = 0; c < 辺の長さ; c += 小四角形の辺の長さ) {
                Variable[] va = new Variable[辺の長さ];
                制約変数.add(va);
                for (int i = 0, p = 0; i < 小四角形の辺の長さ; ++i)
                    for (int j = 0; j < 小四角形の辺の長さ; ++j, ++p)
                        va[p] = 変数[r + i][c + j];
            }
        for (Variable[] va : 制約変数)
            問題.allDifferent(va);
        return 制約変数;
    }

    static void 答(Variable[][] 変数, Map<Variable, Integer> 解答) {
        for (int r = 0; r < 辺の長さ; ++r) {
            StringBuilder sb = new StringBuilder();
            for (int c = 0; c < 辺の長さ; ++c)
                sb.append(String.format("%2d", 解答.get(変数[r][c])));
            logger.info(sb.toString());
        }
    }

    static void 数独束縛順序指定なし(int[][] 入力) {
        Problem 問題 = new Problem();
        Variable[][] 変数 = 変数定義(問題, 入力);
        制約定義(問題, 変数);
        Solver 解決 = new Solver();
        解決.solve(問題, m -> 答(変数, m));
    }

    @Test
    void testWikipedia束縛順序指定なし() {
        // Wikipedia 数独 の例題
        // https://ja.wikipedia.org/wiki/%E6%95%B0%E7%8B%AC
        int[][] 入力 = {
            { 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");
        数独束縛順序指定なし(入力);
    }

暂时解决了，但花了超过20秒的时间。

2020-05-16T21:01:31.789 情報 test wikipedia 
2020-05-16T21:01:52.360 情報  5 3 4 6 7 8 9 1 2 
2020-05-16T21:01:52.361 情報  6 7 2 1 9 5 3 4 8 
2020-05-16T21:01:52.361 情報  1 9 8 3 4 2 5 6 7 
2020-05-16T21:01:52.362 情報  8 5 9 7 6 1 4 2 3 
2020-05-16T21:01:52.363 情報  4 2 6 8 5 3 7 9 1 
2020-05-16T21:01:52.363 情報  7 1 3 9 2 4 8 5 6 
2020-05-16T21:01:52.363 情報  9 6 1 5 3 7 2 8 4 
2020-05-16T21:01:52.364 情報  2 8 7 4 1 9 6 3 5 
2020-05-16T21:01:52.365 情報  3 4 5 2 8 6 1 7 9

变量的绑定顺序简单地从上到下，从左到右，因此我会稍作改变。
我将按照以下策略来定义绑定顺序。

image.png

以下是根据这个方针改变变量绑定顺序的代码。

    static List<Variable> 束縛順序定義(List<Variable> 変数, List<Variable[]> 制約変数) {
        Set<Variable> 束縛順序 = new LinkedHashSet<>();
        for (Variable v : 変数)
            if (v.domain.size() == 1)
                束縛順序.add(v);
        Collections.sort(制約変数,
            Comparator.comparingInt(a -> Arrays.stream(a).mapToInt(v -> v.domain.size()).sum()));
        for (Variable[] a : 制約変数)
            for (Variable v : a)
                束縛順序.add(v);
        return new ArrayList<>(束縛順序);
    }

    static void 数独束縛順序指定あり(int[][] 入力) {
        Problem 問題 = new Problem();
        Variable[][] 変数 = 変数定義(問題, 入力);
        List<Variable[]> 制約変数 = 制約定義(問題, 変数);
        List<Variable> 束縛順序 = 束縛順序定義(問題.variables, 制約変数);
        Solver 解決 = new Solver();
        解決.solve(問題, 束縛順序, m -> 答(変数, m));
    }

结果是在大约0.02秒内解决了。这个例子太简单了，所以我尝试了更困难的问题。根据维基百科，数独的解必须拥有至少17个已知的数字格子才能保证唯一性。
我在网上搜索了一个恰好有17个已知数字的复杂问题。

image.png
    @Test
    void testGood_at_Sudoku_Heres_some_youll_never_complete() {
        // http://theconversation.com/good-at-sudoku-heres-some-youll-never-complete-5234
        int[][] 入力 = {
            { 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");
        数独束縛順序指定あり(入力);
    }

我能在一秒钟内解决这个问题。

2020-05-16T21:22:26.176 情報 Good at Sudoku Heres some youll never complete 
2020-05-16T21:22:26.310 情報  2 6 4 7 1 5 8 3 9 
2020-05-16T21:22:26.311 情報  1 3 7 8 9 2 6 4 5 
2020-05-16T21:22:26.312 情報  5 9 8 4 3 6 2 7 1 
2020-05-16T21:22:26.313 情報  4 2 3 1 7 8 5 9 6 
2020-05-16T21:22:26.315 情報  8 1 6 5 4 9 7 2 3 
2020-05-16T21:22:26.316 情報  7 5 9 6 2 3 4 1 8 
2020-05-16T21:22:26.317 情報  3 7 5 2 8 1 9 6 4 
2020-05-16T21:22:26.318 情報  9 8 2 3 6 4 1 5 7 
2020-05-16T21:22:26.320 情報  6 4 1 9 5 7 3 8 2

如果不指定变量的绑定顺序，即使过了10分钟也得不到解答。

改善限制表达

在定义约束时，需要指定与Lambda表达式相关的变量。由于受约束的变量数量是可变的，因此采用这种写法。

        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);

为了改善这种难以理解的表达方式，我将添加一个固定长度参数的方法。首先，我们要添加以下接口。

@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);

}

.....

接下来，我们将在Problem类中添加一个使用这个约束的工厂方法。

    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);
    }

    .....

如果这样做，就可以实现这样的写法。如果传给constraint()方法的Variable数量与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);

总结

我们已经发现以下因素会影响性能。

    1. 约束条件的设置方式

 

    1. 通过将约束条件细化，可以在变量绑定的早期阶段进行检查，从而缩小选择范围并提高速度。

变量绑定的顺序
首先绑定选择较少的变量可以加快速度。

✖
广告
将在 10 秒后关闭
bannerAds