数学パズル: SEND MORE MONEY

SEND + MORE = MONEY は有名な覆面算パズルです。各文字に10進数の数字を割り当てて、以下の等式を成り立たせます。 $\text{SEND}+\text{MORE}=\text{MONEY}$

制約条件は以下の通りです:

各文字に割り当てられる数字はすべて異なる。
S と M は 0 であってはならない。

定式化

各文字に以下のように一意のインデックスを割り当てます:

index	0	1	2	3	4	5	6	7
letter	S	E	N	D	M	O	R	Y

$I(\alpha)$ を文字 $\alpha$ ($\in \lbrace S,E,N,D,M,O,R,Y\rbrace$) のインデックスとします。 $8\times 10$ のバイナリ行列 $X=(x_{i,j})$ $(0\leq i\leq 7, 0\leq j\leq 9)$ を用いて、各文字に割り当てられた数字を表現します。文字 $\alpha$ に数字 $j$ が割り当てられている場合に限り $x_{I(\alpha),j}=1$ とします。

One-hot制約（各文字はちょうど1つの数字を取る）

$X$ の各行はone-hotでなければなりません。この等式を qbpp.cons() で制約として宣言します。等式制約のエネルギーは違反量の2乗なので、$\text{onehot}$ の値は次のとおりです:

\[\begin{aligned} \text{onehot} &=\sum_{i=0}^{7}\Bigl(\sum_{j=0}^{9}x_{i,j}=1\Bigr) \\ &=\sum_{i=0}^{7}\Bigl(1-\sum_{j=0}^{9}x_{i,j}\Bigr)^2 \end{aligned}\]

$\text{onehot}$ の値は、すべての行がone-hotである場合に限り最小値0になります。

All-different制約（異なる文字は同じ数字を共有しない）

数字は文字間で異なる必要があります。つまり、2つの行が同じ列を選んではなりません: $\begin{aligned} \text{different} &=\sum_{0\leq i<j\leq 7}\sum_{k=0}^9x_{i,k}x_{j,k} \end{aligned}$

単語の線形式による表現

$\text{SEND}$、$\text{MORE}$、$\text{MONEY}$ の値は以下のように表現されます:

\[\begin{aligned} \text{SEND} &= 1000\sum_{k=0}^9 kx_{I(S),k}+ 100\sum_{k=0}^9 kx_{I(E),k}+ 10\sum_{k=0}^9 kx_{I(N),k}+\sum_{k=0}^9 kx_{I(D),k}\\ &= \sum_{k=0}^9k(1000x_{I(S),k}+100x_{I(E),k}+10x_{I(N),k}+x_{I(D),k})\\ \text{MORE} &= 1000\sum_{k=0}^9 kx_{I(M),k}+ 100\sum_{k=0}^9 kx_{I(O),k}+ 10\sum_{k=0}^9 kx_{I(R),k}+\sum_{k=0}^9 kx_{I(E),k}\\ &= \sum_{k=0}^9k(1000x_{I(M),k}+100x_{I(O),k}+10x_{I(R),k}+x_{I(E),k})\\ \text{MONEY} &= 10000\sum_{k=0}^9 kx_{I(M),k}+1000\sum_{k=0}^9 kx_{I(O),k}+ 100\sum_{k=0}^9 kx_{I(N),k}+ 10\sum_{k=0}^9 kx_{I(E),k}+\sum_{k=0}^9 kx_{I(Y),k}\\ &= \sum_{k=0}^9k(10000x_{I(M),k}+ 1000x_{I(O),k}+100x_{I(N),k}+10x_{I(E),k}+x_{I(Y),k}) \end{aligned}\]

等式制約

等式を qbpp.cons() で制約として宣言します。そのエネルギーは残差の2乗です:

\[\begin{aligned} \text{equal} &= \Bigl(\text{SEND}+\text{MORE} = \text{MONEY}\Bigr) \\ &= \Bigl(\text{SEND}+\text{MORE} - \text{MONEY}\Bigr)^2 \end{aligned}\]

統合目的関数

すべての制約を1つの目的関数にまとめます:

\[\begin{aligned} f & = P\cdot (\text{onehot}+\text{different})+\text{equal} \end{aligned}\]

