使用 Groovy 和约束编程（Choco、JaCoP 和 OR-Tools）解决数独谜题

for (s in 1..9)
  for (e in 0..9)
    for (n in 0..9)
      for (d in 0..9)
        for (m in 1..9)
          for (o in 0..9)
            for (r in 0..9)
              for (y in 0..9)
                if ([s, e, n, d, m, o, r, y].toSet().size() == 8) {
                  def send = 1000 * s + 100 * e + 10 * n + d
                  def more = 1000 * m + 100 * o + 10 * r + e
                  def money = 10000 * m + 1000 * o + 100 * n + 10 * e + y
                  if (send + more == money) {
                    println "s = $s, e = $e, n = $n, d = $d"
                    println "m = $m, o = $o, r = $r, y = $y"
                  }
                }

def digits = 0..9
for (p in digits.permutations()) {
    if (p[-1] < p[-2]) continue
    def (s, e, n, d, m, o, r, y) = p
    if (s == 0 || m == 0) continue
    def send = 1000 * s + 100 * e + 10 * n + d
    def more = 1000 * m + 100 * o + 10 * r + e
    def money = 10000 * m + 1000 * o + 100 * n + 10 * e + y
    if (send + more == money) {
        println "s = $s, e = $e, n = $n, d = $d"
        println "m = $m, o = $o, r = $r, y = $y"
    }
}

s = 9, e = 5, n = 6, d = 7
m = 1, o = 0, r = 8, y = 2

new Model("SEND+MORE=MONEY").with {
    def (S, M) = ['S', 'M'].collect { intVar(it, 1, 9) }
    def (E, N, D, O, R, Y) = ['E', 'N', 'D', 'O', 'R', 'Y'].collect { intVar(it, 0, 9) }

    allDifferent(S, E, N, D, M, O, R, Y).post()

    IntVar[] ALL = [
            S, E, N, D,
            M, O, R, E,
         M, O, N, E, Y ]
    int[] COEFFS = [
            1000,  100,  10,  1,
            1000,  100,  10,  1,
   -10000, -1000, -100, -10, -1 ]

    scalar(ALL, COEFFS, "=", 0).post()

    println solver.findSolution()
}

def store = new Store()
def (S, M) = ['S', 'M'].collect { new IntVar(store, it, 1, 9) }
def (E, N, D, O, R, Y) = ['E', 'N', 'D', 'O', 'R', 'Y'].collect { new IntVar(store, it, 0, 9) }
var ctr = new Alldifferent(S, E, N, D, M, O, R, Y)
store.impose(ctr)

IntVar[] ALL = [
                S,   E,   N,   D,
                M,   O,   R,   E,
           M,   O,   N,   E,   Y ]
int[] COEFFS = [
             1000,  100,  10,  1,
             1000,  100,  10,  1,
    -10000, -1000, -100, -10, -1 ]
var lin = new LinearInt(ALL, COEFFS, "==", 0)
store.impose(lin)

var label = new DepthFirstSearch()
var select = new InputOrderSelect(store, ALL, new IndomainMin())
label.labeling(store, select)

Labeling has finished with return value of true
DFS1: DFS([S = 9, E = 5, N = 6, D = 7, M = 1, O = 0, R = 8, Y = 2], InputOrder, (org.jacop.search.IndomainMin@45394b31))

Loader.loadNativeLibraries()

new Solver('Send+More=Money').with {
    def s = makeIntVar(1, 9, 's')
    def e = makeIntVar(0, 9, 'e')
    def n = makeIntVar(0, 9, 'n')
    def d = makeIntVar(0, 9, 'd')
    def m = makeIntVar(1, 9, 'm')
    def o = makeIntVar(0, 9, 'o')
    def r = makeIntVar(0, 9, 'r')
    def y = makeIntVar(0, 9, 'y')

    IntVar[] all = [s, e, n, d, m, o, r, y]
    IntVar[] scalar = [s, e, n, d, m, o, r, e, m, o, n, e, y]
    int[] coeffs = [
                 1000,  100,  10,  1,  //  S E N D +
                 1000,  100,  10,  1,  //  M O R E =
        -10000, -1000, -100, -10, -1   //  M O N E Y
    ]

    addConstraint(makeScalProdEquality(scalar, coeffs, 0))
    addConstraint(makeAllDifferent(all))

    def db = makePhase(all, INT_VAR_DEFAULT, INT_VALUE_DEFAULT)
    newSearch(db)
    while (nextSolution()) {
        println all.join(' ')
    }
    endSearch()

    // Statistics
    println "Solutions: ${solutions()}"
    println "Failures: ${failures()}"
    println "Branches: ${branches()}"
    println "Wall time: ${wallTime()}ms"
}

s(9) e(5) n(6) d(7) m(1) o(0) r(8) y(2)
Solutions: 1
Failures: 5
Branches: 10
Wall time: 60ms

import javax.constraints.*

