ぬりかべのグラフ理論的な
1:最終的に出る式
結論、内部頂点の数=2x(ヒントの数+ヒントの和)-市松の数(白マスの角が接している数)-白マス2x2の数-白マスに接している外部頂点の数が成り立ちます。
実際の図で検証します。
この図において、
内部頂点: 赤+青の点 81個
市松の数: 青の点 1個
白マスに接している外部頂点の数: 緑の点 10個
ヒント数: 7個(3,3,3,4,5,10,11)
ヒント数字の和: 39
となるので、上記の式にあてはめると
81 = 2×(7 + 39) - 1 - 0 - 10
となり、この式は正しいことがわかる。
2:白マスの塊が占有する頂点数
最初の式がどのように出てきたのかを順番に説明します。
まず、ある白マスの塊に対して、占有する頂点数の求め方を考えます。
これは白マスを1つずつ付け足していくことを考えればわかりやすいです。
例えば、次の2→3の変化で増えた頂点数について考えてみます。
この時頂点数は、6個から8個に増えていますが、この増えた2個は元々の塊に接していない白マスの数です。こんな感じで普通に伸ばしていくと2個ずつ増えていくことが予想されます。つまり、nマスに対して2n+2個の頂点数を占めることが出来るはず。
しかし、例外がいくつかあります。それは白マス2x2、ループ、市松が発生する時です。この3つをペナルティと呼ぶことにします。
1:白マス2x2の発生
2:ループ
ちなみに、分断禁がある以上ループは滅多に発生しないので無視してOK
3:市松
これは他のヒントと斜めで接することがあるので結構発生します。
以上に注意すると、白マスの塊が占める頂点数が計算可能です。
最初の例に出した9の塊で考えると、上記のペナルティのうち白マス2x2が2個あるので、2x(1+9) - 2 = 18個と求めることができます。
3:ぬりかべルールへの適用
上記の考え方をぬりかべに適用します。
ルールから、ぬりかべは2x2の黒マスの塊が許されません。これは、内部頂点が白マスで埋められる必要があると言い換えることができます。
つまり、ぬりかべでは白マスで占めることのできる頂点数が内部頂点数を上回る必要があります。余分な分はペナルティや外側の頂点の占有に使われたりして消費されます。
コレを式にしたのが最初のものです。[内部頂点の数=2x(ヒントの数+ヒントの和)-市松の数(白マスの角が接している数)-白マス2x2の数-白マスに接している外部頂点の数]
試しにこの式を使って次の問題を考えてみます。
問題: 次の10x10の盤面に対して？に入る最小値はなんでしょう。
これは内部頂点数を、白マスが埋める頂点数が上回る時を考えれば求まります。
内部頂点数は81個なので、81=6+2x(1+?)-(ペナルティ+占有する外部頂点)を満たす最小の?が分かれば良いです。これはペナルティが1、占有する外部頂点が0の時、?は37となり最小値をとります。
4:例題解説
https://puzsq.logicpuzzle.app/puzzle/123904 この問題を解きます。
この時、内部頂点は81で、わかっているペナルティは市松の1、わかっている占有する外部頂点は10となっている。
また、81=2x(7+39)-(ペナルティ+占有する外部頂点)より、
ペナルティ+占有する外部頂点=11となる。つまり、これ以上ペナルティが発生してもいけないし、外部頂点を占有してもいけないことがわかります。
よって、次のように決まります。
あとは、ペナルティ(市松,2x2)が発生しないように埋めていけばいけます。
5:展望？
これは白マスの密度が低い問題じゃないと使えません。というかこれを使う前提で作られた問題じゃないと使うことないです。白マスの充填に対しても何かあったらいいんですけど、この考え方は分断禁への適用ができないから難しそう
こっちは黒マスに対するグラフを考えたら何かできるようになるかもしれないから、黒マス、白マスそれぞれに対して複合的に考えると何か出てくる可能性がある？