へやわけのペナルティ理論がわからないから自分用まとめ

ゲッソー

2024年6月12日 22:21

最終的な式は"いったんのまとめ"の項目の最後にあります。
ぬりかべでやったことを、へやわけに適用。https://note.com/m98561442_/n/n7d8a8d2235ef

(すでにあるへやわけのペナルティ理論がよくわからなかったので自分用に書きました)
今回の内容は全部空中の部屋について書いてるけど、凹みのない部屋なら常に成り立つはず。

大まかな流れ

1:黒マス基準で頂点占有数の議論
2:白マス基準で頂点占有数の議論
3:白マス基準でグラフの議論
4:まとめ

今後の式は、左を埋め方によらない定数、右がを変数として書きます。ちなみに、
最終的には式は1つしか出ません。

1:黒マス基準で頂点占有数の議論

結論、
黒マスx4-部屋内部の頂点 = 2x部屋外周の黒マス + 部屋角の黒マス + 市松の数 - 白マス2x2の数

(内部+外部)の黒マスの占有頂点数を考えると
部屋全体の頂点数 = 黒マスx3 + 黒マスの塊の数 + 白マス2x2の数 + 黒マスが占有していない外周の頂点数・・・①

次の外周のみを考える、角では3つ消費されるので
部屋外周の頂点数 = 2x外周の黒マス数 + 角の黒マス数 + 黒マスが占有していない外周の頂点数・・・②

となる。よって、①-②より
部屋内部の頂点 = 黒マスx3 + 外周に接している黒マスの塊の数 + 空中の黒マスの塊の数 + 白マス2x2の数 - 2x外周の黒マス数 - 角の黒マス数

で、黒マスの塊の数=黒マス数 - 市松の数より、
部屋内部の頂点 = 黒マスx4 + 市松の数 + 白マス2x2の数 - 2x外周の黒マス数 - 角の黒マス数
よって、定数を移行させると
黒マスx4-部屋内部の頂点 = 2x部屋外周の黒マス + 部屋角の黒マス + 市松の数 - 白マス2x2の数・・・③
情報1個削れてるけど一旦スルー

2:白マス基準で頂点占有数の議論

結論、
全体の頂点-白マス数x2 = 白マスのグループ数x2 - (市松の数+白マス2x2+2x白マスループ)+部屋の角の黒マス・・・④
これも、同様に計算したら出せます。ここでいう白マスループは黒マスだけを含み
、かつ1個以上含んでいるループの個数を表しています。
これは以前のぬりかべの記事を参考にして考えるとわかると思うので省略します。

3:白マス基準でグラフの議論

結論、
全体の辺数 - 黒マスx4 - 白マス数-外周のマス数-角のマス数= (白マスの2x2+白マスループ)- 部屋外周の黒マス数 -白マスのグループ数- 部屋角の黒マス・・・⑤

これは、白マスが占める辺数(白-白、白-壁)=(白マス数-白マスのグループ数)+(白マスの2x2+白マスループ) + 部屋の周辺の白マス数+角の白マス
となるので、これと黒マスの占める本数を考えてあげるとOK
すると、
全体の辺数 = 黒マスx4 + (白マス数-白マスのグループ数)+(白マスの2x2+白マスループ) + 外周のマス数-外周の黒マス数+角のマス数-角の黒マス数)

いったんのまとめ

以上をまとめます。
A = 白マスのグループ数
B = 市松
C = 白マスの2x2
D = 白マスのループ
E = 部屋の角の黒マス
F = 部屋の外周の黒マス
X = 黒マスx4-部屋内部の頂点
Y = 全体の頂点-白マス数x2
Z = 全体の辺数 - 黒マスx4 - 白マス数-外周のマス数-角のマス数
とおくと、
X =2F+E+B-C
Y = 2A-(B+C+2D)+ E
Z = C+D-F-A-E
となる。(X,Y,Zは部屋情報から決まる定数)
で、2Z=X+Yより情報は2つ

今回は-Z,X+Zで考えていく。

1:よく見るやつの制約

-Z = (外周の黒マス数+角の黒マス+白マスの塊の数)-(白マスの2x2+白マスループ)・・・⑥

