アルゴリズム検討(その2)
1.一列分
1-2.黒
ルール2 一番端が黒の場合
<基本>
左端が黒の場合、最初の数字に対応する黒マスとそれに続く白マス1つが確定します。右端も左右ひっくり返せば同じです。
<応用>
端の定義として、問題マスの一番左とするのが基本になりますが、左端から確定した黒マスと白マスの連続の最後の白マスの一コマ隣、としても構いません。文章で書くと分からずらいですが、下図を見てもらえば分かると思います。
この場合、確定している黒のパターンと問題の数列をマッチングさせ、"端"に相当するのがどの数字になるか見つける必要があります。結局、数列とマス目を端から一つずつ照合して行くしか手はありません。
更に、白マスの連続は条件緩和が出来て、次に来る黒マスの長さ-1までは空白があっても良いです。理由はそこには何もはまらないからです。(白マスで埋めるルールが先に適用されていれば、白マスになっている場合もあり)
以上を、少しアルゴリズム的にとして整理すると
- 最初の数値について、長さ-1までの空白を許容して、連続の白マスを探索 空白マスの最後は白マスである必要があり。
- 黒マスがあったらそこから黒マスを埋め、最後に白マスを置く。(すでに、黒マスが置いてあっても、問題の数列とのマッチングのため、再び置くとする)
- 最後に置いた白マスの位置から、次の数値に対して同じことを繰り返す。
- 白マスが途切れるか、白マスのあとが黒マスで無くなるか、で終わり。
もう少し、アルゴリズムとしてまとめたあと、プログラム化して、検証して行くこととします。
(2021.2.6PM更新)
白マスの条件緩和は入っていませんがプログラム実装していみました。
お絵描きロジックパズル解法プログラムを作る#2と同じ例題を解いてみました。まだ、白マス確定のアルゴリズムを入れていませんが、問題としては解けました。
ちなみに、白マスの条件緩和ですが、白マス確定のルールを設定すれば、いずれは白マスで埋まることになるので、個々のルールをあまり複雑にしないという意味では、このままで良いのかもしれません。
次は、白マス確定のルールを考えていきます。