10パズルとは、与えられた4つの数字に任意の四則演算子及び括弧を加えて10にする、割と有名な遊びである。電車の切符を買うと大抵4桁の通し番号が書いてあるので、高校生の時に友達に教えてもらって以来、切符を買う度によくやっていて、40代の今でも、たまに切符を買うとついやってしまう。
最近、2日連続で、解けそうなのに解けない番号に当たった。6287と5773であった。
気になって気になって、家に帰ってからWebで検索しても答えは見つからず、後日プログラムを作ってやっと発見できた。
今後は電車で長時間もやっとした気分を引きずらなくて済むよう、いつも持ち歩いているDoCoMoのfeature phoneに、プログラムを仕込んでおくことにした。
・10パズルソルバーのダウンロードURL
http://ynomura.dip.jp/java/TenPuzzle/Download.html
・サンプル画像
・使い方
数字ボタンで4桁の数字を入力し、「答えを探す」ボタンを押します。
・補足
このゲームは4桁の数字の余白に＋−×÷（）のいずれかを挿入するだけのものである、という筆者のポリシーにより、数字の並び替えには対応していません。
先頭に「−」を置くことを許すかどうかと、2つの数字を繋げて2桁の数字とするのを許すかどうかは、議論があり（先頭の「−」は四則演算でないことと、4つの数字の演算にこだわるかどうか）、許す方がマイナーな気がしましたので、それぞれをOFFにするチェックボタンを用意しています。
・ソースコードの説明
検査するパターンは、演算子と値のツリーとして作成し、答えが見つかれば数式に変換するようにしている。
数字の連結は、１つの演算の扱いにしている。
数式への変換(TenPuzzleSolver.Node.expression())は、
- 乗除算の左辺が加減算なら左辺は括弧付き
- 乗算の右辺が加減算なら右辺は括弧付き
- 除算の右辺が加減乗除なら右辺は括弧付き（右辺が数字の連結なら括弧不要）
というヒューリスティックな方法で、括弧をなるべく付けないようにしている。
括弧を使うことによりあり得る、演算順序の全パターンの作り方としては、3つの演算子と4つの値を混ぜた7つの要素の順列の内、逆ポーランド記法として成り立つ列、を全パターン生成する方法が知られているが、計算量が大きいので、今回は、3つの演算を行う順番は高々3!=6通りしかないことに着目し、1つ目→3つ目→2つ目と3つ目→1つ目→2つ目は同じ式なので1つ省略して5通りのツリーを作成するコードを、べた書きしている。
途中の計算は、全て分数(class Frac)で行うようにしている。
分子も分母も高々3回の乗算であり、通分しなくてもintに収まらなくなることはないので、通分はしていない。
数字の連結という演算は、加減乗除の後にはできない為、加減乗除済かどうかがわかるよう、加減乗除の後には強制的に分母を2以上にしている。
演算順序が違っても、数式が同じになることが多数あるので、文字列の集合のクラス(class StringSet)を用意し、同じ数式の2つ目以降は無視するようにしている。
単項演算子の「−」は、括弧の前に「−」を付けるパターンもあり得るし、それを許すなら2つ目の数字以降にも「−」を付けても良いことになるが、先頭の数字の直前の「−」以外にを付ける以外の式には全て同じ意味の代替の式があり（-(A+B) = -A-B、A+(-B) = A-B、-(A×B) = -A×B）、省略してもそれによって解無しにはならないので、省略している。
先頭の数字に「−」を付けるパターンの検索は、単に先頭の数字を(-1)倍してやり直すようにしている(TenPuzzleSolver.findAnswers())。
・6287と5773の答え
6+28/7 = 10
(62+8)/7 = 10
-5*(7/7-3) = 10
コメント