この式の両辺から、(外周黒マス数最大値+角黒マス
最大値)を引いてあげると、よくみるペナルティの式になるはず。まり餡さんの表記に従うなら
角の黒マス・・・第一種ペナルティ
外周の黒マス数・・・第二種ペナルティ
白マスの2x2+白マスループ・・・第三種ペナルティ
あと、部屋を空中に拡張すると
白マスの塊の数・・・第四種ペナルティ
が発生する。

2:あんまり見ない方の制約

X+Z = -外周の黒マス + 市松の数 + 白マスループ-白マスの塊の数

この制約は使いにくそう…なので、なにか言い換えを考える。
市松の数=黒マス数 - 黒マスの塊の数
白マスループ = 空中(部屋の壁に触れていない)の黒マスの塊の数

すると、
X+Z -黒マス数= -外周の黒マス+空中の黒マスの塊の数-黒マスの塊の数-白マスの塊の数より

黒マス数-(X+Z) = 部屋の壁に接する黒マスの塊の数+白マスの塊-外周の黒マスの数・・・⑦

となる。これは、外周黒マス数- 部屋の壁に接する黒マスの塊の数=壁から壁につながる黒マスの橋の数なので、これは白マスグループ+1に等しくなる。
つまり、常に黒マス数-(X+Z)=-1となる。よって、これは情報が無なので、使う必要はない。

いままでの話をシンプルな10x10の壁に囲まれた盤面に適用

盤面全体では、
白マスの塊の数 = 1なので、⑥は

-Z-1 = (外周の黒マス数+角の黒マス)-(白マスの2x2+白マスループ)・・・⑥'
となる。

解く時の実用的な形に変換(本当にざっくり)

Let's practice applying the Penalty theory to this relatively easy problem.
この比較的簡単な問題で、ペナルティ理論の適応を練習する。https://t.co/5FAg0nPwSX
— Coggy's Pencil Puzzles (@pencilpuzzles) June 26, 2023

ここで紹介されている図のペナルティの対応を調べていく。(以下Coggyさんの図を引用)
ただ検証が疲れたので、雰囲気だけの説明をします。

まず前処理として、⑥から(外周黒マス数最大値+角黒マス最大値)を引いてあげる
すると、
-Z- (外周黒マス数最大値+角黒マス最大値)= (外周の黒マス数の最大値からの欠損+角の黒マスの最大値からの欠損+白マスの塊の数)-(白マスの2x2+白マスループ)
となる。

ここで壁付近を上記のように最大1個まで黒マス
が入れるような部屋に分解する。これによって、
外周の黒マス数の最大値からの欠損 = 青とピンクの領域のうち黒マスが入らなかっ部屋の数(2a,2b)
角の黒マスの最大値からの欠損 = 角が白マスのマスの数(1)
に対応している。

白マス2x2の数 = 完全ループペナルティの数(3a)
で、外部の未接触頂点の数 = 外部頂点 - 部屋外周の黒マスx2 + 部屋角の黒マスとなるので、これが(3b)に対応している。これは壁がないところの黒マスの最大値からの欠損を表している？

上記には書いてないけど、白マスループ(空中の黒マスの塊の数)もペナルティ(4)になる。

白マス塊の数はどこに対応しているか不明、どこやろう

って感じで一旦終わり、厳密なやつがわかったらもっかいまとめて記事書きます。

追記1:厳密なペナルティの式

上記のZで検証して正確なやつ (どんな部屋にも適用できるやつ)を出したので書く

周辺マスを、壁、境界線に接するマスと決めます。
値を次のように決めます。
A_black = 境界線に1辺以上接する黒マスの数+境界線に2辺接する黒マスの数+2x境界線に3辺接する黒マスの数
A_blackMAX = 境界線に1辺以上接する黒マス最大値+境界線に2辺接する黒マス最大値+2x境界線に3辺接する黒マス最大値
A_penalty = A_black_MAX - A_black
A_all = 境界線に1辺以上接するマスの数+境界線に2辺接するマスの数+2x境界線に3辺接するマスの数

この時、
全体の辺の数(白-壁も含む)-4x黒マスの数-白マスの数-A_all+A_blackMAX = A_penalty + (白マスの2x2+白マスループ) - 白マスの塊の数
となる。

ここで左辺は部屋の形に依存する定数。つまり、部屋と数字が与えられると右辺が定まる。

次の部屋で計算してみる。