ここで P は、実行可能性（onehot と different）を優先させるための重みです。 3 つの項はどれも非負で、それぞれの制約が成り立つときにちょうど 0 になります。そのため、$f$ は $\text{onehot}=\text{different}=\text{equal}=0$ のときにだけ最小値 0 をとり、$P=1$ でもその解はすべての制約を満たします。ただし、ヒューリスティックなソルバーでは、P を大きくして実行可能性を優先させたほうが解を見つけやすいことが多いので、プログラムでは P = 10000 としています。

最後に、$\text{S}$ と $\text{M}$ は 0 であってはならないため、バイナリ変数を以下のように固定します: $x_{I(S),0} = x_{I(M),0}= 0$

SEND+MORE=MONEY の PyQBPP プログラム

以下の PyQBPP プログラムは上記の定式化を実装し、EasySolver を用いて解を求めます:

import pyqbpp as qbpp

LETTERS = "SENDMORY"
L = len(LETTERS)

def I(c):
    return LETTERS.index(c)

K = qbpp.array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])

x = qbpp.var("x", shape=(L, 10))

onehot = qbpp.cons(qbpp.vector_sum(x) == 1)

different = 0
for i in range(L - 1):
    for j in range(i + 1, L):
        different += qbpp.sum(x[i] * x[j])

send = qbpp.sum((1000 * x[I('S')] + 100 * x[I('E')] + 10 * x[I('N')] + x[I('D')]) * K)
more = qbpp.sum((1000 * x[I('M')] + 100 * x[I('O')] + 10 * x[I('R')] + x[I('E')]) * K)
money = qbpp.sum((10000 * x[I('M')] + 1000 * x[I('O')] + 100 * x[I('N')] + 10 * x[I('E')] + x[I('Y')]) * K)

equal = qbpp.cons(send + more - money == 0)

P = 10000
f = P * (onehot + different) + equal
f.simplify_as_binary()

ml = {x[I('S')][0]: 0, x[I('M')][0]: 0}
g = qbpp.replace(f, ml)
g.simplify_as_binary()

solver = qbpp.EasySolver(g)
sol = solver.search(target_energy=0)

full_sol = qbpp.Sol(f).set(sol, ml)

print(f"onehot = {full_sol(onehot)}")
print(f"different = {full_sol(different)}")
print(f"equal = {full_sol(equal)}")

val = qbpp.onehot_to_int(full_sol(x))

def digit_str(d):
    return "*" if d < 0 else str(d)

print("SEND + MORE = MONEY")
print(f"{digit_str(val[I('S')])}{digit_str(val[I('E')])}{digit_str(val[I('N')])}{digit_str(val[I('D')])} + "
      f"{digit_str(val[I('M')])}{digit_str(val[I('O')])}{digit_str(val[I('R')])}{digit_str(val[I('E')])} = "
      f"{digit_str(val[I('M')])}{digit_str(val[I('O')])}{digit_str(val[I('N')])}{digit_str(val[I('E')])}{digit_str(val[I('Y')])}")

このプログラムでは、LETTERS が "SENDMORY" の各文字に整数インデックスを割り当て、$I(\alpha)$ を実装しています。 L$\times$10 のバイナリ変数行列 x を定義します（ここで $L=8$）。 K は 0 から 9 までの整数の配列で、send・more・money は、x の行に桁の重みを掛けて足した配列と K の要素ごとの積を qbpp.sum() で合計して作ります。 onehot と equal は qbpp.cons() で宣言した制約、different はペナルティ式で、重み P とともに1つの式 f にまとめられます。

辞書 ml を使って x[I('S')][0] と x[I('M')][0] を 0 に固定し、この置換を適用して縮約された式 g を作成します。ソルバーは g に対して実行され、得られた割り当て sol は固定値 ml と qbpp.Sol(f).set(sol, ml) によって統合され、元の目的関数 f に対する full_sol が生成されます。

最後に、qbpp.onehot_to_int(full_sol(x)) がone-hot行を数字に変換し（ちょうど1つの1を含まない行は -1）、プログラムは得られた解を出力します。

このプログラムは以下の出力を生成します:

onehot = 0
different = 0
equal = 0
SEND + MORE = MONEY
9567 + 1085 = 10652

すべての制約が満たされ、正しい解が得られたことが確認できます。