×

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

ナイト(騎士)の最適配置問題

チェスのナイト(騎士)を以下の規則に従って配置するパズルです。

1.すべての空きがどれかのナイトの効き筋になっていること。
      複数のナイトから効いていてもかまわない。
2. ナイト同士は互いに効き筋にはない。
3. なるべく少ない数のナイトで配置する。

この3つの規則を満たすように、ナイトを配置します。

この手の他のパズルと同様、バックトラックを使って探索します。
どうやって、探索数を減らすのかが、高速化の決め手になると思いますが、
なかなか手ごわい問題で、すぐに答えが見つかるようなコードを書くことができませんでした。

探索開始ボタンを押すと、パズルの解答を求められますが、
僕のPCだと、1分10秒ほどかかってしまいます。まあ、答えが出るまで気長に待ってください。



どんなふうに求めているかと言うと、チェス盤を4×4の4つのブロックに区切って探索しています。
ひとつのブロックには、最大でも4つのKnightを配置すれば条件を満たせるはずです。
なぜなら、ひとつのブロックに対し、以下のように配置すれば条件を満たせるからです。



かつ、隅の4つの箇所は、他のブロックに置いたナイトからは届かない場所ですから、
一つのブロックで4つのナイトを配置した時に、隅の4つが効き筋でもなく、ナイトも置いていなかったら、
条件を満たさないことになります。これで枝刈りを行っています。

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

※このプログラムは、そのほかのプログラムでも利用している Board, BoardCanvasクラスを利用しています。Board, BoardCanvasクラスのソースコードはこちらに掲載しています。

■ArrangeKnight.cs
  

■MainPage.xaml.cs


■MainPage.xaml