ニコリの波及効果　2日目 - 西尾泰和のはてなダイアリー

3x3の9マスの空間を作って、かつ初期状態で数値を全く置かなかった場合に、答えが決まる最小サイズはどれくらいだ？
2x2の場合は、、、とここまで書いてブログで形状を表現するのがかなりめんどくさいことに気がついた

の続きの話。とはいえ、まだブログ上で見やすくするスクリプトとか書いていないので書いても反応が薄いだろうとは思うけど。(スクリプト書いてないというより今日の今日まで何もしてなくて、昼休みにふと思いついて紙の上でグリグリ書いていたら面白いことに気づいたって話)

そもそも「2×2の空間を含んでる、ヒント無しで一意に決まる最小のサイズは？」という問いは問題が大きすぎる。小さい方から考えよう。「n×mのパズルには、ヒント無しで一意に決まる分割の仕方があるか？」

1×1には当然ある。1×2には2通りしか分割のしかたがなくて、AAだと解が一意に決まらない(以下「不定」)、ABだと解がない(以下「不能」)、1×3はABBの分割で一意に解が決まる。2×2に決まる分割はない。2×3には少し考えて(いいパズルだった)分割が存在することがわかった。そして2×4に関して散々考えて、分割が見つからないが、分割の列挙に取りこぼしがないか自身がないので存在しない証明はできず。

帰りの電車で、2×4はとりあえず諦めて、3×3を考えてみた。これは分割がある。3×4もある。3×5もある。あれ？もしかして片方の辺が奇数だと簡単に見つかるのか？というわけで4×4に挑戦。一度当初目標にしていた「2×2の空きマスを含む」に挑戦して挫折するという遠回りがあったが、これも分割が見つかった。

あとこの問題を友達に説明してて気づいたんだけど1xnはnが奇数の時にはABBCC...ZZという分割があるね。(25日追記:これは間違い。ABBCCのABBの部分が121になった後、CCは21でも12でも制約違反)偶数ならどうかというと…出来るって例をだそうとしたら意外と難しかった。まあでもこれは分割の列挙が簡単だからプログラムを書けばすぐわかるね。

未解決問題メモ(多分難易度順)

1×nで一意に決まる分割のある最小の偶数nはいくらか？
「2×4には一意に決まる分割方法がない」という予想は正しいか？
「十分大きければ(3×3以上なら)かならず一意に決まる分割が存在する」という予想は正しいか？
2×2の部屋を含む最小のパズルは？(25日追記:5×5で条件を満たすパズルを作れる)
3×3の部屋を含む最小のパズルは？

ちなみにここまでのところ全部紙とペンと目視でのチェックなのでミスが入っている可能性は否定出来ない。分割例は自分で考えてみるほうが面白いと思うけどメモしておかないと僕が忘れるので書いておく

ABB
CBD
CDD

ABBC
DBEC
DEEC

ACCEE
BCDEF
BDDEF

ADDF
BDEF
BCEF
CCEG