×

[PR]この広告は3ヶ月以上更新がないため表示されています。
ホームページを更新後24時間以内に表示されなくなります。

小町リング

以下のような5つの円に1-9までの数を入れ、どの円の中も合計すると同じ数になるように、数を埋めるというパズルです。左右の円は2つの合計、それ以外は3つの合計です。

「小町リング」というのは、僕が勝手に命名したものです。本当の名前はわかりません。

小町リング

このパズルを、手計算でやろうとすると、解を一だけ見つけるのも結構大変だと思います。興味のある方はチャレンジしてください。

これを、プログラムで求めようというわけですが、単に1から9までの順列をすべて求めて、それぞれの合計を求めるのが一番手っ取り早いのですが、ここでは、順列を求めている途中で、条件にあっているかどうかを調べ、枝刈りを行っています。これにより効率的に解を求めることができるようになります。

以下、作成したプログラムです。実際に動かして解を知ることができます。[Solve]ボタンを押してください。



■コードの簡易解説
このプログラムの中心的な部分が、Solverクラスの_Solveメソッドです。
このメソッドでは、1~9までの順列を求めながら、条件にあっているかどうかを調べています。
順列の求め方は、「すべての順列を求める」で示した方法ではなく、もっと素人っぽいやり方を取っています。numsというリストを用意し、そこに 数を追加する際に、すでに入っている数ならば除外し、入っていなければ追加する。numの要素数が 9 になったら、一つの順列が求まったので、IsRightメソッドを呼び出し、条件に一致しているかどうかを調べています。
いちいちリストの中にあるかどうかを調べているので効率は悪いですが、その効率の悪さをカバーしているのが、枝刈りです。
IsRightメソッドはnumsに数が途中まで入っている状態でも、調べるこどができるようになっています。
例えば、1,2,3,4まで求まれば、1+2 ≠ 2+3+4 で条件を満たさないことが分かるので、5桁目以降は調べる必要はありません。
for文の直前に行っている IsRightメソッドによる判断がこれに当たります。

GUI部では、この結果を IEnumerableで受け取ります。これから IEnumeratorオブジェクトを取り出し、Nextボタンで、次の解を表示できるようにしています。

なお、鏡像的解は除いていませんので、これを除こうとすると、もう少し工夫が必要です。

以下に、C#+Silverlightのコードを示します。


■KomachiRing.cs

■MainPage.xaml.cs
  
■MainPage.xaml