分断寸前

盤面のいくつかのマスを黒く塗り、
黒マス同士は辺で接しない、
黒マスによって盤面が分断されない（白マスは一繋がりになる）

という条件は、いろいろなパズルに出てきます。
クロスワードパズルも大抵はこの条件になっています。

この条件で、黒マスを最大何個配置できるか、について10年以上前にコンピュータで調べたことがあります。これを高速に調べるうまいアルゴリズムを思いついて、１３ｘ１３までの正方格子について最大数を求めてあります。
ろくに調べていませんが、ほかに取り組んだ人はいないんじゃないかないか、と思っています。

結構面白いパズルだと思うのでここで紹介しておきます。
へやわけ、の問題にもできるかな？

問題1．７ｘ７の盤面に黒マスを17個（全１解）
問題2．１１ｘ１１の盤面に黒マスを41個（回転鏡像を同一解として、全３解）
問題3．１３ｘ１３の盤面に黒マスを57個（回転鏡像を同一解として、全８解）

ちなみに、問題３は自分でも全解はわかっていません。
（当時作ったプログラムが、最大個数と、全部で何通りの配置があるかだけを求めるものだったので、具体的な盤面は知らないのです。）
ここ数日久しぶりに手で取り組んでみたけど、やはり問題3は全部はわかっていません。

これ以上の黒マスは配置できない時の最小個数、を求めるのも面白そうだけど、取っ掛かりが無くて調べていません。こっちのほうも奥は深そうです。