アルゴリズム検討(その3)
1.一列分
2-1.白確定
ルール3 黒マスのパターンが問題数列とマッチングする場合
<基本>
連続する黒マスの列が、問題の数列と完全一致する。この場合は、楽です。空白マスは、全て白マスで確定です。
アルゴリズムとしてはいくつか考えられます学習、ルール1の発展で、左詰めのパターンと右詰めパターンを作ったあと、この2つのパターンがマス毎に全部一致することを判定すれば良い。
<発展>
黒マスの列の左右を白マスで確定する場合、これは、バリエーションが多いです。
1)問題の数列の最大のものと黒マスの数が同じ場合
a)最大のものが1個のとき
その黒マスの両端は、白で確定
b)最大のものが2個以上の時
それでも、同様に黒マスの両端は黒で確定。ただし、問題の数列のどちらにマッチングするかは、これだけでは判別出来ない。
2)黒マスの数が、問題数列の数より少ない場合
a)問題の数列が1個
黒マスの列を含む様に問題の数だけ黒マスを置いた時に、黒マスとなる可能性の無いところは、白マス確定。
と、ここまで考えて、黒マスは必ずしも連続でなくても、黒列が包含出来ればよいことに気づく。とすると、条件判断として、最初に黒マスの数を判定するのは意味がないことになる。
では、最初に判断するのは、問題の数字の数となるか。その場合、数字が2個になった途端、場合分けが多数。
上の条件の続きで、”b)問題の数列の2番目に大きいものより黒マスの数学が大きい”という条件も考えようしたが、止まってしまった。
あらゆる組み合わせで成立するルールを考えると、結局置いて見て矛盾がないかを確認することになるのでは無いかと思う。この”矛盾がないか”というのは、書くのは簡単だがアルゴリズムにするには、かなり難しい。
さて、どうしたものか、、、、
(2021.2.14更新)
なかなか良い考えが浮かばないので、まずは、絶対いる基本パターンについで、プログラムを実装しました。
黒マスの連続する数を数え、問題の数列と一致しているかを判定することにしました。ルール1では、確定黒マスと矛盾の無いパターンを生成するところが実装できていなかったので、完全なものになっていなかったので、断念です。
このサンプルでは、一応、空白マスがなく、全てが確定しました。
(2021.2.20更新)
発展形について、限定的ですが実装してみました。ルール4のところで使ったサンプルを用いて解いてい見ましたが、やはり、全部は解けませんでした。