10パズルを解いてみた。

数式の列挙問題を考えていてよくある例題として四つの数字と四則演算で１０を作るパズルを考えていた。

Wikipediaによるとこの問題のことを10パズルというらしい。
wikipedia:10パズル

本来やりたかったのは抽象構文木の列挙だったのだが、この問題は逆ポーランド記法を使うと簡単に書けるようだ。
【Ruby】【アルゴリズム】10パズルを解く。全ての数式を逆ポーランドで作る編 - せかいや

この10パズルの問題は大きく分けて３パターンある。一つは自然数の範囲内で解が存在するもの、二つ目は計算過程で有理数が出現してもよいという条件で解が存在するもの、もう一つは有理数を許しても解が存在しないものだ。

HaskellのListモナドを使えばきれいにこれらの制限をパラメータ化できそうなので実際に書いて解析してみた。

gist9562047

ideoneでの実行結果は以下の通り
http://ideone.com/Z9fOnO

1158,1199,1337,3478は自然数の範囲内では解が存在しないが、有理数の範囲では解が存在するという結果だった。それぞれの解は以下の通り




ちなみに自然数を整数に緩めた（引き算のときに負の数が現れてもよいとする）場合でも結果は変わらない。

電車の広告に難問として載っている物はどうせこれらのうちのいずれかなので覚えておくといいかも。