最近作問した高難易度のバトルシップについて、解説を載せます。
6 問作成しましたが、根底にある考え方は同じなので、その中から 1 つ選んで解説します。解説するのは 4 つ目に出した次の問題です：
一見すると何の手掛かりもないように見えますが、裏に隠された制約を見破ることでロジカルに解答を導くことができます。以下の解説ではその制約の説明をしたあと、実際に正解までの手順を追っていくことにします。
なお、他の問題もあわせてリンクを貼っておきます。
1 問目 8x8
2 問目 8x8
3 問目 10x10, 2 問目の拡張
4 問目 10x10, 上のもの、1 問目の拡張
5 問目 8x8
6 問目 8x8, 5 問目の拡張
ルールと用語についてはこちら：
大域手筋
隠されている制約は 2 つあり、どちらも盤面全体で考える大域的なものになっています。
さて、通常のバトルシップでは 10x10 の盤面にサイズ 4 のスタンダードフリートを配置することが多いですが、今回作成したものは 8x8 にサイズ 4 の艦隊を詰めたり、10x10 にサイズ 5 の艦隊を詰めたりしています。
試してみるとわかりますが、これらの設定だと詰めるのは結構ギリギリです。そのギリギリ度合いを測る要素として、次の 2 つが考えられます。
1. 格子点カウント
盤面の頂点 (格子点) に注目します。
「異なる艦同士がタテヨコナナメに接さない」という条件から、異なる艦に含まれる頂点が互いに重ならずに盤面の格子点を占有することがわかります。
HxW の盤面の格子点は全部で (H+1)*(W*1) 個あり、これらを艦隊で分け合うことになります。
長さ 1, 2, 3, 4, 5 の艦はそれぞれ 4, 6, 8, 10, 12 個の頂点を含んでいて、サイズ 4, 5 の艦隊合計でそれぞれ 60, 100 個です。
したがって、サイズ 4 in 8x8, サイズ 5 in 10x10 だと、どちらも 21 個の格子点が占有されずに残ります。
占有されない格子点が艦隊配置の際の余裕となるわけです。
2. ブロックカウント
2x2 のブロックに注目すると、その中に艦は高々 1 種、高々 2 マスしか占有できません。これは対角配置禁止によるものです。
したがって、艦それぞれを長さ 2 ずつのパーツに区切ると、それらは必ず異なる 2x2 ブロックを占有することになります。
サイズ 4, 5 だとこのパーツがそれぞれ 13, 22 個あり、8x8, 10x10 の盤面をを 2x2 のブロックに分けるとそれぞれ 16, 25 個になるので、サイズ 4 in 8x8, サイズ 5 in 10x10 だと艦が占有しないブロックは「最大で」3 個になります。
なお、偶数の長さの艦について、配置によっては 1 つ多くパーツを使うことがあります (パーツの分け方が 2 ではなく 1+1, または 2+2 ではなく 1+2+1, のようになるケース)。
この余分な分け方もブロックの余裕を消費しますが、一方で余裕がなくなればこのような分け方になる配置があり得ないともわかります。
これらの格子点的余裕・ブロック的余裕の 2 つを評価しながら、論理を進めていきましょう。
初手・余裕値の評価
ここから解答手順に入っていきます。
まず、盤面でのブロック的余裕について調べましょう。
上で述べたように 10x10 の盤面を 2x2 のブロック 25 個に分割したとき、艦が入らないブロックは高々 3 つです。
ここで角に注目すると、そのうち 2 つを消費していることが分かります。
また 5-6 行目にも注目すると、艦が (1+3=) 4 つしか入らないことから、5-6 行目にあるブロック 5 個のうち 1 つには艦が入りません。
したがってこれでブロック的余裕を使い果たし、(事実A) 1-4, 7-10 行目の残り 18 ブロックすべてに艦が入ることがわかりました。
さらに、(事実B) 5-6 行目の 5 ブロックのうち、艦が入る 4 ブロックには艦が 1 個ずつ入ることもいえます。艦が入らないブロックが 2 個以上あってはいけないからですね。
加えて、艦の分け方も余裕がなく、(事実C) 長さ 2, 4 の艦は 2x2 のブロックにそれぞれ 2, 2+2 という分かれ方で入ることもわかります。
これらの事実は地味ですが、後で艦を埋めるときに役立ちます。
次に、格子点的余裕を調べます。
もともと格子点は全部で 121 個あり、そのうち 100 個を艦が占有するため、残り 21 個の艦が占有しない頂点がどこかを探ります。
ここでも、角が余裕を使うことが分かります。階段型の波マスにより、確定で 6 個は占有しません。また対角に入らないことから 2 個余分に余裕を使うとわかります。
これで、角二つ分で 16 個の余裕を使うとわかりました。
また、やはり 5-6 行目に艦が 4 つ入らないことに注目すると、5-6 行目の間にある格子点 11 個のうち、艦に占有されるのは高々 (2x4=) 8 個です。よって最低でも 3 個は余裕を使います。
よって、残る余裕は 2 個しかないとわかりました。ここで、残りの余裕を使う要因は
- 角 2 箇所・中央の行以外の格子点が占有されない
- 角の対角 2 択した部分について、その両方で艦に占有されない
- 中央の格子点について、艦が並ぶなどして余分に余裕を使う
などが考えられます。
二線の大きい数字
余裕の考察から、ブロック的余裕はなく、格子点的余裕も残り 2 個しかないことがわかりました。
そして、盤面には格子点的余裕を消費してしまう場所があります。それが 9 列目の 5 のヒントです。
というのも、辺から 2 列目 (二線) に連続して艦が入ると、 辺の格子点の余裕を 3 つ消費してしまうためです。
したがって、1-2 行 9 列の 2 マスの両方が艦になると、余裕を 3 個使うことになりハタンします。3-4 行 9 列の 2 マスについても同様です。
すると、これらには艦が 1 つまでしか入りません。さらに、事実 B により、5-6 行 9 列にも 1 つまでです。したがって、 7-8 行 9 列の 2 マスにはどちらも艦が入るとわかります！
ここで注目すべきは、その 2マスの右で格子点的余裕を 1 使うことです。
また、評価に使った 9 列目の 1-2 行、3-4 行、5-6 行のペアについても、艦が 1つずつ入るとわかります。
加えて、上の辺での余裕に注目することで議論が進みます。
例えば 2 行 10 列が艦になると、角で 余裕を 3 個消費してハタンします。
このように余裕の消費に気を付けることで、右辺を埋めきることが可能です：
右辺が決まる。また余裕がなくなった！
そしてついに、右辺で格子点の余裕を 2 消費しました。よって、(事実D) 角・中央・右辺以外の頂点はすべて艦に占有されることが分かりました！これは大きな事実で、たとえばこの時点で 5 行 9 列のマスや 左下角のマスに艦が入ることが分かります。また格子点の余裕がもうないことから、
- (事実E) 左上角・右下角の頂点占有の二択のうち、どちらかは占有する
- (事実F) 中央の線上の格子点の余裕はちょうど 3 つ。特に艦が連続して入ることはない。
などもわかります。これらの事実により、盤面が一気に進みます。
中盤・わかった事実の適用
ここからは、これまでに分かった事実を総動員して埋めていきましょう。
まずは事実 C (偶数艦の分け方) と事実 D (頂点占有) のコンボです。
10 行 7 列の艦に注目すると、もしこれが横に伸びるならば、事実 C より長さが偶数にならないことがわかります。
特に、10 行 7 列に艦が入らないと、辺の頂点占有により長さ偶数の艦が入ってしまいハタンします。よって 10 行 5 列に艦が入ります。
このように一つ飛ばしの単純仮定が 10 行目および 4 行目で適用できて、次のように進みます。
さらに、下半分の区域の 6 列目に注目します。ここは先ほどの二線のような形になっており、頂点占有のロスが起きないようにする必要があります。
たとえば 6 行 6 列に艦が入ると、頂点占有しないように横に伸びることになりますが、これは事実 F (中央で艦が連続しない) に矛盾します。
さらに、7 行 6 列も艦が入りません。入ると上の対角にある 2 マスに入らなくなり、 事実 B (中央ブロックで艦が入らないのは 1 つまで) に矛盾するためです。
この議論は 4 列目・2 列目と波及して、次のように進みます。
すると、 4 列目のヒントの 3 が苦しくなってきました。よってここに注目します。
まず 2 行 4 列のマスについて、ここに艦が入ると、角の二択 (事実 E) どちらについても格子点の余裕を消費してしまいます。よって艦は入りません。
さらに、1 行 4 列のマスに艦が入ると、2 行目のヒントの 2 により 2 行目で連続で艦が入ることとなり、やはり格子点の余裕を消費してしまいます。
よって、残る 4, 8, 10 行目の 3 マスに艦が入るとわかります。
そこからさらに、頂点占有 (事実 D) に気を付けて 埋めていくことができます。8 行目がやや難しいですが、10 列目を進めた上の議論と同様に進められます。
終盤・艦自体をカウント
あとは埋めるだけです！
各々の長さの艦をカウントしましょう。まず長さ 2 の艦はすでに 4 つすべて入っています。よって右上は長さ 4 になります。
また、6 行目のヒント 3 の残った二択について、7 列目のほうに入らないと、頂点占有の影響で艦が下から伸び、長さ 2 になってハタンします。よってこの二択も決まります。
ここで、長さ 4 の艦をあとひとつ入れる必要があって、左下にしか入りません。
さらに、6 列目ヒントの 1 の二択で長さ 5 が売り切れるため、4 行目に残っている場所は長さ 1 と 3 になります。
そして長さ 1 が売り切れたため、下の部分を埋めきることができます。
まとめ
艦の頂点占有＋ブロック占有を大域的に調べることで、手筋として使える事実がいくつもわかり、それらを使って埋めていくことができました。
頂点・ブロックともに注目する必要がある、というのが美しいポイントかなと思います。
なお、他の問題も同様の議論で解き進めることができます。個人的には 6 問目の角の機構が美しいと思ったので、気になる方は解いてみてください！
