こんばんは。きなこ屋です。
今日もシャカシャカのお話です。
表題の通り、ここで扱うのは「数字なし・外周のみ」シャカシャカの唯一解性について。
問題
図1のように、通常盤面で数字がなく、外縁部のみに黒マスが配置されたシャカシャカを考えます。
https://puzsq.logicpuzzle.app/share/110596
与えられたm*n(m≦n)サイズの盤面に対して、唯一解となる配置は存在するのでしょうか。
本稿では、これを一般の(m,n)に対して検証していきます。
1~3*n
通例、シャカシャカには「盤面に1つ以上の三角形を配置しなければならない」というルールが設けられます。これは極めて特殊な盤面においてパズル性を担保するための措置とみられますので、ここでは無視することとします。
1*nの場合、任意の盤面はそのまま唯一解です。
2*nの場合、全マスが外縁部ですので、全マスを黒マスにすれば唯一解です。上記のルールを考慮しても、2*3以上では図2上の構造が解になります。
3*nの場合、図2上に真っ黒な3列目を加えることで構成できます。もう少しパズルらしくしたい場合、図2下の例が挙げられます。
4*n
まずn=4,5,6,7,8,9,10,11,12,14の例を列挙します。
黒マス最少の例を探したつもりだが、n=8などは怪しい
<命題1> 4*n盤面で唯一解となる配置が存在するのは、n=4,5,6,7,8,9,10,11,12,14のときに限られる。
以下、<命題1>の証明です。
<補題1> ある4*n盤面が唯一解であるならば、図4は黒マスの配置に関わらず灰色領域で破綻しない。
以降の図では、辺縁部のうち特に黒マスを置かない白マスには※をつけて明示することにします。従って、例えば図4では辺縁部に黒マスを表示していませんが、実際には辺縁部のいずれのマスにも黒マスが入りうることを想定している点に注意してください。
<補題1の証明> 図5左の領域A1,領域A2を考えます。
右中央：A1,A2の一方が埋まっている
右下：A1,A2が埋まっていない
領域A1,A2それぞれに1つでも黒マスが入る場合、図4から手を進めると図5右上のようになり破綻せず成立することが分かります。以降、盤面の隅のA1にあたる3マスの領域に1つでも黒マスが入る場合、それを埋まった隅と呼称します。そうでないものを空いた隅と呼びます。
領域A1,A2のいずれかに黒マスが入り他方に入らない、すなわち隅の片方が埋まりもう片方が埋まっていない場合、図5右中央のようになりこれも成立します。
では領域A1,A2のいずれにも黒マスが入らない、すなわち隅の両方が埋まっていない場合。 このとき図4は破綻するのですが、代わりにこの配置が唯一解ではないことが同時に示されます。従ってこのパターンは除外され、図4の成立が保証されます。
唯一解ではないことの証明は次のようになります(長いです)。まず図6左のマスB1,B2の白黒で場合分けを行います。
B1,B2がいずれも黒マスの場合、図6右上①,②のいずれかとなりますが、どちらも左側の空間が複数解となります。
B1,B2の一方が黒マスの場合、これも図6右中央③,④のいずれかとなり、やはり左側が複数解となります。
B1,B2の両方が白マスの場合(⑤)、左側の空間を唯一解にするような周囲の形状は図7左しかありません。図7左を含む想定解は①〜④の4パターンです。しかし外部の(※がついていないマスの)情報からは、①や②は⑤と、(②や)③は⑥と、④は⑦と、それぞれ区別することができません。すなわち図7左とは異なる解が存在することになり、複数解が確定します。
以上より、図5下の2隅が埋まっていないパターンはもれなく複数解となります。(証明終)
<補題2> ある4*n盤面が唯一解であるならば、図8は黒マスの配置に関わらず灰色領域で破綻しない。ただし、灰色領域の左右に少なくとも幅3マスが必要。
<補題2の証明> ('23 3/27追記：証明パートを修正)
図8内部の成否は、図9上に示す6マスのみに依存します。殆どのパターンでは図8の配置は内部で1つ以上の解を持つことが全探索により確認できます。解を持たないのは図9下及びその鏡像のパターンに限られますが、この配置は唯一解にならないことが示せます。
下：図8の配置が破綻する唯一のパターン(鏡像を除く)
図9下の配置が唯一解でないことを確かめるため、本来の想定解によって場合分けします。2つの黒マスの間に注目します。
想定解が図10の形の場合、右部分に壁ができ、<補題1>によって唯一解が否定されます。
想定解が図11上の形の場合、場合分けにより図11①~⑥の6パターンに進行します。これらはそれぞれ下のように外部から区別できない別解を生じます。なお図9下に示した4つの※は省略されています。
①...A1が空なら①-1、そうでなくA2が空なら①-2、
そうでなくA3の1マス以上が黒なら①-3、どれでもないなら①-4が別解。
③...B1が空なら③-1、B2が空なら③-2、いずれでもないなら③-3が別解。
④...C1の1マス以上が黒なら④-1、そうでないなら④-2が別解。
②⑤⑥...それぞれ②-1、⑤-1、⑥-1が別解。
想定解が図12上の形の場合、場合分けにより同様に別解を生じることがわかります。
右端の場合、A1,A2が空いているか否かで分岐。
なお、図11、12の別解を考える上で次の2つの性質を使っています。
<性質1> 想定解で直立長方形に含まれる白マスは、別解で三角形を入れても破綻しない。
<性質1の説明> 数字なしのシャカシャカでは一般に、2*2以上の直立長方形があると唯一解になりません。中に三角形を入れて容易に別解を作ることができるためです。このため唯一解に直立長方形があるとすれば1*nの形になります。従って三角形で一部を埋めても長方形以外の形になりません。
もちろん想定解から三角形を減らして白マスを生じさせる場合は、周囲の形状によっては破綻します。
<性質2> 図13の①の形が唯一解なら、②は図の左側の灰色部分で破綻しない。
<性質2の説明> 左側の想定解での配置を図13下③~⑦で場合分けすることによって確かめられます。この性質は図11①、④、⑤で利用しています。
例えば⑤の上(想定解)から下(別解)を作るにあたり、<性質1>を使っている。
以上で、図9下の配置が複数解になり、図8が破綻しないことが示されました。(証明終)
(再掲)<命題1> 4*n盤面で唯一解となる配置が存在するのは、n=4~12,14の場合に限られる。
<命題1の証明> n=4~12,14の場合の成立例は既に挙げました。
nが13以上の奇数のとき、図14上・下のように三角を配置します。
下：<補題1>、◇、<補題2>、<補題1>の順に並べる。
上下いずれの配置でも、青部分は<補題1>、黄部分は<補題2>から破綻しないと分かります。他の部分は全て埋まっていますから、それぞれの図から解を構成することができます。そして解はいずれも仮定した唯一解に一致することになります。しかしながら、2つの配置は図15に示す通り両立できませんので、矛盾が導かれました。
nが16以上の偶数のとき、図16上・下のように三角を配置します。
下：<補題1>、<補題2>×2、<補題1>の順に並べる。
こちらも上下ともに解を構成し、これらは両立しないことから矛盾が導かれます。(証明終)
5*n
https://puzsq.logicpuzzle.app/puzzle/114964(作：locker様)にて、幅3k+1の場合は唯一解にできることが示されました。この配置は短辺への黒マス配置を必要としませんので、両端に真っ黒な列を追加することで幅3k+2,3k+3の場合も構成することができます。従って5*n盤面は常に唯一解盤面が存在します。
8*n, 10*n〜
順番が前後しますが、先に8*n以上の場合を考えます。
かんれいと様による先行研究(https://twitter.com/etar_nac/status/1682891913215762433?s=20)により、2m*2n(m,n≧4)、すなわち8*8以上で偶数*偶数の場合には全て複数解になることが明らかになっています。先ずこれを参照させていただきます。
8*8の場合、図18左のように中央と隅を開けて辺から2列目に三角を並べることで破綻せずに解をなし、中央部分に三角が入るか否かで複数解となります。
この解は図18右のように2マスずつ延長することができ、中央部は依然複数解ですので、8*8以上の偶数*偶数盤面は全て複数解になります。
(右)8*8以上の2m*2nサイズも複数解
以上がオリジナルの証明になります。
オリジナルでも言及されていますが、幅が奇数の場合にも同様の考え方を適用することができます。図19のように、8*11、11*11の場合にも中央部を空けた複数解が存在します。これらの解も同様に延長することができます。
このことから、8*n(n≧10)やm*n(m≧10,n≧10)盤面に唯一解配置は存在しません。後の9*nの考察からもわかります。
従って、残るは6*n,7*n,9*nとなります。
6*n
n=6,7,8の場合は図20のようにして構成できます。
<命題2> 6*n盤面で唯一解となる配置が存在するのは、n=6,7,8のときに限られる。
<命題2の証明> n=9,10で複数解になることを示せれば、それを2マスずつ延長してn≧9のときは常に複数解になることが言えます。
n=10の場合、まず盤面を上下に分割します。図21のように上半分を考えると、隅の埋/空によらず図17左①は破綻しません。さらに、隅や辺の場合分けによって②-1~②-4のいずれかが成立することが分かります。こうして上半分だけで2通りの埋め方ができます。
下半分も同様に2通りの埋め方があり、上下を組み合わせても横幅1の直立長方形しか影響しないため破綻することはありませんから、最終的に6*10盤面は異なる4つの解を持つことになります。
左上隅が空いていれば、②-1か②-2(橙マスで分岐)のどちらかが成立。
右上隅が空いている場合はその鏡像が成立。
2隅とも埋まっていて、かつ青マスのうち1つでも埋まっていれば②-3が成立。
そうでないなら②-4が成立。こうして①②の2つの解ができる。
n=9の場合も盤面を上下に分断した上で、隅が埋まっているか否かで場合分けを行います。
図22のうち、2隅が埋まっている場合は①と②、1隅が埋まっている場合は③と④(④-1or④-2)、2隅とも空いている場合は⑤(⑤-1or⑤-2)と⑥(⑥-1or⑥-2)が、それぞれ破綻せず解をなすことができます。よってやはり上半分だけで2パターンの解が生じることになります。
下半分についても同様に作り、上下を貼り合わせます。やはり貼り合わせに際して破綻を生むことはありません。このようにして、6*9の場合も少なくとも4つの解を有する複数解となります。
橙部分は、※のマスが黒マスか否かで分かたれる。
図21,22で適当な位置に◇を挿入することにより、n≧11の場合も全て複数解となることが分かります。(証明終)
7*n
7*7,7*8の場合は図23のようにして構成できます。例によって...
7*7：作：鷹野リン様 https://puzsq.logicpuzzle.app/share/110596
7*8：作：かんれいと様 https://puzz.link/p?shakashaka/7/8/h.h.g.l.k.l..r..n.h.g、90°回転
<命題3> 7*n盤面で唯一解となる配置が存在するのは、n=7,8のときに限られる。
<命題3の証明> まず命題2の6*nの場合と同様、n=9,10で唯一解にならないことを示していきます。実のところ、この記事で最も難しいのはここです。
n=10のとき、まず長辺を二分し、左右で解を構成します。埋まっている隅の数で場合分けすると図24のようになります。
図24に従って左右半分の解を作り貼り付けます。貼り付けに際してやはり破綻は生じませんので、これによって少なくとも1つの解が見つかります。BとCのパターンは2つの解を持つことを踏まえると、左右いずれかがBやCであれば、言い換えると1つでも空いている隅があれば複数解が確定します。
1隅埋の場合、②と③(③-1~③~3)で複数解。2隅空も同様。
③は橙部分の状況によって場合分けされる。
そこで、4隅とも埋まっている場合に2つ目の解を探します。
図25左の青領域A1,A2に注目します。A1,A2のうち少なくとも一方が全て白マスならば、図21右のように別解が見つかります。
A2も同様。
そうでない場合、図26左を考えます。図26左の中央部は置いておいて、周辺部は黒マスの状況に関わらず破綻しないように解くことが可能です(これはA1,A2の全ては白マスではないことから従います)。そうして出来た図26中の橙マスを埋めるように、周囲の四角を「上手く」延長して図26右のような解を得ます。
ここで橙マスが両方とも「上手く」埋められることは次のように示せます。図27左①において、Bが含まれる長方形は図27中列②1~3のいずれかの形状になりますから、橙マスのうち少なくとも一方に伸ばすことが可能です。これはEについても同様ですから、もしBとEで橙マス両方を埋められないとすれば図27右上③(または鏡像)の形状になる必要がありますが、この場合は図27右下④のようにしてAかDが伸ばせます。すなわち周囲の形状に関わらず、図27の橙マスを埋める操作は可能です。
以上より、7*10ではどの配置でも複数解となります。
続いて7*9の場合、盤面を幅3:6に分割し、それぞれを図28のように隅の埋/空で場合分けします。これまでと同様に左右で破綻することなく配置が可能で、左右の貼り付けでも破綻しませんから、1つの解が見つかります。しかし逆に幅6:3で分割した際にも解が生じます。こうして出来た2つの解は中央部で衝突し両立できませんので、複数解となります。
②-1or2、③-1or2は図中橙マスの白黒に対応する。
④の中央部は7*10の時と同様に「上手く」伸ばせる。
⑤は、右辺の橙部分に黒マスがない場合⑤-1、下辺の橙部分に黒マスがない場合⑤-2、いずれにも黒マスがある場合は⑤-3を選択する。
最後に一般のnについて考えます。nが11以上の奇数の場合は、図29左のように配置することで7*9のときと同様に示せます。nが12以上の偶数でかつ四隅が1箇所でも空いていれば、これも図29右のように7*10のときと同様に示せます。
右：7*10の5:5分割に橙色の2列を好きなだけ追加する
nが12以上の偶数でかつ四隅が全て埋まっている場合は次のようにします。図30左①が第一の解となります。もし図中A1かA2が2マスとも白マスならば図30右上②(または鏡像)の別解が生じますし、そうでないなら図30右下③が別解となります。橙部分はいくらでも増やせますので、12以上の全ての偶数nに対して複数解となります。
A1,A2の状況に応じて②か③がその別解となる。
以上で7*nの場合が網羅できました。(証明終)
9*n
結論から言えば...
<命題4> 9*n盤面は複数解である。
<命題4の証明> まず盤面を図31のように分割します。
図31の青/赤/橙/緑部分は、いずれも隅の3×3領域から2×kの長方形が伸びた格好になっています。これらは図32のように埋めることができます。長方形部分の長さkの偶奇(つまり盤面の幅の偶奇)と隅の埋/空によって4パターンを用意します。いずれも橙部分は0個以上くっつけて繰り返し構造をなします。
①,③は辺の長さが偶数、②,④は奇数の場合。
④-1,2は赤マスの白黒で分岐。
これを使って埋めると、周辺部は破綻せず、中央部に3*(n-6)の長方形(と図32②に由来する突起)が残ります。中央部は図33のように複数解になることが確かめられます。(証明終)
①9*9、②9*11以上の奇数、③9*10以上の偶数。
9*nの証明は、m*n(m,n≧8)の場合にも容易に適用できます。
まとめ
以上より、与えられたm*n(m≦n)サイズの盤面に対して唯一解となる配置が存在するのは、
(m,n)=(1,n),(2,n),(3,n),(4,4)~(4,12),(4,14),(5,n),(6,6),(6,7),(6,8),(7,7),(7,8)
の場合に限られます。
構成的に進めたため、冗長な部分が多々あるかと思います。証明に穴がありましたらご一報ください。
