SGPの特別編です。
はじめに
SGP2019のRd5でParquet Sudokuが出題されました。
過去にもいろんな場所で何度か出題されたことのあるVariantですが、初見ではなかなかとっつきにくいルールになっています。
どうやら、手筋を知っているかそうでないかで大きく解き味が変わるようなので、ここでまとめておきます。
なお、質問や意見・指摘などありましたらTwitterやコメントなどでお教えください。
ルール
基本は普通の数独と同じですが、箱が4*4となっていくつかのマスが大きくなり、9個の箱と12本の行・列のそれぞれで1から9が1回ずつ出現するようにします。
盤面
盤面のパターンはいろいろありますが、次のものが一番基本的です。
4*4の箱のなかで中央が2*2となるのがわかりやすいパターンです。上の基本的な盤面ではL字のマスの向きが「左上・右下」そろっていますが、これが「左下・右上」でも問題はありません。実際、SGP2019Rd5のインストラクションでは次のような盤面になっていました。この盤面も一般的なようです。
ひとまず、L字マスの向きが同じ盤面を「基本盤面」とよぶことにして、基本盤面の場合の手筋を考えます。SGPの本番で出題されたのも基本盤面でした。
なお、中央に2*2が無い場合、マスのサイズがの組み合わせが433111111でない場合 (例えば42221111)等、盤面の形はいろいろ考えられます。この記事ではひとまず中央に2*2があることと、サイズが4333111111であること(3はL字) を仮定しておきます。その他のケースについても、似た議論が適用できることは多いです。
基本盤面に対する手筋
用語として、通常より大きいマスを「大マス」、通常のマスを「小マス」とよぶことにします。また大マスの中でも左上のL字マスを「左上大マス」、真ん中の2*2マスを「中央大マス」、右下のL字マスを「右下大マス」とよぶことにします。
得られた結果を定理の形で書いておきます。証明は後のセクションにつけておくので、気になる人は参考にしてください。
・定理1
タテ3個の箱、ヨコ3個の箱にある9個の大マスには、1から9が1個ずつ入る。図で言うと、水色の9マス、橙色の9マスには1から9が1個ずつ入る。
・定理2
「右上大マス」9個、「中央大マス」9個、「左下大マス」9個には、それぞれ1から9が1つずつ入る。
・定理3
さらに、各箱の小マスで同じ位置にある9個についても、それぞれ1から9が1つずつ入る。
この定理をフル活用すると、SGP2019Rd5で出題された問題を、かなり簡単に解くことができます。興味のある人はやってみてください。
証明
以下上の定理の証明を与えます。
・定理1の証明
上の図で、水色の9マスを考えます。このとき水色マスのある箱3つを合わせて、各数字は横に長さ4だけ占有しないといけません。大マスは長さ2を、小マスは長さ1を占有するので、3つの数字で長さ4にするには2+1+1とするほかありません。よって大マスには必ず各数字が1つずつ入ります。
・定理2の証明
左上大マスに注目しましょう。そのうち2つに同じ数字が入ったとします。定理1よりその同じ数字はタテヨコの違う箱のものになるはずです。一般性を失わず、左上の箱と右下の箱の左上大マスに同じ数字が入ったとします。
すると、その同じ数字の利きと定理1により、右上箱にその数字は入れず、矛盾します。よって、左上大マス9個には1から9が1つずつ入ります。
同様の議論により、右下大マス9個にも1から9が1つずつ入ります。
最後に中央大マスですが、定理1から大マス27個に1から9が3個ずつ入ると分かるため、そこから左上・右下大マスを除いた中央大マス9個にも1から9が1個ずつ入ります。
・定理3の証明
1つの数字に注目して、同じ位置のマスにちょうど1つだけ入ることを示せばよいです。
定理2から、1つの数字の位置について大部分の配置が確定します。対称性から、大マスの位置として図のパターンを考えれば十分です。
青色のマスに同じ数字が入るとすると、残りの数字は白マスの場所に入るとわかります。残りのどの入れ方についても、同じ位置のマスにちょうど1つ入ることは明白です。
一般の盤面について
基本盤面でない場合について、同様の手筋が成り立つか考えます。
まず定理1については成立します。占有長さについて同じ議論ができるのでよいですね。
次に定理2についてですが、これはうまくいきません。大マスとして、「左下大マス」「右上大マス」があるかもしれないからです。ただし、向きの同じ大マスどうしで別の数字になることは保証されます (同じ議論ができるため)。
では、中央大マスについてはどうでしょうか。これについては、おそらく基本盤面と同じことが言えます。
・予想2'
基本盤面でない一般の盤面についても、中央大マス9つには1から9が1つずつ入る。
証明の方針としては、中央マス以外に同じ数字が3つ入らないことを示すというもので、3つ入る盤面パターン自体は存在しますが、数字すべてを埋める方法はどうもないと思われます。なお、インストラクションのパターンではそもそも3つ入ることがないようです。
なお、「一般の盤面」といっても、中央に2*2が無い場合は反例が構成できるようなので、注意してください (指摘がありました。ありがとうございます)。
証明は地道にパターンをつぶすというもので、個人的に解けた気がしていますが、パターン見落としがあるかもしれないので、いったん「予想」の形にしておきます。反例や証明のある方はご一報ください。
そのほかの手筋として、同じ列の4*4の箱3つについて、端の列にある9個ずつのブロックをとりのぞいた9個について、1から9が1回ずつ出る、というのもあります。理由は明らかですね。イメージとしては、中央の「ゆがんだ」列が引ける感じでしょうか。
ひとまず、これらの事実と証明 (もとい、成り立つ理由) を理解しておけば、どんな盤面が来てもある程度対応できると思われます。
