10パズル作成ソフトウェアの開発

今回は私が好きなパズルの一つである"10パズル"
その問題を生成するソフトウェアの開発に取り組んだことについて書かせていただきます。
内容は以下の通りとなっております。

１．"10パズル"って何？
２．問題生成アルゴリズム
３．完成・まとめ

１．"10パズル"って何？

"10パズル"というパズルをご存知でしょうか？
"数独"や"ナンクロ"等と比べると知名度が低く、ご存じで無い方も多いと思います。
私も日常生活の中で"10パズル"を見かけたのは電車内の広告で一度見た位です。

"10パズル"のルールは非常に単純です。
『用意された複数の数値全てに対し、四則演算を行いその結果を 10 にする』それだけです。
例）6 8 8 9 使用可能な演算子＋－ × ÷ （）
（ 8 － 6 ）× 9 － 8 ＝ 10

この"10パズル"は他のパズルにはない魅力を持っています。
それは適当な数字が複数あればどこでも遊ぶことができる事です、
自動車のナンバープレート、電車の車両番号、現在時刻、
ありとあらゆる複数の数字から問題を作成できるのです。

しかし問題が作成できると言っても限度があり、解無しの問題を作成してしまうこともあります。
例) 1 1 1 1, 8 8 9 9, etc…

私が開発に至ったのはこれを解決し、
大量の問題を供給できるソフトウェアが欲しいと思ったからです。

２．問題生成アルゴリズム

今回考えた生成アルゴリズムを大まかにまとめると以下の通りになります。

Ⅰ．要素数・最小値・最大値から、取りうる全ての組み合わせを求める
Ⅱ．組み合わせに対して全ての計算パターンを当てはめ、解となる値が得られるかを判定する
Ⅲ．解となる値が得られる組み合わせを画面に表示する

この中で一番の曲者がⅡ番の判定式です。
単純な四則演算とはいえ、全てのパターンを導くのは中々骨が折れます。

そこで以下の３パターンの判定アルゴリズムを考えました。

①．計算式のパターンを全て準備し、そこに値を入れて計算する
②．再帰的に値を取り出し、四則演算を行う
③．逆ポーランド記法の式を再帰的に生成し、計算する

①．は非常に不格好です。
ソースコードは増え、要素数の変化に非常に弱く、プログラマとしては許しがたいものです。
一応要素数４に対応したものを作成してみました。
パターンが少ない事もあり簡単に作れ、処理も軽量でした。

②．は単純かつ要素数の変化にも強く、ソースコードも短いものにできます。
直前の値に次の値で四則演算を行う処理を再帰的に行うだけです。
しかしこの方法には前方からしか計算できないという問題があり、
計算順序の変更を行うことができませんでした。
例）本来の計算結果 1 × 2 ＋ 2 × 4 ＝ 10
②．の計算結果 ((( 1 × 2 ) ＋ 2 ) × 4 ) ＝ 16
計算結果が異なっているのは致命的で①．より劣っていると言わざるをえません。

③．は要素数の変化に強く、一見複雑そうに見えますが簡単な処理です。
(ソースコードは同じく再帰を使用する②．と比べ大幅に増えましたが)
基本情報処理技術者試験を受けた方であればご存じでしょう。
「こんな所で使えるなんて、試験を受けていて良かった！」と心から思いました。
解説に戻りますが逆ポーランド記法では（）を使用することなく計算順序を設定することができ、
なおかつ再帰的に処理を行うことができます。
(逆ポーランド記法について詳しく知りたい方は参考書等を読んでいただきたい)
例）一般的な記法 1 × 2 ＋ 2 × 4 ＝ 10
逆ポーランド 1 2 × 2 4 × ＋
1 2 ×
2 2 4 ×
2 8 ＋
10

桁数の変更を行いたかった事、プログラマらしいソースコードを書きたかった事から
今回はⅡ．のアルゴリズムとして③．逆ポーランド記法を採用しました。

残りのⅠ．Ⅲ．は適当に生成しました。

20160315_01
図１）組み合わせを求めるメソッド