ぬりかべ1 解説ハバネロ

2024年7月20日 02:03

1ヶ月前に連投したハバネロぬりかべx5の解説をします。
すぐに解説を出さなかったのは、理詰めじゃないのに理詰めと言い張られるようなハバネロのぬりかべがソルバーで量産されそうな気がしたからです。

結論、ペナルティを利用すると解けます。コメントのXの値はペナルティを表していました。

ペナルティの式

ずっと前にあげたぬりかべのグラフ理論のところから式を持ってきます。
(m+1)(n+1)-白マス数x2-白マスヒント数 = 黒マスループ+外周の黒マス+角の黒マス-白マス2x2
この式を最密問題に適用できるように次のように変形させていきます。
白マス2x2 = 白マス2x2の最大値 - Penalty{白マス2x2}
外周の黒マス = 外周から2マス以内にあるヒント数 + Penalty{余剰外周ヒント数} + Penalty{外周余剰黒マス}
角の黒マス = Penalty{角の黒マス}
黒マスループ =Penalty{黒マスループ}
とすると、今までのPenaltyの合計をPenalty_totalとすると、
(m+1)(n+1)-白マス数x2-白マスヒント数 - 外周から2マス以内にあるヒント数 + 白マス2x2の最大値 = Penalty_total
となります。

外周の黒マスの補足

例えば下図の外周の黒マスを最小にしたいと考えると、外周の白マスの塊に触れているヒントを黒マス1個で分断すればいいとわかる。この時に必要な黒マス数はヒント数に一致する。なので、理論値を外周から2マス以内にあるヒント数として、そこからのズレをペナルティとしている。

例題の図で確かめる

次の図で検証します。

この図の場合、121-2x42-10-6+9=30となります。
(白マス2x2の最大値は4,5が1個、6が2個、9が4個となる。)
つまり、ペナルティを30も犯しています。
このペナルティを検証します。
1:Penalty{白マス2x2}
→実際の2x2は2なので、7となります。
2:Penalty{余剰外周ヒント数}
→外周から2マスに侵入しているヒント数は真ん中の3以外なので、9個
つまり、3個余剰なので、3となります。
3:Penalty{外周余剰黒マス}
→外周2マスに入っているヒント数は9個、外周の黒マスは26なので、
26-9=17となります。
4:Penalty{角の黒マス}
→3個なので、3となります
5:Penalty{黒マスループ}
→0となります

つまり、今回はPenalty_total=7+3+17+3=30となり一致する。

実際に解いてみる

この問題を解いてみます。
ペナルティは121-2x73-6-5+(8+6+4+0+6+12)=0となるので、
この問題を解くにあたって、
・白マス2x2は最大値と一致
・10は外周から2マスの範囲に侵入しない
・外周で黒マスが2個以上連続して繋がることがない
・角は白マス
・黒マスループは無し
という制約が加わります。

すると、色々と決まっています。
13は以下の1パターンしかありえません