Puzzle DE Programming

はじめに

一般に、数字を使ったパズルは図形や駒などを使ったパズルよりも比較的やさしいので、プログラミング入門用の教材に適しています。まずは「小町数」のパズルから始めましょう。

●小町数と小町算

パズルの世界では、1 から 9 までの数字を 1 個ずつすべて使った数字を「小町数」といいます。たとえば、123456789 とか 321654987 のような数字です。「小町算」というものもあり、たとえば 123+456+789 とか 321 * 654 + 987 のようなものです。

小町数は 1 から 9 までの数字を並べるわけですから、個数は全部で 9! = 362880 個しかありません。現在のように強力なパソコンが使える環境では、総当たりで検索しても短時間で答えを見つけることができるでしょう。

最初に鎌田さんから出題された小町算を解いてみます。

[問題] ○に1～9を1回ずつ入れて式を完成させましょー。

小町分数(1)
○○○○÷○○○○○＝1/2

小町分数(2)
○○○○÷○○○○○＝4/5

小町平方数(1)
○○○^2＝○○○○○○

小町平方数(2)
○○○○○○○○○＝□□□□□^2

問題を提供された鎌田さんに感謝いたします。最初は小町分数 (1) を解きましょう。使用する言語は何でもいいのですが、ここでは Python3 (ver 3.8.10) を使うことにします。興味のある方は、自分の好みの言語でプログラムを書き換えてみてください。プログラミングの勉強になると思います。

●生成検定法

まず最初に「すべての小町数を生成してチェックする」という一番単純な方法を採用します。これを「生成検定法 (genarate and test)」といいます。小町数の場合、1 から 9 までの順列を生成すればいいわけです。これはバックトラックを使えば簡単です。プログラムは次のようになります。

リスト : 順列の生成 (number.py)

def permutation(func, n, xs, ps = []):
    if n == 0:
        func(ps)
    else:
        for x in xs:
            if x not in ps:
                ps.append(x)
                permutation(func, n - 1, xs, ps)
                ps.pop()

関数 permutation() は引数 xs から n 個を選ぶ順列を生成します。xs はイテレータを実装しているオブジェクト (iterable) であれば何でもかまいません。選んだ要素は ps に格納します。ps は Python のリスト (一次元配列) です。

n が 0 であれば、順列が一つ完成しました。関数 func に ps を渡して呼び出します。permutation() は高階関数になっていることに注意してください。そうでなければ、xs から要素 x を一つ選びます。x が ps に無い場合、append() で ps に x を追加して、permutation() を再帰呼び出しします。戻ってきたら、ps から x を pop() で削除します。これですべての順列を生成することができます。

簡単な実行例を示しましょう。

>>> from number import *
>>> permutation(print, 3, range(3))
[0, 1, 2]
[0, 2, 1]
[1, 0, 2]
[1, 2, 0]
[2, 0, 1]
[2, 1, 0]
>>> permutation(print, 3, [1, 3, 5])
[1, 3, 5]
[1, 5, 3]
[3, 1, 5]
[3, 5, 1]
[5, 1, 3]
[5, 3, 1]

次は、生成した小町数が条件を満たしているかチェックする関数を作ります。

リスト : 条件のチェック

# xs を整数に変換
def to_num(xs):
    return functools.reduce(lambda a, b: a * 10 + b, xs, 0)

