複数の解き方を考えて実装してみよう！ #パズルのアルゴリズム問題

前回（定番のアルゴリズムは退屈？アルゴリズムをもっと楽しく学ぼう！）はアルゴリズムを楽しく学ぶために、パズルを解くことを提案しました。また、サンプルとして魔方陣を解くプログラムを作ることを考えました。実際に解けなかった方も、ぜひ以下の解き方を参考にして、自分で実装してみてください。

このとき、コピー＆ペーストするのではなく、キーボードを叩いて入力することが大切です。入力ミスによりうまく動かない場合もあると思いますが、これを一つずつ解決することがスキルアップにも繋がります。できれば自分の得意な言語だけでなく、新たに取り組みたい言語で挑戦してみるのも良いでしょう。

先月の問題の解答例

【先月の問題】
3×3の魔方陣は1〜9までを一つずつ配置したものですが、n〜n+8を配置したものを求めるプログラムを作成してください。例えば、n=1の時は上記の例、n=2の時は以下のような例が生成できます。
ここで、nは1以上10以下の整数とします。

この問題をとりあえず解くだけであれば、単純に全探索する方法が考えられます。左上から右下に向けて、n〜n+8の数を順に当てはめ、同じ数を使わずに各行、各列、対角線のいずれも和が一致すれば求められます。

ただ、少し考えると処理に時間がかかりそうです。すべてのマスについて、9通りを試すと、9の9乗で387,420,489通り、つまり3億通り以上を試すことになります。

もう少し工夫して、一度使った数は使わないようにしてみると、左上は9通りですが、次は8通り、その次は7通り、というように減っていきます。この場合、9×8×7×…×1＝362,880通りです。これならなんとか解けそうです。

図のように左上を「a」、その隣を「b」、…、としてプログラムを実装してみます。

Rubyを使って以下のように実装すると、数秒で求められました。

順列を求める関数が用意されているRubyのような言語の場合は、ライブラリを使って同じ処理をシンプルに書くこともできます。

数学的に考えてみる

もう少し工夫できないか考えてみます。魔方陣では使う数が決まっているため、一列の合計は事前に計算できます。縦、横、対角線の数の和が同じ値になることから、この和をXとします。

横方向に各行の和を考えると、a+b+c=X、d+e+f=X、g+h+i=Xです。この両辺を合計すると、a+b+c+d+e+f+g+h+i=3Xとなります。ここで、a〜iにはn〜n+8が一つずつ入るため、Xはn〜n+8の和を3で割ったものです。

今度は中央の数eを求めてみます。縦、横、対角線の和を考えると、b+e+h=X、d+e+f=X、a+e+i=X、c+e+g=Xです。この両辺を合計すると、a+b+c+d+4e+f+g+h+i=4Xとなります。ここで、a+b+c+d+e+f+g+h+i=3Xだったことを使用すると、3e=Xとなります。つまり、一列の合計は中央の数の３倍になっていることがわかります。

このように、問題文のnが決まると、一列の合計や中央の数が計算で求められることに気づきます。

合計を使って探索範囲を絞る

合計がわかると、2マスが決まると残り1マスは自動的に決まります。例えば、一行目を考えたとき、aとbが決まると、合計からcを計算できます。これを他の行や列、対角線にも使うと、aとbの2箇所を決めるだけで、他の場所に入る数は以下のように自動的に決まります。

(1) eはnが決まると計算できる
(2) aとbを決める
(3) aとbからcが決まる
(4) cとeからgが決まる
(5) aとgからdが決まる
(6) dとeからfが決まる
(7) bとeからhが決まる
(8) aとeからiが決まる

つまり、考える必要があるのはaとbだけです。このため、aとbの9×8=72通りを調べるだけで求められることがわかります。ただし、使う数はn〜n+8の間で、同じ数を複数回使うことがないように、チェックする必要があります。

これを実装すると、以下のように書けます。

他の結果を活用する

もう一つの考え方として、他のnにおける結果を活用する、という考え方もあります。すでにn=1のときの結果が問題文で与えられているため、これを利用してみます。それぞれのマスに入る値にそれぞれ1を加算しても、縦、横、対角線の和はそれぞれ3ずつ増えるだけで、合計はいずれも同じ値のはずです。

つまり、n=1のときの値を使えば、その他も簡単に求められます。

ただ、和が等しくなる配置が他に存在しないか、確認しなければなりません。しかし、もし他の配置が存在すれば、すべてのマスから同じ値を足したり引いたりしたものも成立するはずです。n=1のときに存在しない配置は、他に存在しないということがいえますので、上記の内容で問題ありません。

今回のポイント

全探索すると求められる問題でも、探索範囲を絞り込むことで、圧倒的に高速に処理できることがわかりました。今回の場合、単純に全探索すると処理に時間がかかりますし、実装も複雑になります。

一方で、事前に規則性に着目し、数学的に考えておいたことで、プログラムもシンプルになり、高速な処理を実現できました。さらに、既存のデータを使ってもっとシンプルに実装する方法についても考えました。

このように、複数の解き方を考えられるのもプログラミングの醍醐味です。答えは同じでも、さまざまな解き方を考えることで、より効率良い解き方、実装を導けるかもしれません。

最初のうちは自分では思い付かないかもしれません。でも、他の人の解き方を読んでみると、新しい発見があるかもしれません。その発想を次に問題を解くときに活かせればスキルアップしたと言えるでしょう。

今月の問題

この連載では、毎月1回問題を出題し、次回にその解答や解説、アルゴリズムの紹介を行います。問題を解く速さを競うわけではありませんが、解いた方は自由にオリジナルの解答を公開していただいて構いません。

【今月の問題】
こどもの頃に階段でよく遊んだゲームを考えます。じゃんけんして、勝った手によって進む段数が異なるゲームで、グーで勝ったときは「グリコ」、チョキで勝ったときは「チョコレート」、パーで勝ったときは「パイナップル」と言いながら進みます（それぞれ3段、6段、6段進む）。
AさんとBさんの2人がこのゲームをします。整数m, nが与えられたとき、３m段の階段で、じゃんけんをn回行います。じゃんけんに勝ったほうが進むことを繰り返したとき、Aさんが先にゴールに到達するようなそれぞれの出す手が何通りあるか求めるプログラムを作成してください。

なお、じゃんけんがn回未満でもAさんが先にゴールした場合や、Aさんがゴールの段数を超えた場合もカウントします。あいこの場合は2人とも進みません。m, nはともに1以上10以下の整数とします。
例えば、m=5, n=3のとき、次の20通りがあります。

（著者プロフィール）

WRITING：増井敏克（マスイトシカツ）

増井技術士事務所　代表。技術士（情報工学部門）、テクニカルエンジニア（ネットワーク、情報セキュリティ）、その他情報処理技術者試験に多数合格。また、ビジネス数学検定1級に合格し、公益財団法人日本数学検定協会認定トレーナーとしても活動。「ビジネス」×「数学」×「IT」を組み合わせ、コンピュータを「正しく」「効率よく」使うためのスキルアップ支援を行っている。著書に『エンジニアが生き残るためのテクノロジーの授業』『おうちで学べるセキュリティのきほん』『プログラマ脳を鍛える数学パズル』『もっとプログラマ脳を鍛える数学パズル』『図解まるわかりセキュリティのしくみ』（翔泳社）、『プログラミング言語図鑑』『シゴトに役立つデータ分析・統計のトリセツ』（ソシム）がある。