×

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

[パズル]Less Than Three - 2色の石を規則に沿って置いてゆく

問題

6×6の格子点上に、黒石12個、白石12個を置いていきます。
このとき、格子点上を繋ぐ直線上(縦、横、斜め)に3個以上の石を置いてはいけません。
この時の斜めの直線は、以下に示すような、45度の斜め線以外の直線も考慮に入れます。

 

ここでは、このパズルの名前を(Less Than Three)と名付けました。
この問題の解き方ですが、まず、横方向だけに注目して考えて見ることにします。どの直線にも3個以上置いてはいけないのですから、必ず横一列(1行) に2個ずつ置いていく必要があります。そうしないと12個の石を置くことができません。

2つの石を横一列(1行)のどこの置くかは、6個の要素からから2個を取り出す組み合わせとなりますね。
なので、まずは組み合わせを求めるCombinationというクラスを定義します。 組み合わせを求める方法は、「組合せ」 でも示しましたが、ここでは、アルゴリズムを若干変えています。
今見直してみると、ここで示したアプローチの方が素直なコードかなと思います。(ソースコードは後述)

このCombinationクラスで得られた結果を元に、石を横一列ごとに2つずつ置いていきます。 その際、石を置いた点を通る8つの直線すべてで、同じ色の石が2つ以内かを調べ、すべてが2つ以内ならば、次の行に石を置いていきます。
同じ色の石が3つ以上の直線があれば、失敗なのでバックトラックします。

6行すべてに石を置き終わったら、同じように白石を1行目、2行目、3行目...と石を置いていき、 最後の行まで行けば、解が求まったことになります。
解が求まった時点で、その解をプリントしています。

ひとつの解が求まっても終わりとせず、すべての解を求めています。 ただし、回転、鏡像などは、除外していません。

なお、このプログラムは、.NET Framework4.0で導入された IObserver / IObservable インターフェース を利用しています。

Solverクラスには、解が見つかったことを通知する機能を持たせるため、発行者クラスと位置付けます。そのため、IObservable<T>を実装しています。 ジェネリックの型パラメータTは、オブザーバーへの通知情報を示すクラスであり、解の状態を保持しているMyBoardクラスとしています。

IObservable<T>の具象クラスが実装すべきメソッドは、Subscribeです。 Subscribe メソッドは、オブザーバー・オブジェクト(通知を受け取るオブジェク ト)を受け取り、オブザーバーを登録します。
複数のオブザーバーを登録可能にするために、Listコレクションクラスでオブザ ーバーを保持します。
解が見つかったときに、OnNextメソッドを呼び出し、購読者クラス(IObserver)に、解が見つかったことを知らせます。

購読者クラスは、ResultViewer クラスで、IObserver<MyBoard> を実装しています。 OnNextメソッドで、MyBoard.Printを呼び出し、結果をコンソールに出力しています。 以下 C#のコードを示します。

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

 

■Combination.cs


■MyBoard.cs


■Solver.cs


■Program.cs

 

最後に、実行結果を示します。# が黒石、○が白石です。