×

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

ハイパークィーン問題

ずいぶん昔の雑誌Quarkに載っていたパズルです。

チェスのクィーンは、縦横斜めすべての方向に動けます。将棋の飛車と角を合わせた動き方ができます。このパズルでは、さらに、盤の左と右をくるっと回してくっつけてクィーンが動けると仮定します。同様に、上と下もくるっとまわしてくっつけ、クィーンが動けると仮定します。

このとき、7×7の盤上に、お互いに利き筋にあたらないように7つのクィーンを配置してください。という問題です。

Solveボタンを押せば、解を求め、7つのクィーンが配置されます。
ここでは、鏡像や回転像も含めて求めています。


ここでも使うのは、バックトラック法です。7つのクィーンを置けるすべてのパターンについて、条件を満たしているかどうかを調べるとしたらものすごい数(アバウトですみません)の配置パターンについて調べないといけません。

そのため、ここでは、1行目にひとつの駒を置いたら、次は、2行目に条件を満たすようにおき、次に、3行目も条件を満たすように駒を置く... とこれを7行目まで続けることで解を求めています。

もちろん、途中で条件に合わない場合がでてきますので、その際はひとつ前に状態を戻し、さらに探索を続けることをやります。

ソースは、最後に載せますが、主要なクラスは、HyperQeenクラスと、MyBoardクラスです。HyperQueenクラスはパズルを解くクラスであり、その時に、MyBoardクラスに駒を置きながらパズルを解いていきます。
なお、BoardCanvasクラスは、MyBoardクラスの状態を、画面への表示を担当しています。

このプログラムで利用している Board, BoardCanvasクラスは、他のプログラムでも利用できるよう
ある程度汎用性を持たせています。Board, BoardCanvasクラスのソースコードはこちらに掲載しています。

以下に、C#+Silverlightのコードを示します。
どなたか興味があるかたは、鏡像や回転像を含めないように改善してください。



■HyperQuenn.cs


■MainPage.xaml.cs
 

■MainPage.xaml