ProblemFactory.newProblem('SEND+MORE=MONEY').with {
    def (S, M) = ['S', 'M'].collect { variable(it, 1, 9) }
    def (E, N, D, O, R, Y) = ['E', 'N', 'D', 'O', 'R', 'Y'].collect { variable(it, 0, 9) }

    postAllDifferent(S, E, N, D, M, O, R, Y)

    Var[] ALL = [
            S, E, N, D,
            M, O, R, E,
            M, O, N, E, Y]
    int[] COEFFS = [
            1000, 100, 10, 1,
            1000, 100, 10, 1,
            -10000, -1000, -100, -10, -1]

    post(COEFFS, ALL, '=', 0)

    def solver = getSolver()
    def solution = solver.findSolution()
    println solution ?: 'No solution'
    solver.logStats()
}

Solution #1:
 S[9] M[1] E[5] N[6] D[7] O[0] R[8] Y[2]

new Model("ABCD*4=DCBA").with {
    def (A, D) = ['A', 'D'].collect { intVar(it, 1, 9) }
    def (B, C) = ['B', 'C'].collect { intVar(it, 0, 9) }
    def R = (0..2).collect { intVar(0, 9) }

    allDifferent(A, B, C, D).post()
    R[2].add(A.mul(4)).eq(D).post()
    R[1].add(B.mul(4)).eq(C.add(R[2].mul(10))).post()
    R[0].add(C.mul(4)).eq(B.add(R[1].mul(10))).post()
    D.mul(4).eq(A.add(R[0].mul(10))).post()
    solver.findAllSolutions().each {
        println "$name: ${pretty(it, [A, B, C, D, ' * 4 = ', D, C, B, A])}\n$it\n"
    }
}

new Model("AA+BB+CC=ABC").with {
    def (A, B, C) = ['A', 'B', 'C'].collect { intVar(it, 1, 9) }
    allDifferent(A, B, C).post()
    A.mul(11).add(B.mul(11).add(C.mul(11))).eq(A.mul(100).add(B.mul(10)).add(C)).post()
    solver.findAllSolutions().each {
        println "$name: ${pretty(it, [A, A, ' + ', B, B, ' + ', C, C, ' = ', A, B, C])}\n$it\n"
    }
}

new Model("HALF+HALF=WHOLE").with {
    def (H, W) = ['H', 'W'].collect { intVar(it, 1, 9) }
    def (A, E, F, L, O) = ['A', 'E', 'F', 'L', 'O'].collect { intVar(it, 0, 9) }
    allDifferent(H, W, A, E, F, L, O).post()
    IntVar[] ALL = [
            H, A, L, F,
            W, H, O, L, E]
    int[] COEFFS = [
            2000, 200, 20, 2,
            -10000, -1000, -100, -10, -1]
    scalar(ALL, COEFFS, "=", 0).post()
    solver.findAllSolutions().each {
        println "$name: ${pretty(it, [H, A, L, F, ' + ', H, A, L, F, ' = ', W, H, O, L, E])}\n$it\n"
    }
}

new Model("HALF+FIFTH+TENTH+TENTH+TENTH=WHOLE").with {
    def (H, F, T, W) = ['H', 'F', 'T', 'W'].collect { intVar(it, 1, 9) }
    def (A, L, I, E, N, O) = ['A', 'L', 'I', 'E', 'N', 'O'].collect { intVar(it, 0, 9) }
    allDifferent(H, F, T, W, A, L, I, E, N, O).post()
    IntVar[] ALL = [
            H, A, L, F,
            F, I, F, T, H,
            T, E, N, T, H,
            T, E, N, T, H,
            T, E, N, T, H,
            W, H, O, L, E]
    int[] COEFFS = [
            1000, 100, 10, 1,
            10000, 1000, 100, 10, 1,
            10000, 1000, 100, 10, 1,
            10000, 1000, 100, 10, 1,
            10000, 1000, 100, 10, 1,
            -10000, -1000, -100, -10, -1]
    scalar(ALL, COEFFS, "=", 0).post()
    solver.findAllSolutions().each {
        def parts = [H, A, L, F, '+', F, I, F, T, H, '+', T, E, N, T, H, '+',
                     T, E, N, T, H, '+', T, E, N, T, H, '=', W, H, O, L, E]
        println "$name: ${pretty(it, parts)}\n$it\n"
    }
}

// helper method to print solutions
def pretty(model, parts) {
    parts.collect { p -> p instanceof IntVar ? model.getIntVal(p) : p }.join()
}

ABCD*4=DCBA: 2178 * 4 = 8712
Solution: A=2, D=8, B=1, C=7, IV_1=3, IV_2=3, IV_3=0, (A*4)=8, sum_exp_4=8, (B*4)=4, …,

AA+BB+CC=ABC: 11 + 99 + 88 = 198
Solution: A=1, B=9, C=8, (A*11)=11, (B*11)=99, (C*11)=88, …,

HALF+HALF=WHOLE: 9604 + 9604 = 19208
Solution: H=9, W=1, A=6, E=8, F=4, L=0, O=2,

HALF+HALF=WHOLE: 9703 + 9703 = 19406
Solution: H=9, W=1, A=7, E=6, F=3, L=0, O=4,

HALF+HALF=WHOLE: 9802 + 9802 = 19604
Solution: H=9, W=1, A=8, E=4, F=2, L=0, O=6,

HALF+FIFTH+TENTH+TENTH+TENTH=WHOLE: 6701+14126+25326+25326+25326=96805
Solution: H=6, F=1, T=2, W=9, A=7, L=0, I=4, E=5, N=3, O=8,