ぬりかべのグラフ理論的な2
いろいろ間違っていたので修正しました。
黒マス側でも適用してみました。
今回は、次の問題で考えていきます。(作者:Kuchiwo様)
https://puzsq.logicpuzzle.app/puzzle/124227
1:頂点数における制約
前回の記事と同じように考えていきましょう。黒マスの塊が占める頂点数は
黒マスのペナルティ数(黒マス2x2、市松、ループ)
黒マスの数
で決まります。ここで黒マスの数は(盤面-ヒント数字の合計)で確定します。
ただし、黒マス2x2はルール上発生しません
今回だと、黒マス数は81-32=49で、市松は5、ループは0なので、黒マスが占有する頂点数は2x(1+49)-5-2x0=95となります。
今回の盤面では、外周も含めた頂点数は100個なので100-95=5が黒マスが一切関与しない頂点、つまり(白マス2x2の数+外周の黒マスが触れない頂点数)となります。これが一つ目の制約です。
2:ヒント数の制約
これは新しい考え方です。ヒント数による制約を求めていきます。
とはいえコレもシンプルで
ヒント数=黒マスのループ数+外周に接している白マスを含むヒント数+市松の数
となります。
なぜコレが成り立つかというと、外側を完全に黒マスで埋め尽くした状況を考えるとわかります。
こうすると、ループ数は斜めにひと繋がりの白マスの塊に対応していることがわかり、市松はその塊内部にあるヒント数字の数に対応していることがわかります。
3:いままでの話のまとめ
(#5/16 15時修正 頂点数の計算式B+C,B-Cが間違っていたので修正しました。)
今までの話をまとめると、盤面制約としての定数条件が3つ出てくることがわかります。
1:白マスが占有する外部頂点+白マス2x2の数+市松の数 = X
2:黒マスが触れない頂点数-(2x黒マスループの数+市松の数) = Y
3:黒マスのループ数+外周に接している白マスを含むヒント数+市松の数 = Z
(X,Y,Zは問題盤面から求まる定数)
上記の条件を
白マス2x2の数=A
外周に接する白マスの数=B
外周に接する白マスのヒント数=C
白マスの市松の数=D
黒マスのループ数=E
角にある白マスの数=F
としてまとめてみます。
すると
白マスが占有する外部頂点=B+C+F
黒マスが触れない頂点数=A+(B-C+F)
となるので、判明している盤面制約の条件は
A+B+C+D+F=X
A+B-C-D-2E+F=Y
C+D+E=Z
となります。
ただし、盤面サイズをNxMとした時
X=2x(ヒント数＋ヒントの数字の合計) - (N-1)x(M-1)
Y=(N+1)x(M+1) - 2x(黒マス数+1)
Z=ヒント数
とする。
この条件は2x2禁、分断禁を取り込んだぬりかべルールの言い換えにほぼ等しいものだと考えられます。
4:条件式を弄ってなにかできないか
上記の式をいじくり回してシンプルな結論がでると問題に取り込みやすくなるかもしれないので、何か探します。
2x(A+B-E+F)=X+Y
A+B-E+F=Z+Y
ってことは情報が1つ余分らしい
なので、再度整理すると
A+B-E+F=Z+Y
C+D+E=Z
となります。
ってことは変数が多すぎるから制約としてめちゃくちゃ弱い。
うーん、まともに使えなさそう。
ただ、A,B,Fを0になるようにしたら、Eの最小値を指定できそう？
結論:式に落とし込めたけどあんまり応用が効かなさそう