最初に申しておきますと、このセクションは、１５パズルの話からは少しはずれたお話をします。
今まで、１５パズルにはパズルが成立する場合と成立しない場合があることを言い、そして成立するかどうかを判定する方法を２種類挙げ、どちらも結果は同じだと言うことを述べました。
率直に聞きます。
転倒数を数える方法と、偶循環を数える方法の、どちらの方が簡単と感じましたか？
多くの人は、後者の方が簡単だと感じたのではないでしょうか。
だって、数字を順番に探していって、１５個並べるだけで、目で見てもよく分かる形で成立判定が出来るのですから。
一方の前者は、ターゲットの数字より値の小さい数字を探すときに見落としがあったり、また合計１４個の数の足し算をすることになるので、計算間違いもしやすいですね。 実は私も、前者の方法は苦手です。
では、誰もがそう思っているのでしょうか？
答えは、ほぼＹＥＳです！
計算量という言葉があります。
あまり難しい話をしたくないので、簡単に説明すると、これは、「ある計算をするのに要する時間の目安」を意味します。
ただしここで言う『計算』は、必ずしも、＋−×÷の「四則演算」のようなものだけではなく、大小の比較や、計算の途中経過の記憶など、全体の計算をする上でかかる『手間』なども考慮に入れて考えたものなのです。
そしてある取り決めに従って、２つの成立判定方法の計算量を各々計算すると、その結果は、前者が大体３７０、後者がその約半分の１３５くらいになります。
これを見ても、後者の判定方法がいかに簡単かが伺えます。
ところが、前者の方法の方がやりやすい、という意見を持っているものもあります。
それは、コンピュータ。
コンピュータは、CPUやその他電気素子がどこもいかれてさえいなければ、常に正しい答えをそれも高速で算出します。
それが、コンピュータが前者の方法が得意な理由の一つです。
今ひとつは、コンピュータは、「単純な動作の繰り返し」が得意だ、ということです。
前者の転倒数を数える方法というのは、まさに、左上から順番に数字を見ていって、一つずつ比較していく、その繰り返しです。コンピュータは、「ループ命令」というものを駆使して、そう言った処理を効率よくこなすことが出来ます。
一方でコンピュータは、その時々によって違うことをしなければいけないような処理というのは、比較的苦手です。
「条件分岐命令」というものも持ち合わせてはいますが、それが複雑なものだと、即ち、条件がたくさんあってその各々に対して別々のことをしなければならないようなときには、その「条件分岐命令」を非常に多用しなくてはならなくなります。そうすると、その時々でいちいち条件を比較するときに、非常に手間がかかってしまうのです。
これは、後者の方法が苦手な最大の理由です。
拙作のJavaアプレット１５パズルでの成立判定処理は、従って前者の方法を採用しています。
でももし、皆様が実際に１５パズルをされるときは、成立するかどうかの判定には後者の方法を強くオススメします！
To be continued...