1
//! The two ways to give Z3 an `allDifferent`.
2
//!
3
//! Both rules sit in the `Smt` rule set at the same priority, so they are equally applicable to any
4
//! `allDifferent` and the heuristic picks between them: `-h i` asks, `-h x` enumerates both, and
5
//! `-h c`/`-h f` take the first. Whichever wins rewrites the expression, so the choice is recorded
6
//! in the model and is not asked again on the next visit.
7
//!
8
//! `distinct` is usually the better of the two, but not always -- Z3 sometimes does better with the
9
//! counting encoding, which is why this is a choice rather than a fixed lowering.
10

            
11
use conjure_cp::ast::matrix::safe_index_optimised;
12
use conjure_cp::ast::{
13
    AbstractLiteral, Expression as Expr, GroundDomain, Metadata, Moo, SymbolTable,
14
};
15
use conjure_cp::essence_expr;
16
use conjure_cp::rule_engine::{
17
    ApplicationError::{DomainError, RuleNotApplicable},
18
    ApplicationResult, RuleEffect, register_rule,
19
};
20

            
21
/// Hand `allDifferent` to Z3 as its native `distinct`.
22
#[register_rule("Smt", 4000, [AllDiff])]
23
1239
fn alldiff_as_smt_distinct(expr: &Expr, _: &SymbolTable) -> ApplicationResult {
24
1239
    let Expr::AllDiff(_, m) = expr else {
25
21
        return Err(RuleNotApplicable);
26
    };
27
1218
    Ok(RuleEffect::pure(Expr::SmtDistinct(
28
1218
        Metadata::new(),
29
1218
        m.clone(),
30
1218
    )))
31
1239
}
32

            
33
/// Encode `allDifferent` as "no value occurs more than once" instead of using `distinct`.
34
#[register_rule("Smt", 4000, [AllDiff])]
35
1239
fn unwrap_alldiff(expr: &Expr, _: &SymbolTable) -> ApplicationResult {
36
1239
    let Expr::AllDiff(_, m) = expr else {
37
21
        return Err(RuleNotApplicable);
38
    };
39

            
40
1218
    let dom = m.domain_of().ok_or(RuleNotApplicable)?;
41
    let Ok(GroundDomain::Matrix(val_domain, index_domains, _)) =
42
1218
        dom.resolve().map(Moo::unwrap_or_clone)
43
    else {
44
        return Err(RuleNotApplicable);
45
    };
46
1218
    let [idx_domain] = index_domains.as_slice() else {
47
        return Err(DomainError);
48
    };
49

            
50
    // Counting occurrences means enumerating the element domain and testing each entry against
51
    // every value in it. That only reads as `allDifferent` when the entries are scalars: for a
52
    // matrix of matrices the "values" are whole rows, and the encoding would compare a row against
53
    // whatever the chosen layout left each entry as. `distinct` handles those natively.
54
1218
    if !matches!(
55
1218
        val_domain.as_ref(),
56
1218
        GroundDomain::Bool | GroundDomain::Int(_, _)
57
1218
    ) {
58
        return Err(RuleNotApplicable);
59
1218
    }
60

            
61
1218
    let val_iter = val_domain.values().map_err(|_| DomainError)?;
62
1218
    let clauses = val_iter
63
6587
        .map(|lit| {
64
6587
            let idx_iter = idx_domain.values().map_err(|_| DomainError)?;
65
6447
            let occurences = idx_iter
66
40649
                .map(|idx| {
67
40649
                    let elem = safe_index_optimised(m.as_ref().clone(), idx).ok_or(DomainError)?;
68
40649
                    Ok(essence_expr!("toInt(&elem = &lit)"))
69
40649
                })
70
                .collect::<Result<Vec<_>, _>>()?;
71
6447
            let occurences_list = Expr::AbstractLiteral(
72
6447
                Metadata::new(),
73
6447
                AbstractLiteral::matrix_implied_indices(occurences),
74
6447
            );
75
6447
            Ok(essence_expr!("sum(&occurences_list) <= 1"))
76
6587
        })
77
140
        .collect::<Result<Vec<_>, _>>()?;
78
1078
    let clauses_list = Expr::AbstractLiteral(
79
1078
        Metadata::new(),
80
1078
        AbstractLiteral::matrix_implied_indices(clauses),
81
1078
    );
82

            
83
1078
    Ok(RuleEffect::pure(essence_expr!("and(&clauses_list)")))
84
1239
}