問題設定

$m \times n (m, n は奇数)$ の土地に，地雷が埋められている．地雷は各地点に高々1つ埋められているが，どこに地雷があるかはわからず，各土地とその8近傍（各土地と，上下左右斜めの土地）に存在する地雷の総数だけがわかっている．

このとき，中央の行に存在しうる地雷の最大数を求めよ．

考察

この問題の答えの解説は秋葉さんの本に譲るとして，この問題を眺めていると自然とこんな疑問が湧いてきます．

$m \times n$ 個の0/1変数と $m \times n$ 本の線形等式で定義される整数計画問題なのだから，ガウスの消去法で地雷の配置が（一意に！）定まるのではないか？

どうなのでしょうか．この疑問に答えるべく，python で実験してみます．ここでは，問題サイズ（ $20 \times 20$ まで）ごとに，線形等式系を表す行列のランクがどれだけ 落ちているか を表にしました．

       1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20 
-------------------------------------------------------------------------------------
  1:       1           1           1           1           1           1           1 
  2:   1   3   3   4   6   6   7   9   9  10  12  12  13  15  15  16  18  18  19  21 
  3:       3           3           3           3           3           3           3 
  4:       4           4           4           4           4           4           4 
  5:   1   6   3   4   9   6   7  12   9  10  15  12  13  18  15  16  21  18  19  24 
  6:       6           6           6           6           6           6           6 
  7:       7           7           7           7           7           7           7 
  8:   1   9   3   4  12   6   7  15   9  10  18  12  13  21  15  16  24  18  19  27 
  9:       9           9           9           9           9           9           9 
 10:      10          10          10          10          10          10          10 
 11:   1  12   3   4  15   6   7  18   9  10  21  12  13  24  15  16  27  18  19  30 
 12:      12          12          12          12          12          12          12 
 13:      13          13          13          13          13          13          13 
 14:   1  15   3   4  18   6   7  21   9  10  24  12  13  27  15  16  30  18  19  33 
 15:      15          15          15          15          15          15          15 
 16:      16          16          16          16          16          16          16 
 17:   1  18   3   4  21   6   7  24   9  10  27  12  13  30  15  16  33  18  19  36 
 18:      18          18          18          18          18          18          18 
 19:      19          19          19          19          19          19          19 
 20:   1  21   3   4  24   6   7  27   9  10  30  12  13  33  15  16  36  18  19  39

空欄は行列のランクが落ちていない，フルランク（つまり提案手法で解ける部分）を示しています．

これを眺めていると，ランクが最大で $m+ n-1$ 落ちてしまっていて，線形等式系を用いたアプローチは筋が悪いように思えてきます．（実際， $m+ n$ 以上ランクが落ちることはありません．これは，土地の上辺と左辺の変数を固定したら，行列がフルランクになる＝答えが一意に定まることから従います．）

では，線形等式系を用いて問題を解けるような設定があるのか，考えてみます．次の問題を考えます．

変種

$m \times n (m, n は奇数)$ の土地に，地雷が埋められている．地雷は各地点に高々1つ埋められているが，どこに地雷があるかはわからず，~~各土地と~~その8近傍（ ~~各土地と，~~ 上下左右斜めの土地）に存在する地雷の総数だけがわかっている．

このとき，中央の行に存在しうる地雷の最大数を求めよ．

灯台下暗しな地雷探索をするバージョンです．この場合，線形等式系のランク落ちは次のようになります．

       1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20 
-------------------------------------------------------------------------------------
  1:   1       1       1       1       1       1       1       1       1       1     
  2:                                                                                 
  3:   1       1       1       1       1       1       1       1       1       1     
  4:               2                   2                   2                   2     
  5:   1       1       1       1       1       1       1       1       1       1     
  6:                                                                                 
  7:   1       1       1       1       1       1       1       1       1       1     
  8:                                                                                 
  9:   1       1   2   1       1       3       1       1   2   1       1       3     
 10:                                                                                 
 11:   1       1       1       1       1       1       1       1       1       1     
 12:                                                                                 
 13:   1       1       1       1       1       1       1       1       1       1     
 14:               2                   2                   2                   2     
 15:   1       1       1       1       1       1       1       1       1       1     
 16:                                                                                 
 17:   1       1       1       1       1       1       1       1       1       1     
 18:                                                                                 
 19:   1       1   2   1       1       3       1       1   2   1       1       3     
 20:

ランクは高々3しか落ちないようです．それゆえ，上手に3変数を固定してしまえばあとは配置が一意に定まるわけです．3つの0/1変数は8通りの値しかとらないので， 8回線形等式系を解けば答えが見つかるということです．

線形等式系を解くというアプローチでこの変種を解くためには，

従属する3本のベクトル（3変数）を選び出してくるアルゴリズム
その正当性の証明（ランクが高々3しか落ちないことの証明）

が必要なのですが，これができていません．土地の4頂点のうち3つを固定したら残りの問題はフルランクになるような気がしているのだけど，証明できていません．明らかな周期性が見えているので時間をかけたら証明できるように思います．

追記

@k_k_hiroki さんとの議論によって，秋葉さんの紹介している手法は「地雷の数の行ごとの和に関する一意可解な線形方程式系を作り，それを解く」という内容であることがわかりました．この手法が変種に適用可能かどうかは，謎です．

buq’s blog

覚えておきたいけど覚えておけなさそうなことを書きます?

マインスイーパーは解けるのか GCJ 2008 final C

問題設定

考察

変種

関連研究

追記