アルゴリズム検討（その１）
１．一列分
１－１．黒
ルール1 左詰と右詰の重なり
＜基本＞
初期状態で未だ何も確定していない状況から
最初の数字に対する黒列を左黒詰めで置く。一マス空けて、次の数字に対応する黒列を置く。以下、数字が終わるまで、それを繰り返す。
これで、左詰めのバターが完成。
同様にして、右詰パターンを作成。
その後、左詰パターンと右詰パターンをマス位置毎にａｎｄを取れば完成。
アルゴリズム的に書くと
＜発展＞
既に何か所か、黒、または白の確定がある前提も同様の処置が可能。
この場合、置けるか？の部分をちゃんと実装しないとだめ。
置ける場合の判定として、
・当該のマス目（及び左右１マス）だけをみて判断
・問題として矛盾がないかまで判断
がいるが、後者はちょっと難しいので、まず、前者から。青が置けるパターン、赤が置けないパターン。最後のマス外は、基本確定箇所を間違っていなければ発生しないはず。
置こうとする黒列の範囲内に何もなければ必ず置ける（初期状態）。白があったらダメ、黒はＯＫ。黒列の外側１個目が黒はダメというものです（問題のマス目の外周に接する場合は、そちらは判定不要）。
次に、問題として矛盾がないかは、問題の数列について、すべてを含めて整合性をチェックしないといけないので、どのようなアルゴリズムが良いかは少し考えます。例としては、次のような場合です。3番目の２が赤枠の位置におけるかは、その番号だけに着目すれば置けますが、当然その右方向に黒マスがあるので、そこに置くと問題として矛盾する訳です。
自分で解いているとき、どのように判断しているか整理してみます。
ただ、重なりを考えるとき、問題として矛盾があるものは、重ならないと思われるので、あえてそれを区別する必要は無いかもしれません。
まずは、上記について一旦プログラムとして、検証して行くこととします。
(2021.2.6更新)
フリーのお絵描きロジック問題集より、簡単な10×10の問題を選択。
ルール１を適用して解いてみた結果。
こうなりました。問題枠の下の横長の枠は、アルゴリズムチェック用のもの。
正解と比べても、ほぼ解けている感じです。この問題については、ルール１でもそこそこ行けました。