# 整数 n をリストに分解
def from_num(n):
    if n < 10:
        return [n]
    else:
        return from_num(n // 10) + [n % 10]

# 条件のチェック
def check1(xs):
    m = to_num(xs[:5])
    n = to_num(xs[5:])
    if n * 2 == m:
        print('{:d} / {:d} = 1 / 2'.format(n, m))

問題は 4 桁の数 / 5 桁の数 = 1 / 2 とありますが、ようするに 5 桁の数が 4 桁の数の 2 倍になればいいわけです。生成した小町数は引数 xs に格納されています。これを前半 5 個と後半 4 個の数字に分け、関数 to_num() を使ってリストを整数に変換します。値は変数 m と n にセットします。to_num() はライブラリ functools の関数 reduce() を使うと簡単です。あとは、n * 2 が m と等しければ print() で解を出力するだけです。

解を求める関数 solver1() は次のようになります。

リスト : 小町分数 (1) 

def solver1(check):
    s = time.time()
    permutation(check, 9, range(1, 10))
    print(time.time() - s)

引数 check にはデータをテストする関数を渡します。結果は次のようになりました。

>>> solver1(check1)
6729 / 13458 = 1 / 2
6792 / 13584 = 1 / 2
6927 / 13854 = 1 / 2
7269 / 14538 = 1 / 2
7293 / 14586 = 1 / 2
7329 / 14658 = 1 / 2
7692 / 15384 = 1 / 2
7923 / 15846 = 1 / 2
7932 / 15864 = 1 / 2
9267 / 18534 = 1 / 2
9273 / 18546 = 1 / 2
9327 / 18654 = 1 / 2
1.3460462093353271

実行環境 : Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz

解は全部で 12 通りで、時間は約 1.35 秒かかりました。やっぱり、単純な生成検定法は遅いですね。それでは高速化に挑戦してみましょう。

●高速化にチャレンジ

パズルを生成検定法で解く場合、生成するデータの総数を減らすことができると、実行時間を大幅に短縮することができます。単純に考えると大量のデータを生成しなければならないような問題でも、パズルの特徴や性質を見極めて、データの総数を大幅に減らすように工夫することが大切です。

このパズルでは、与えられた数式から解を満たす数字の範囲を限定することができます。4 桁の数字の最大値は 9876 ですね。これを 2 倍した値 19752 が 5 桁の数字の最大値となります。1 は一番小さな値ですから、数字の 5 桁目は 1 に確定することができます。これだけで生成するデータ数は 1 / 9 となります。

permutation() の引数 xs に [1] を渡すと、1 から始まる順列だけを生成することができます。プログラムと実行結果を示します。

リスト : 高速化 (1)

def solver11(check):
    s = time.time()
    permutation(check, 8, range(2, 10), [1])
    print(time.time() - s)

>>> solver11(check1)
6729 / 13458 = 1 / 2
6792 / 13584 = 1 / 2
6927 / 13854 = 1 / 2
7269 / 14538 = 1 / 2
7293 / 14586 = 1 / 2
7329 / 14658 = 1 / 2
7692 / 15384 = 1 / 2
7923 / 15846 = 1 / 2
7932 / 15864 = 1 / 2
9267 / 18534 = 1 / 2
9273 / 18546 = 1 / 2
9327 / 18654 = 1 / 2
0.1795060634613037

実行時間は約 0.18 秒ですから約 7.5 倍の高速化に成功しました。今回のパズルでは、生成するデータ数を減らすことができましたが、データを生成している途中でチェックを入れることで、無駄なデータをカットする方法もあります。これを「枝刈り」と呼びます。バックトラックを使ってパズルを解く場合、この枝刈りのよしあしによって実行時間が大きく左右されます。パズル固有の性質を良く調べて、適切な枝刈りを考えることが重要になります。

また、小町数を生成してチェックする以外にも方法はあります。たとえば、まず 4 桁の数字を生成し、それを 2 倍して 5 桁の数字を作り、それが小町数となっているかチェックする方法もあります。プログラムは次のようになります。

リスト : 高速化 (2)

# 小町数のチェック
def is_komachi(xs):
    c = 0
    flag = [False] * 10
    for x in xs:
        if x <= 0 or x >= 10 or flag[x]: return False
        flag[x] = True
        c += 1
    return c == 9

def check11(xs):
    n = to_num(xs)
    m = n * 2
    ys = from_num(m)
    if is_komachi(xs + ys):
        print('{:d} / {:d} = 1 / 2'.format(n, m))

def solver2(check):
    s = time.time()
    permutation(check, 4, range(1, 10))
    print(time.time() - s)

関数 is_komahi() は引数 xs に 1 から 9 までの数字が一つずつ格納されているか調べます。重複要素の判定はリスト flag を使います。flag の要素を False に初期化します。flag[x] が False ならば、x はまだ出現していません。flag[x] を True に、個数 c を +1 します。flag[x] が True ならば、x は重複しているので False を返します。最後に、c が 9 ならば 1 から 9 までの数字を一つずつ見つけたので True を返します。

関数 check11() は簡単です。引数 xs には 4 桁の数 (順列) が渡されます。それを to_num() で数値に変換し、2 倍した値を変数 m にセットします。あとは、m をリストに分解して xs と連結し、それを is_komachi() でチェックします。返り値が True ならば小町数なので、print() で解を表示します。関数 solver2() は 1 - 9 の数字から 4 つの数字を選ぶ順列を生成し、check11() でチェックします。

結果は次のようになりました。

>>> solver2(check11)
6729 / 13458 = 1 / 2
6792 / 13584 = 1 / 2
6927 / 13854 = 1 / 2
7269 / 14538 = 1 / 2
7293 / 14586 = 1 / 2
7329 / 14658 = 1 / 2
7692 / 15384 = 1 / 2
7923 / 15846 = 1 / 2
7932 / 15864 = 1 / 2
9267 / 18534 = 1 / 2
9273 / 18546 = 1 / 2
9327 / 18654 = 1 / 2
0.013807058334350586

こちらの方が断然速かったですね。生成する数字は 9 * 8 * 7 * 6 = 3024 個しかないので、当然の結果といえるでしょう。

●小町分数 (2)

次は小町分数 (2) を解いてみましょう。

リスト : 小町分数 (2)

def check2(xs):
    n = to_num(xs)
    if (n * 5) % 4 == 0:
        m = n * 5 // 4
        ys = from_num(m)
        if is_komachi(xs + ys):
            print('{:d} / {:d} = 4 / 5'.format(n, m))

関数 check2() の引数 xs には 4 桁の数 (順列) が渡されます。それを数値に変換して変数 n にセットします。n を 5 倍した数が 4 で割り切れるならば、n * 5 / 4 を変数 m にセットし、from_num() でリストに分解します。あとは、is_komachi() で xs + ys が小町数かチェックするだけです。

>>> solver2(check2)
9876 / 12345 = 4 / 5
0.0059850215911865234

このパズルは、解が 9876 / 12345 の一通りしかなく、数字の並びも面白くて楽しむことができました。ところで、このパズルはプログラムを作らなくても答えを求めることができます。小町分数 (1) のように、数式から解を満たす数字の範囲を限定すると、答えを導くことができます。コンピュータを使わなくても解けるので、一般的な数理パズルとして通用するのではないでしょうか。

●小町平方数

次の問題は小町平方数 (1) です。これは小町分数 (2) のプログラムを少し改造するだけで、簡単に求めることができます。生成する数字は 3 桁なので、実行速度はもっと速くなるでしょう。

リスト : 小町平方数 (1)

def check3(xs):
    n = to_num(xs)
    m = n ** 2
    ys = from_num(m)
    if is_komachi(xs + ys):
        print('{:d} ** 2 = {:d}'.format(n, m))

def solver3(check):
    s = time.time()
    permutation(check, 3, range(1, 10))
    print(time.time() - s)

>>> solver3(check3)
567 ** 2 = 321489
854 ** 2 = 729316
0.0028994083404541016

3 桁の数字は 504 通りしかないので、Python でも一瞬で答えを求めることができます。

次の小町平方数 (2) はちょっとやっかいです。最小値 123456789 の平方根は 11111.1、最大値 987654321 の平方根は 31426.9 です。したがって、11112 から 31426 までの数値を 2 乗して、それが小町数になるかチェックすればいいでしょう。それでも 2 万回近くループするので、Python では時間がかかるかもしれません。

プログラムは繰り返しで OK です。

リスト : 小町平方数 (2)

def solver4():
    s = time.time()
    for x in range(11112, 31427):
        y = x * x
        ys = from_num(y)
        if is_komachi(ys):
            print('{:d} = {:d} ** 2'.format(y, x))
    print(time.time() - s)

とくに難しいところはないですね。実行結果は次のようになりました。

>>> solver4()
139854276 = 11826 ** 2
152843769 = 12363 ** 2
157326849 = 12543 ** 2
215384976 = 14676 ** 2
245893761 = 15681 ** 2
254817369 = 15963 ** 2
326597184 = 18072 ** 2
361874529 = 19023 ** 2
375468129 = 19377 ** 2
382945761 = 19569 ** 2
385297641 = 19629 ** 2
412739856 = 20316 ** 2
523814769 = 22887 ** 2
529874361 = 23019 ** 2
537219684 = 23178 ** 2
549386721 = 23439 ** 2
587432169 = 24237 ** 2
589324176 = 24276 ** 2
597362481 = 24441 ** 2
615387249 = 24807 ** 2
627953481 = 25059 ** 2
653927184 = 25572 ** 2
672935481 = 25941 ** 2
697435281 = 26409 ** 2
714653289 = 26733 ** 2
735982641 = 27129 ** 2
743816529 = 27273 ** 2
842973156 = 29034 ** 2
847159236 = 29106 ** 2
923187456 = 30384 ** 2
0.07938241958618164

解の総数は 30 通りで実行時間は 0.08 秒となりました。Python の場合、while ループや for ループによる繰り返しはちょっと遅くなるのですが、この問題は高速に解くことができました。また、解はもっと少ないと思っていたので意外な結果でした。

●式の値が 100 になる小町算

次は小町算の中でも一番有名なパズルを解いてみましょう。

[問題] 小町算

1 から 9 までの数字を順番に並べ、間に + と - を補って 100 になる式を作ってください。
ただし、1 の先頭に - 符号はつけないことにします。

例 : 1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100

それではプログラムを作りましょう。式は次のように + を '+' に、- を '-' としてリストで表すことにします。

1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 => [1, '+', 2, '+', 3, '-', 4, '+', 5, '+', 6, '+', 78, '+', 9]

あとは、式を生成して値を計算するだけです。次の図を見てください。

[1] => [1 + 2] => [1 + 2 + 3]
               => [1 + 2 - 3]
               => [1 + 23]
    => [1 - 2] => [1 - 2 + 3]
               => [1 - 2 - 3]
               => [1 - 23]
    => [12]    => [12 + 3]
               => [12 - 3]
               => [123]

式を生成するとき、配列に数字と演算子を順番に追加していきます。数字と +, - を追加する処理は簡単です。プログラムのポイントは数字を連結する処理、たとえば 1 と 2 を連結して一つの数値 12 にする処理です。この処理はリストの末尾の数字 1 を 12 (1 * 10 + 2) に置き換えることで実現できます。配列が [1 + 2] であれば、数字 2 を 23 (2 * 10 + 3) に置き換えます。

式を生成するプログラムは次のようになります。

リスト : 式の生成

def make_expr(n, expr):
    if n == 10:
        if calc_expr(expr) == 100:
            print_expr(expr)
    else:
        make_expr(n + 1, expr + ['+', n])
        make_expr(n + 1, expr + ['-', n])
        m = expr[-1]
        expr[-1] = m * 10 + n
        make_expr(n + 1, expr)
        expr[-1] = m

関数 make_expr() の引数 n が追加する数字、expr が生成する式 (リスト) です。n が 10 の場合は、式が完成したので値を計算します。関数 calc_expr() で式 expr を計算します。値が 100 になれば関数 print_expr() で式を出力します。

n が 10 未満であれば、演算子 (+. -) と n を expr に追加して make_expr() を再帰呼び出しします。最後が数字を連結する処理です。この場合、リストを破壊的に修正するので、末尾の数値 expr[-1] を変数 m に保存しておきます。それから、expr[-1] の値を m * 10 + n に書き換えます。これで数字を連結することができます。make_expr() を再帰呼び出しして戻ってきたら末尾の数字を元に戻します。この処理を忘れると正常に動作しません。ご注意くださいませ。

次は式を計算する calc_expr() を作ります。今回の問題は演算子に + と - しかないので、リストで表現した式を計算することは簡単です。次のプログラムを見てください。

リスト：式の計算 (+ と - だけ)

def calc_expr(expr):
    n = expr[0]
    for i in range(1, len(expr), 2):
        if expr[i] == '+':
            n += expr[i + 1]
        else:
            n -= expr[i + 1]
    return n

expr[0] を変数 n にセットします。あとは、for ループの中で expr から演算子を表す文字列 (expr[i]) と数値 (expr[i + 1]) を順番に取り出して計算します。expr[i] が '+' であれば n に expr[i + 1] を加算し、'-' であれば n から expr[i + 1] を減算します。

最後に、make_expr() を呼び出す関数 komachi_solver() を作ります。

リスト : 小町算の解法

def komachi_solver():
    s = time.time()
    make_expr(2, [1])
    print(time.time() - s)

それでは実行結果を示します。

>>> komachi_solver()
1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100
1 + 2 + 34 - 5 + 67 - 8 + 9 = 100
1 + 23 - 4 + 5 + 6 + 78 - 9 = 100
1 + 23 - 4 + 56 + 7 + 8 + 9 = 100
12 + 3 + 4 + 5 - 6 - 7 + 89 = 100
12 + 3 - 4 + 5 + 67 + 8 + 9 = 100
12 - 3 - 4 + 5 - 6 + 7 + 89 = 100
123 + 4 - 5 + 67 - 89 = 100
123 + 45 - 67 + 8 - 9 = 100
123 - 4 - 5 - 6 - 7 + 8 - 9 = 100
123 - 45 - 67 + 89 = 100
0.019505739212036133

解は全部で 11 通りになりました。それでは、数字を逆順に並べたらどうなるでしょうか。

[問題] 逆順の小町算

1 から 9 までの数字を逆順に並べ、間に + と - を補って 100 になる式を作ってください。
ただし、9 の先頭に - 符号はつけないことにします。

例 : 9 - 8 + 7 + 65 - 4 + 32 - 1 = 100

この問題も Python で簡単にプログラムを作ることができます。次のリストを見てください。

リスト : 逆順の小町算

def make_expr_rev(n, expr):
    if n == 0:
        if calc_expr(expr) == 100:
            print_expr(expr)
    else:
        make_expr_rev(n - 1, expr + ['+', n])
        make_expr_rev(n - 1, expr + ['-', n])
        m = expr[-1]
        expr[-1] = m * 10 + n
        make_expr_rev(n - 1, expr)
        expr[-1] = m

def komachi_rev_solver():
    make_expr_rev(8, [9])

関数 make_expr_rev() を再帰呼び出しするとき、引数 n の値を -1 します。これで数字を逆順に並べることができます。そして、n の値が 0 になったら再帰呼び出しを停止して式の値を calc_expr() で計算します。とても簡単ですね。結果は次のようになります。

>>> komachi_rev_solver()
9 + 8 + 76 + 5 + 4 - 3 + 2 - 1 = 100
9 + 8 + 76 + 5 - 4 + 3 + 2 + 1 = 100
9 - 8 + 7 + 65 - 4 + 32 - 1 = 100
9 - 8 + 76 + 54 - 32 + 1 = 100
9 - 8 + 76 - 5 + 4 + 3 + 21 = 100
98 + 7 + 6 - 5 - 4 - 3 + 2 - 1 = 100
98 + 7 - 6 + 5 - 4 + 3 - 2 - 1 = 100
98 + 7 - 6 + 5 - 4 - 3 + 2 + 1 = 100
98 + 7 - 6 - 5 + 4 + 3 - 2 + 1 = 100
98 - 7 + 6 + 5 + 4 - 3 - 2 - 1 = 100
98 - 7 + 6 + 5 - 4 + 3 - 2 + 1 = 100
98 - 7 + 6 - 5 + 4 + 3 + 2 - 1 = 100
98 - 7 - 6 + 5 + 4 + 3 + 2 + 1 = 100
98 - 7 - 6 - 5 - 4 + 3 + 21 = 100
98 - 76 + 54 + 3 + 21 = 100
0.020670175552368164

解は全部で 15 通りあります。

●小町分数 (3)

最後にもうひとつ、小町算のパズルを出題しましょう。

[問題] 小町分数 (3)

○に 1 から 9 までの数字を 1 回ずつ入れて式を完成させてください。

(A) ○○○○○÷○○○○＝６６
(B) ○○○○○○÷○○○＝６３５３

どちらの問題もそれほど難しくありません。(A), (B) ともに、解の候補は 20 個程度に絞り込むことができるので、プログラムを作らなくても解けると思います。ここで絞り込む方法は説明しないので、皆さん考えてみてください。

プログラムと実行結果を示します。

リスト : 小町分数 (3) の解法

def check3a(xs):
    m = to_num(xs)
    n = m * 66
    ys = from_num(n)
    if is_komachi(xs + ys):
        print('{:d} / {:d} = 66'.format(n, m))

def solver3a():
    s = time.time()
    permutation(check3a, 4, range(1, 10))
    print(time.time() - s)

def check3b(xs):
    m = to_num(xs)
    n = m * 6353
    ys = from_num(n)
    if is_komachi(xs + ys):
        print('{:d} / {:d} = 6353'.format(n, m))

def solver3b():
    s = time.time()
    permutation(check3b, 3, range(1, 10))
    print(time.time() - s)

>>> solver3a()
83754 / 1269 = 66
0.016378164291381836
>>> solver3b()
927538 / 146 = 6353
978362 / 154 = 6353
0.0034389495849609375

大町数と大町算

パズルの世界では、1 から 9 までの数字が 1 回ずつすべて登場する数を「小町数」といいますが、これに 0 を加えた数を 「大町数」といいます。そして、0 から 9 までの 10 個の数字を 1 個ずつ使った計算を「大町算」といいます。それでは問題です。

[問題] 大町算

0 から 9 までの数字を逆順に並べ、間に + と - を補って 999 になる式を作ってください。
ただし、9 の先頭に - 符号はつけないことにします。

例 : 9 + 8 + 7 + 654 + 321 +(-) 0 = 999

ちなみに、小町数の場合は 9 + 8 + 7 + 654 + 321 の 1 通りしかありません。この問題も Python を使って簡単にプログラムを作ることができます。次のリストを見てください。

リスト : 大町算

def make_oomachi(n, expr):
    if n == -1:
        if calc_expr(expr) == 999:
            print_expr(expr)
    else:
        make_oomachi(n - 1, expr + ['+', n])
        make_oomachi(n - 1, expr + ['-', n])
        m = expr[-1]
        expr[-1] = m * 10 + n
        make_oomachi(n - 1, expr)
        expr[-1] = m

def oomachi_solver():
    s = time.time()
    make_oomachi(8, [9])
    print(time.time() - s)

関数 make_oomachi() を再帰呼び出しするとき、引数 n の値を -1 します。これで数字を逆順に並べることができます。そして、n の値が -1 になったら再帰呼び出しを停止して式の値を calc_expr() で計算します。とても簡単ですね。

それでは実行してみましょう。

>>> oomachi_solver()
9 + 8 + 7 + 654 + 321 + 0 = 100
9 + 8 + 7 + 654 + 321 - 0 = 100
9 + 8 + 765 + 4 + 3 + 210 = 100
987 + 6 + 5 - 4 - 3 - 2 + 10 = 100
987 + 6 - 5 - 4 + 3 + 2 + 10 = 100
987 - 6 + 5 + 4 - 3 + 2 + 10 = 100
0.04042792320251465

解は全部で 6 通りあります。

それでは次の問題です。

[問題] ３数で大町どうさま

ある連続した３数 (n, n+1, n+2) を掛け合わせたら、大町数になったという。
そのような３数をすべて見つけてほしい。もちろん、負の数は考えない。

出典 : 『Ｃマガ電脳クラブ』 Ｃマガジン 1998 年 2 月号（ソフトバンク）

この問題も Python で簡単にプログラムを作ることができます。最初に整数 n の範囲を絞り込みます。大町数の最大値は 9876543210 で最小値は 1023456789 ですから、n の値は次の範囲内になります。

>>> 1023456789 ** (1/3)
1007.758578449832
>>> 1006 * 1007 * 1008
1021146336
>>> 1007 * 1008 * 1009
1024191504

>>> 9876543210 ** (1/3)
2145.5319657992272
>>> 2145 * 2146 * 2147
9883005990
>>> 2144 * 2145 * 2146
9869196480

x ** y は x の y 乗を返します。これらの計算結果から n は 1007 以上 2144 以下であることがわかります。n の範囲がぐっと狭くなりましたね。これならば、あとは単純に計算して大町数になるかチェックすればいいでしょう。プログラムは次のようになります。

リスト : ３数で大町どうさま

def is_oomachi(xs):
    c = 0
    flag = [False] * 10
    for x in xs:
        if x < 0 or x >= 10 or flag[x]: return False
        flag[x] = True
        c += 1
    return c == 10

def oomachi_solver2():
    s = time.time()
    for n in range(1007, 2145):
        m = n * (n + 1) * (n + 2)
        xs = from_num(m)
        if is_oomachi(xs):
            print('{:d} * {:d} * {:d} = {:d}'.format(n, n + 1, n + 2, m))
    print(time.time() - s)

プログラムは単純な生成検定法です。関数 oomachi_solver2() で 1007 から 2144 までの数 n を生成します。次に、n, n+1, n+2 を掛け算して変数 m にセットし、それを from_num() でリストに分解します。それを関数 is_oomachi() でチェックして、大町数であれば print() で表示します。is_oomachi() は is_komachi() に 0 のチェックを加えるだけなので簡単です。

実行結果を示します。

>>> oomachi_solver2()
1267 * 1268 * 1269 = 2038719564
1332 * 1333 * 1334 = 2368591704
0.005501270294189453

2 通りの解を見つけることができました。

覆面算

計算式の数字を文字や記号に置き換えて、それを元の数字に戻すパズルを「覆面算」といいます。異なる文字は異なる数字を表し、同じ文字は同じ数字を表します。使用する数字は 0 から 9 までで、最上位の桁に 0 を入れることはできません。

それでは問題です。

[問題１] 覆面算

     S E N D
 +   M O R E
-------------
   M O N E Y

[問題２] 小町覆面算

    W R O N G
 *          M
--------------
    R I G H T

SEND + MORE = MONEY はデュードニーが 1924 年に発表したもので、覆面算の古典といわれる有名なパズルです。なお、WRONG * M = RIGHT は使用する数字を 1 から 9 までとします。

問題１の場合、式 SEND + MORE = MONEY は足し算なので、M が 1 であることはすぐにわかります。ここでは、それ以外の数字を求めるプログラムを作ります。単純な生成検定法でプログラムを作ると、次のようになります。

リスト : 覆面算 (1)

# SEND + MORE = MONEY
def check_hukumen(xs):
    o, n, e, y, s, d, r = xs
    send = s * 1000 + e * 100 + n * 10 + d
    more = 1000 + o * 100 + r * 10 + e
    money = 10000 + o * 1000 + n * 100 + e * 10 + y
    if send + more == money:
        print('{:d} + {:d} = {:d}'.format(send, more, money))

def hukumen_solver():
    s = time.time()
    permutation(check_hukumen, 7, [0, 2, 3, 4, 5, 6, 7, 8, 9])
    print(time.time() - s)

1 を除いた 9 個の数字の中から数字を 7 個選ぶ順列を permutation() で生成します。それを関数 check_hukumen() に渡して、条件を満たしているかチェックします。7 個の数字はリスト xs に格納されいて、先頭から順番に o, n, e, y, s, d, r に対応します。あとは send, more, money を計算して、send + more = money を満たしていれば print() で解を表示します。

実行結果を示します。

>>> hukumen_solver()
9567 + 1085 = 10652
0.2995452880859375

答えは 9567 + 1085 = 10652 の 1 通りしかありません。興味のある方はもっとクールな方法を考えてみてください。

次は問題２を解きましょう。単純な生成検定法でプログラムを作ると、次のようになります。

リスト : 覆面算 (2)

# WRONG * M = RIGHT
def check_hukumen2(xs):
    w, r, o, n, g, m, i, h, t = xs
    wrong = w * 10000 + r * 1000 + o * 100 + n * 10 + g
    right = r * 10000 + i * 1000 + g * 100 + h * 10 + t
    if wrong * m == right:
        print('{:d} * {:d} = {:d}'.format(wrong, m, right))

def hukumen_solver2():
    s = time.time()
    permutation(check_hukumen2, 9, range(1, 10))
    print(time.time() - s)

関数 check_hukumen2() の引数 xs には小町数が渡されます。あとは、 wrong と right を求めて、wrong * m = right を満たせば、print() で解を表示します。

実行結果を示します。

>>> hukumen_solver2()
16958 * 4 = 67832
0.9689555168151855

解は一通りしかありません。ところで、wrong と right は同じ桁数なので、w < r が成り立ちます。この条件を使って枝刈りすると、もう少し速くなるかもしれません。興味のある方はプログラムを改良してみてください。

●プログラムリスト

#
# number.py : 数字のパズル
#
#             Copyright (C) 2022 Makoto Hiroi
#
import functools, time

# 順列の生成
def permutation(func, n, xs, ps = []):
    if n == 0:
        func(ps)
    else:
        for x in xs:
            if x not in ps:
                ps.append(x)
                permutation(func, n - 1, xs, ps)
                ps.pop()

# 数値に変換
def to_num(xs):
    return functools.reduce(lambda a, b: a * 10 + b, xs, 0)

# リストに変換
def from_num(n):
    if n < 10:
        return [n]
    else:
        return from_num(n // 10) + [n % 10]

#
# 小町数と小町算
#

# 小町分数 (1)
def check1(xs):
    m = to_num(xs[:5])
    n = to_num(xs[5:])
    if n * 2 == m:
        print('{:d} / {:d} = 1 / 2'.format(n, m))

def solver1(check):
    s = time.time()
    permutation(check, 9, range(1, 10))
    print(time.time() - s)

def solver11(check):
    s = time.time()
    permutation(check, 8, range(2, 10), [1])
    print(time.time() - s)

# 小町数のチェック
def is_komachi(xs):
    c = 0
    flag = [False] * 10
    for x in xs:
        if x <= 0 or x >= 10 or flag[x]: return False
        flag[x] = True
        c += 1
    return c == 9

def check11(xs):
    n = to_num(xs)
    m = n * 2
    ys = from_num(m)
    if is_komachi(xs + ys):
        print('{:d} / {:d} = 1 / 2'.format(n, m))

# 小町分数 (2)
def check2(xs):
    n = to_num(xs)
    if (n * 5) % 4 == 0:
        m = n * 5 // 4
        ys = from_num(m)
        if is_komachi(xs + ys):
            print('{:d} / {:d} = 4 / 5'.format(n, m))

def solver2(check):
    s = time.time()
    permutation(check, 4, range(1, 10))
    print(time.time() - s)

# 小町平方数 (1)
def check3(xs):
    n = to_num(xs)
    m = n ** 2
    ys = from_num(m)
    if is_komachi(xs + ys):
        print('{:d} ** 2 = {:d}'.format(n, m))

def solver3(check):
    s = time.time()
    permutation(check, 3, range(1, 10))
    print(time.time() - s)

# 小町平方数 (2)
def solver4():
    s = time.time()
    for x in range(11112, 31427):
        y = x * x
        ys = from_num(y)
        if is_komachi(ys):
            print('{:d} = {:d} ** 2'.format(y, x))
    print(time.time() - s)

# 小町算
def print_expr(expr):
    for x in expr:
        print(x, end=' ')
    print('= 100')

def calc_expr(expr):
    n = expr[0]
    for i in range(1, len(expr), 2):
        if expr[i] == '+':
            n += expr[i + 1]
        else:
            n -= expr[i + 1]
    return n

def make_expr(n, expr):
    if n == 10:
        if calc_expr(expr) == 100:
            print_expr(expr)
    else:
        make_expr(n + 1, expr + ['+', n])
        make_expr(n + 1, expr + ['-', n])
        m = expr[-1]
        expr[-1] = m * 10 + n
        make_expr(n + 1, expr)
        expr[-1] = m

def komachi_solver():
    s = time.time()
    make_expr(2, [1])
    print(time.time() - s)

# 逆順の小町算
def make_expr_rev(n, expr):
    if n == 0:
        if calc_expr(expr) == 100:
            print_expr(expr)
    else:
        make_expr_rev(n - 1, expr + ['+', n])
        make_expr_rev(n - 1, expr + ['-', n])
        m = expr[-1]
        expr[-1] = m * 10 + n
        make_expr_rev(n - 1, expr)
        expr[-1] = m

def komachi_rev_solver():
    s = time.time()
    make_expr_rev(8, [9])
    print(time.time() - s)

# 小町分数 (A)
def check3a(xs):
    m = to_num(xs)
    n = m * 66
    ys = from_num(n)
    if is_komachi(xs + ys):
        print('{:d} / {:d} = 66'.format(n, m))

def solver3a():
    s = time.time()
    permutation(check3a, 4, range(1, 10))
    print(time.time() - s)

# 小町分数 (B)
def check3b(xs):
    m = to_num(xs)
    n = m * 6353
    ys = from_num(n)
    if is_komachi(xs + ys):
        print('{:d} / {:d} = 6353'.format(n, m))

def solver3b():
    s = time.time()
    permutation(check3b, 3, range(1, 10))
    print(time.time() - s)

#
# 大町数と大町算
#

# 大町算
def make_oomachi(n, expr):
    if n == -1:
        if calc_expr(expr) == 999:
            print_expr(expr)
    else:
        make_oomachi(n - 1, expr + ['+', n])
        make_oomachi(n - 1, expr + ['-', n])
        m = expr[-1]
        expr[-1] = m * 10 + n
        make_oomachi(n - 1, expr)
        expr[-1] = m

def oomachi_solver():
    s = time.time()
    make_oomachi(8, [9])
    print(time.time() - s)

# 大町数のチェック
def is_oomachi(xs):
    c = 0
    flag = [False] * 10
    for x in xs:
        if x < 0 or x >= 10 or flag[x]: return False
        flag[x] = True
        c += 1
    return c == 10

# ３数で大町どうさま
def oomachi_solver2():
    s = time.time()
    for n in range(1007, 2145):
        m = n * (n + 1) * (n + 2)
        xs = from_num(m)
        if is_oomachi(xs):
            print('{:d} * {:d} * {:d} = {:d}'.format(n, n + 1, n + 2, m))
    print(time.time() - s)

#
# 覆面算
#

# SEND + MORE = MONEY
def check_hukumen(xs):
    o, n, e, y, s, d, r = xs
    send = s * 1000 + e * 100 + n * 10 + d
    more = 1000 + o * 100 + r * 10 + e
    money = 10000 + o * 1000 + n * 100 + e * 10 + y
    if send + more == money:
        print('{:d} + {:d} = {:d}'.format(send, more, money))

def hukumen_solver():
    s = time.time()
    permutation(check_hukumen, 7, [0, 2, 3, 4, 5, 6, 7, 8, 9])
    print(time.time() - s)

# WRONG * M = RIGHT
def check_hukumen2(xs):
    w, r, o, n, g, m, i, h, t = xs
    wrong = w * 10000 + r * 1000 + o * 100 + n * 10 + g
    right = r * 10000 + i * 1000 + g * 100 + h * 10 + t
    if wrong * m == right:
        print('{:d} * {:d} = {:d}'.format(wrong, m, right))

def hukumen_solver2():
    s = time.time()
    permutation(check_hukumen2, 9, range(1, 10))
    print(time.time() - s)