古典的な覆面算「もっと金送れ（SEND MORE MONEY）」を解きたいです。

 SEND
+MORE
-----
MONEY

これは、同じアルファベットには同じ数字を、異なるアルファベットには異なる数字を当てはめて、この筆算を成立させましょうというパズルです。たとえば「S=1 E=2 N=3 D=4 M=5 O=6 R=7 Y=8」とすると、

 1234
+5672
-----
56328

となって、これは成立しません。お金は送ってもらえませんでした。

解かせ方

さて、Scala から Google OR-Tools を呼びだして、このパズルを解かせてみましょう。まずアルファベットに対応する変数を用意します。

val dict = "SENDMOREMONEY".toCharArray.toSet[Char]
             .map(c => (c, solver.makeIntVar(0, 9, c.toString))).toMap

アルファベットは全て異なる数字であるという制約をかけます。

solver.addConstraint(solver.makeAllDifferent(dict.values.toArray))

そして「SEND + MORE = MONEY」の制約をかけます。

  val send = dict('S') * 1000 + dict('E') * 100 + dict('N') * 10 + dict('D')
  val more = dict('M') * 1000 + dict('O') * 100 + dict('R') * 10 + dict('E')
  val money = dict('M') * 10000 + dict('O') * 1000 + dict('N') * 100 + dict('E') * 10 + dict('Y')
  solver.addConstraint(send + more === money)

さてさて Google OR-Tools が出す答は？？？

6851 + 0738 = 07589
6853 + 0728 = 07581
5849 + 0638 = 06487
3821 + 0468 = 04289
3829 + 0458 = 04287
2819 + 0368 = 03187
2817 + 0368 = 03185
5732 + 0647 = 06379
5731 + 0647 = 06378
3712 + 0467 = 04179
3719 + 0457 = 04176
7643 + 0826 = 08469
7649 + 0816 = 08465
9567 + 1085 = 10652
8542 + 0915 = 09457
7534 + 0825 = 08359
7531 + 0825 = 08356
7539 + 0815 = 08354
6524 + 0735 = 07259
8432 + 0914 = 09346
7429 + 0814 = 08243
6415 + 0734 = 07149
6419 + 0724 = 07143
8324 + 0913 = 09237
7316 + 0823 = 08139

おやおや、いっぱい答が出ててしまいました。~~いっぱいお金も送ってもらえますね！~~

これは一番上の桁には 0 を入れてはならないというルールを忘れていたからでした。気を取りなおして、

solver.addConstraint(dict('S') !== 0)
solver.addConstraint(dict('M') !== 0)

さてさて？

9567 + 1085 = 10652

はい、上手に解けました。

コード一式

Google OR-Tools の環境構築手順は『巨大お絵かきロジックを最適化ソルバーで瞬殺（ネタバレあり）』を参照してください。

src/main/scala/SendMoreMoney.scala

object SendMoreMoney extends App {
  System.loadLibrary("jniortools")

  implicit val solver: Solver = new Solver("")

  val dict = "SENDMOREMONEY".toCharArray.toSet[Char]
               .map(c => (c, solver.makeIntVar(0, 9, c.toString))).toMap

  solver.addConstraint(solver.makeAllDifferent(dict.values.toArray))
  solver.addConstraint(dict('S') !== 0)
  solver.addConstraint(dict('M') !== 0)
  val send = dict('S') * 1000 + dict('E') * 100 + dict('N') * 10 + dict('D')
  val more = dict('M') * 1000 + dict('O') * 100 + dict('R') * 10 + dict('E')
  val money = dict('M') * 10000 + dict('O') * 1000 + dict('N') * 100 + dict('E') * 10 + dict('Y')
  solver.addConstraint(send + more === money)
  solver.newSearch(solver.makePhase(dict.values.toArray,
    Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MAX_VALUE))

  while (solver.nextSolution()) {
    println(
      "SEND".toCharArray.map(dict).map(_.value()).mkString("") + " + " +
        "MORE".toCharArray.map(dict).map(_.value()).mkString("") + " = " +
        "MONEY".toCharArray.map(dict).map(_.value()).mkString(""))
  }

  implicit class IntExprHelper(i: IntExpr)(implicit solver: Solver) {
    def +(j: IntExpr): IntExpr = solver.makeSum(i, j)
    def *(j: Long): IntExpr = solver.makeProd(i, j)
    def ===(j: IntExpr): Constraint = solver.makeEquality(i, j)
    def !==(j: Long): Constraint = solver.makeNonEquality(i, j)
  }
}

build.sbt

name := "send-more-money"
version := "0.1.0"
javacOptions ++= Seq("-source", "11", "-target", "11")
scalaVersion := "2.13.0"

fork := true
javaOptions += "-Djava.library.path=lib"

Google OR-Toolsで「もっと金送れ」

解かせ方

コード一式