×

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

パズルMagic Starを解く

マジックスター(MagicStar)というパズルをC#で解くプログラムを書いてみました。

マジックスターは、下の図の12 個ある○に 1 から 12 までの数字をひとつずつ入れていき、
直線上の4個の数字の合計が、すべて 26 になるように、数字を配置するというものです。

このパズル、手で解くとなると、結構難しく、頭を悩ませることになるのですが、上のプログラムを
実行していただければわかる通り、解が想像以上に多いのにびっくりされると思います。
すべての解を求めるとなると、よっぽど根気のある人でないと無理なんじゃないかと思います。

でも、コンピュータで解かせれば、すべての解をあっという間に求めることができます。
もちろん、プログラミングにはそれなりの時間がかかりますが。。。。

このパズルは12個の数値を扱うので、解が入る要素12の配列を用意し、そこに数値を入れていきます。
このプログラムでは、下の図のように、配列のインデックスと○の位置の対応付けをしています。

このページの最後に、ソースコードを載せていますが、MagicStarsSolverクラスのSolveメソッドで、
private の _Solveメソッドを呼び出しています。
この_Solveメソッドがバックトラックの手法を使って、パズルを解いています。
引数には、○にまだおかれていない数値のリストを渡します。

_Solveメソッドでは、空いている○に引数で与えられたリストの中の数値を置き、
解の条件に合致しているかを調べ、合致していたら、リストからその数値を取り除き、
_Solveメソッドを再起呼び出しします。
合致していなかたら、空いている○に数値をおかずに、メソッドを抜けます。

これを再帰的に繰り返すことで、解を求めています。

なお、回転や鏡像を排除するためにちょっと工夫をしています。
詳しくはソースコードを見てください。

このMagicStarパズルの解き方についてもっと詳しく知りたい方は、
こちらのページ(言語はC言語ですが)がとても参考になると思います。
http://www.geocities.jp/m_hiroi/puzzle/puzdoc02.html

以下、C#+Silverlightのコードです。


■MagicStarSolver .cs


■MainPage.xaml.cs


■MainPage.xaml