難問なのか？奇問なのか？
0. 概要
2019WPC選抜のバトルシップ2について、解法をまとめておきます。
問題自体は公式サイトから確認してください。要約すると、
・1*2の艦20個を10*10の盤面に配置する。
・艦同士はタテヨコナナメに接触しない。
・いくつかの指定されたマス (波マス) には艦を置けない。
というものです。
1. 頂点でのいいかえ
「接触禁」の問題は、マスの頂点に注目するとうまくいくことが多いです。スネークの最長配置問題などもそれでうまくいきます。
今回の場合、1*2の艦1つを配置すると2*3=6個の頂点を占有することになり、接触禁により頂点は高々1個の艦にしか占有されないため、全部で6*20=120個の頂点を占有することになります。
もともとの盤面には11*11=121個の頂点しかないので、この時点でかなり制約のつよいことが分かるでしょう。
さらに頂点とマスの双対を取れば、「11*11のマス目に2*3の長方形を20個配置する、ないし分割する」問題と言い換えられます。
この言い換えで「指定マスに艦が置けないこと」を言い換えると、「指定された頂点を内部に含むような長方形は置けない」となります。図としては次の通りです。
黒点を内部に含むような長方形は作れません。辺にくるのは問題ありません。
2. タイル置きの制約
11*11の盤面に2*3の長方形を20個置くので、使わないマスがちょうど1つあります。実は、この未使用マスの候補はかなり限られます。たとえば角のマスを使わないとすると、その周りで長方形が置けないことはすぐわかるでしょう。では一般にはどうでしょうか？
これについては、色塗りメソッドにより答えが得られます。まず盤面を市松に塗る (角を黒とする) と、配置する2*3の長方形は白黒マスを同数含むので、未使用マスは黒マスでないといけません。
同様に、3色での塗り分けも効果的です。角から1, 2, 3, ... と値をずらして書き込むと、ちょうど2のマスが1マス多くなるため、候補を絞れます。
結果的に、11*11のマスのうち、未使用マス候補は次の5個にまで減らせます。大事なのは、これが黒点の配置によらず、タイルと盤面の形状のみによることです。
実はこのネタを大昔にハバネロで仕込んだことがありました。現実にはだいたいの人が「引いて」解いてしまったのですが。。。
3. 実際に解く
ここまで準備した上で実際に解いてみましょう。長方形に分割していく上で大事なことは、「使用しないマス以外に、幅1の場所は存在しない」ということです。
とりあえず黒点が並んでいるところに分割線が引けます。それ以外は取っ掛かりが無いように見えますが、R7C7で対角に黒点があることに注目しましょう。このマスは必ず使用しないといけないため、このマスから左上か右下に長方形を伸ばすしかありません。先ほどの幅1の原理も使うと、このマスの使い方は2通りしかないと分かります。
左上に伸ばすならこうなりますが...
このように分割が進むと矛盾してしまいます。
というわけで、右下に長方形が伸びるとわかります。
こうなると、後は順調に分割が進みます。R9C9が未使用と確定し、R9C3に先ほどと同じ議論が使えることにも注意しましょう。そうすると...
このように分割できて、解けました！元の盤面への再翻訳は省略します。
4. 感想とまとめ
もともとこの問題は、見た目や配点からして理詰めのない試行錯誤問題のように見えます。しかし実際には、大部分を理詰めで解くことができます。左上の波マスの配置などを見るに、作者の方も理詰めをある程度把握して作られていると感じます。一見よく分からない問題が、こうして鮮やかに解けるのは気持ちいいものですね。
実際の選抜試験中にこの解き方をするのは難しいかもしれませんが、試行錯誤を効率よく行える可能性はあります。今回使った「タテヨコナナメ接触禁の頂点注目メソッド」と、色塗りメソッドは、別のパズルにも応用が多いので、頭の片隅に置いておくとよいでしょう。
意見や感想などお待ちしております。今回の解法では2択を行っていますが、もっと議論を詰めればうまく回避できるかもしれません。それに限らず、何かしら数理を見つけた方は、ぜひご一報ください。
