« VMWareでのFreeBSD 9.3のX Window環境セットアップ | メイン | 男性不妊因子の治療 »

 10パズルを解くiアプリ作成

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にするチェックボタンを用意しています。

ソースコードの説明
検査するパターンは、演算子と値のツリーとして作成し、答えが見つかれば数式に変換するようにしている。
数字の連結は、1つの演算の扱いにしている。
数式への変換(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

トラックバック

このエントリーのトラックバックURL:
http://ynomura.dip.jp/cgi-bin/mt/mt-tb.cgi/221

コメント投稿フォーム

※投稿されたコメントはオーナーが承認するまで表示されません。


Powered by Movable Type 3.35