テンパズルを解く

先日、仕事帰りの電車の車内広告に、「9999 の数字から 10 を作ってみよう」という問題が載っていました。いわゆるテンパズルです。昔は電車の切符でよく遊んだものですが、Suica の導入で終わってしまいましたね。

そんなわけで、懐かしく思ったので久しぶりにチャレンジしてみました。PHP で実装したプログラムを github に置いてあります。
ten_puzzle.php

実行結果はこのようになります。

$ php ten_puzzle.php >ten_puzzle_result.txt
$ head -n 5 ten_puzzle_result.txt
(((0 + 0) + 1) + 9)
((0 + 0) + (1 + 9))
((0 + (0 + 1)) + 9)
(0 + ((0 + 1) + 9))
(0 + (0 + (1 + 9)))

Wikipedia の説明 (下記リンクを参照) によると、数字の並び替えを許可するのが一般的なルールだということです。私の実装では並び替えを考慮していないので、それぞれ別の解として出力します。また、上の出力例からもわかるように、加算や乗算の結合法則も考慮していないので、これも、それぞれ別の解として出力されます。この条件で、0000 から 9999 までのすべての数字、すべての四則演算の組み合わせ、すべての括弧の付け方に対して、36,545 通りの解が得られました。
テンパズル - Wikipedia

さて、この出力結果を集計して、出題の 4 桁の数字ごとに、そこから 10 を作る方法が何通りあるのかを計算してみたいと思います。まず、以下のような awk スクリプトを作成して、それぞれの解にインデックスを付けます。数字の並び替えについては、ここで考慮することにしました。

#!/bin/gawk -f

{
    str = $0;
    gsub(/[^0-9]*/, " ", str);
    split(str, arr, " ");
    asort(arr);
    print arr[1], arr[2], arr[3], arr[4], $0;
}

このスクリプトを通したものは以下のようになります。各行の計算に使われている 4 桁の数字が追加されます。

$ ./add_index_to_result.awk ten_puzzle_result.txt >ten_puzzle_result_with_index.txt
$ head -n 5 ten_puzzle_result_with_index.txt
0 0 1 9 (((0 + 0) + 1) + 9)
0 0 1 9 ((0 + 0) + (1 + 9))
0 0 1 9 ((0 + (0 + 1)) + 9)
0 0 1 9 (0 + ((0 + 1) + 9))
0 0 1 9 (0 + (0 + (1 + 9)))

これをソートして uniq -c で行数をカウントします。計算方法の少ない順に 30 行を出力させてみると、次のような結果になりました。

$ cut -f1-4 -d' ' ten_puzzle_result_with_index.txt | sort | uniq -c | sort -ns | head -n 30 | column -c 80
      1 1 1 5 8       2 2 6 6 6       2 3 5 7 7       2 7 7 7 8       3 4 8 8 8
      2 1 1 1 6       2 3 3 3 3       2 3 5 8 8       2 7 8 9 9       3 5 8 8 9
      2 1 1 4 9       2 3 3 5 7       2 4 4 6 6       2 8 8 8 8       3 6 6 7 8
      2 1 1 6 7       2 3 3 6 6       2 4 4 6 7       2 8 9 9 9       3 6 7 7 9
      2 1 1 8 9       2 3 3 7 7       2 4 5 5 9       2 9 9 9 9       4 1 1 1 4
      2 2 2 8 9       2 3 4 7 8       2 5 5 5 7       3 1 2 7 7       4 1 1 6 8

0000 から 9999 までの全ての問題のなかで、解が一通りしか存在しないのは 1158 だけという結果になりました*1。1158 はテンパズルでも有名な問題のようですね。Google で「テンパズル」と入力したところキーワードの候補に出てきました。解答は敢えて載せないでおきますので、挑戦してみてはいかがでしょうか。

*1:前述のように、今回の実装では結合則や交換則を適用すれば同じ式になるものも別解としているので、それを考慮すれば、解が一通りしか存在しない問題は他にもあります。