拡張テンパズル

YoutubeのQuizKnockを見ていて、面白い問題を人間とコンピュータ（のプログラムを作る人間）が勝負していました。動画はもちろん面白かったのですが、このパズルを解くプログラムを自分でも作ってみたくなりました。

このパズルは例えば次のようなものです。

数字1, 2, 3, 4, 5と四則演算（加減乗除のこと）をつかい、その式の計算結果が20になるような式を見つけよ。

答えは複数ある可能性がありますが、ひとつ見つければ良いことにします。例えば、

$3\times 5-1+2+4=20$

はひとつの答になっています。

このパズルは有名なのでしょうか？またその呼び名はあるのでしょうか？ネットを探してみると、「テンパズル」または「メイクテン」というのが、これに似ています。

ただし、テンパズルは与えられる一桁の数字が4個で、計算結果は10に固定されています。計算結果が10ということが「テン」パズル、あるいはマイク「テン」の元になっているようです。

このパズルの条件を拡張します。

これをここでは「拡張テンパズル」と呼ぶことにします。拡張テンパズルを解くプログラムをRubyで作ってみました。 GitHubにすでにアップロードしてあります。

(9/29 追記）

このレポジトリのプログラム全体が大きく変更されました。そのため、以下の記事とレポジトリの説明文書が異なる部分があります。その場合は、レポジトリ内の文書の方が正しいです。また、変更後のプログラムはgem形式になっていて、requireするときは、ライブラリ全体を対象に行います。

require 'math_programs'

下記のプログラムのrequire_relative文は、このように置き換えるなどしてみてください。

（追記　終わり）

プログラム名の「e10p.rb」がextended TenPuzzleからきています。このプログラムはライブラリであり、メインプログラムを作る必要があります。 demo.rbがそのような例になっているので、参考にしてください。

プログラムを実行するためのメインプログラムの例を示します。

require_relative "e10p.rb"

numbers = ARGV.dup.map{|s| s.to_i}
sum = numbers.pop
puzzle = E10P.new(numbers, sum)
print "#{puzzle.solve}\n"

これを実行するときに、引数に「式に使う数字」と「合計」を空白区切りで指定します。例えば、式に使う数字が11, 20, 33で、合計が42とすると、

$ ruby main_program.rb 11 20 33 42
33-(11-20)

このように答えが表示されます。

テンパズルもやってみましょう。

$ ruby main_program.rb 2 3 5 8 10
5*(8-2*3)

面白いのは、分数が一度出てくるような例があることです。

$ ruby main_program.rb 1 1 9 9 10
9*(1+1/9)

例　2,4,5,6から10を作る

答えの一例は

$5\times(2\times 4-6)$

です。これは木構造で表すと

  *
 / \
5   -
   / \
  *   6
 / \
2   4

となります。一番下の階層は2*4になっています。この結果は8ですが、これから、この問題は、8と5, 6の3つで10になる計算を見つければ良いことになります。もちろん、最初から2と4を組み合わせれば良いことは分かりませんから、4つの数字から2個をとる順列を生成し、虱潰しに探していきます。

数字がひとつ減ったので、今と同じ方法を用いると、次は数字が2つになります。このようにして数字を減らしていって、計算結果が10になる場合を見つければ良いことになります。これは、再帰呼出しです。

GitHubのプログラムでは、solve_realというメソッドがそれに当たります。

この問題はプログラム化が結構難しいと思いますが、Rubyのクラスを導入して木構造を作ると短くまとめることができます。