aqre

数字のある領域のマス数の合計をmとする。mを出来るだけ少なくして唯一解問題にする。

合体して1領域にしても唯一解。

数字のない出来るだけ大きな長方形領域を入れ、唯一解問題にする。

この問題を応用すれば、数字のない領域を無制限に拡大可能。

上はいずれも、0を周囲2マス幅のみに配置した、唯一解問題である。

同様に、横幅を3マス、縦幅を6マスずつ順次拡大できる。

23x33の盤面に、ヒントマスが98マス入っている。

nxm盤面にヒントマス(2n+2m-14)マス入りである。

以下の機構は左上部分を確定させる。

盤面角や端に、数字のない出来るだけ大きな長方形領域を入れ、唯一解問題にする。

10x10に4x10空白 author:ぬーん 出題20221221掲載20230112

盤面に出来るだけ多く黒マスを入れる

黒マスが最大限入った解を構築するには、ほとんどの場合、どの1x4にも1マスだけ白マスが入っているようにすればよい。

盤面に出来るだけ少なく黒マスを入れる

最大値と比べ、最小値は複雑である。

author: Mitchell Lee

盤面サイズ縦m,横nを、ともに3以上の数とする。この盤面に入る黒マスの最小値を考察する。

以下引用

the minimum number of shaded cells in an mxn Aqre grid is between (2/5)mn - (3/5)(m+n+1) and (2/5)mn + (3/5)(m+n-3).

2章では具体的構成を延べ、(2/5)mn + (3/5)(m+n-3) マスの黒マスで足りることを示している。サイズによっては、さらに端の黒マスを数個減らすことができる場合があるが、mやnのオーダーでは減らないと考えられている。

3章では最低 (2/5)mn - (3/5)(m+n+1) マス必要であることを示している。黒マスどうしが横に隣り合っている場所の数に注目し、横に白マスが最大で3マスしか連続しないことから不等式を導く。縦でも同様に考察し、最後に黒マスのひとつながりルールから隣り合う場所の数の制限を検討して導いている。つまり、この評価は、黒マスが4連続しないという制約を用いず、白4連禁＋黒ひとつながりのみで導かれている。

4章では、3章の不等式の等号成立条件から、以下を示す（ペナルティaqre理論）。

盤面の黒マスの数は、ちょうど (2/5)mn - (3/5)(m+n+1) + P/5 マスになる。ただし、Pは以下で定義される。

P=2*r1+r2+3*se+6*sc+3g

r2を、横向きあるいは縦向きにちょうど2マスだけ白マスが連続している（その両隣が黒マスないし盤面外になっている）場所の数の合計とする。

r1を、横向きあるいは縦向きにちょうど1マスだけ白マスが連続している（その両隣が黒マスないし盤面外になっている）場所の数の合計とする。四方を黒に囲まれた1マスの白マスがあるときは、2回カウントする。

seを、盤面の辺上（四隅を除く）の黒マスの数とする。

scを、盤面の四隅の黒マスの数とする。

gを、a-s+1とする。sは黒マスの数。aは黒マス隣接箇所の数。黒マスでループが1つ出来るとgは1増える。

白マスは出来るだけ3連続していてほしいので、r1,r2が増えると損。また盤面端から3マス白マスがあってほしいので、端に黒マスがあると損であり、se,scが増えると損。黒マスをひとつながりにする最小限の隣接箇所を超えて、隣接箇所があると、「白マスが0連続している」ととらえられるので、gが増えると損。

また、端の黒マスが全くないと白マス4連禁に反するので、ペナルティを完全に回避することはできない。

以下の文章では、上の論文の結果を、わずかながら詰めていく。

2章(B)について、(B)の領域に入れる黒マスの数は、

(9/5)*(n-3) if n-3≡0 (mod 5)

(9/5)*(n-4)+3 if n-3≡1 (mod 5)

(9/5)*(n-5)+4 if n-3≡2 (mod 5)

(9/5)*(n-6)+6 if n-3≡3 (mod 5)

(9/5)*(n-7)+8 if n-3≡4 (mod 5)

であり、これらの値はいずれも (9/5)*n-21/5 を上回らない、とある。

しかし、実際には以下のような黒マスの入れ方が存在する。

https://gyazo.com/378fb921d5535ceda297af934c00067d

左上隅の1x1から始めて、盤面を拡大していくときに順次黒マスも置いていき盤面を右下方向へ広げていくイメージ。例えば、白抜き数字の6は、左上隅を含む6x6に黒マスを入れるときに初めて置く黒マスを表す。7,12,17が無いのは、黒マスを追加しないまま盤面を広げてもルールに反しない配置が得られるためである。よって、以下のようになる。

(9/5)*(n-3) if n-3≡0 (mod 5)

(9/5)*(n-4)+2 if n-3≡1 (mod 5)

(9/5)*(n-5)+4 if n-3≡2 (mod 5)

(9/5)*(n-6)+5 if n-3≡3 (mod 5)

(9/5)*(n-7)+5 if n-3≡4 (mod 5)

であり、これらの値は(9/5)*n-(k/5) (kは順に-27,-26,-25,-29,-38)だから、

いずれも(9/5)*n-25/5 を上回らない。

したがって盤面に入れる黒マスの数の合計は、最大でも

3+((9/5)*n-25/5)+((9/5)*m-25/5))+(2/5)*(m-3)(n-3)=(2/5)mn+(3/5)(m+n-3)-8/5

さらに、実際には「-25/5」は最悪の場合であるので、一辺の長さnが

n-3≡0,1,2,3,4 (mod 5) のとき、さらに-2/5, -1/5, -0, -4/5, -13/5 してよい。縦も同様。

（n≡0,1,2,3,4 (mod 5) のとき、さらに-0, -4/5, -13/5, -2/5, -1/5, してよい。）

4章について、盤面の黒マスの数は、ちょうど (2/5)mn - (3/5)(m+n+1) + P/5 マスで、P=2*r1+r2+3*se+6*sc+3g

であった。

端の列について、必ず発生するペナルティを加算する。

長さnマスの端の列には、少なくとも(n-3)/4マス黒マスが入る。さもなければ白マスが4連続する。

よってこの端の列だけ考えてもPに3*se=(3/4)*(n-3)加算される。他の端も同様で、合計

(3/2)*(m+n-6)加算。（scは列と行で3ずつ、合計6加算すると考えれば変わらないので、0としてよい。）

したがって、盤面の黒マスの数は、最少でも

(2/5)mn - (3/5)(m+n+1) + (3/10)*(m+n-6)

= (2/5)mn - (3/10)(m+n+8)

この値も、黒マス4連禁を考慮していない。

具体的なサイズについて。以下の表の一部は引用。

table: aqre number

Size(m*n) (2/5)mn - (3/10)(m+n+8) Minimum (2/5)mn + (3/5)(m+n-3)-8/5 -α

3*3 -0.6 0 3.8

4*4 1.6 7 7.8 7.4

5*5 4.6 9 12.6 12.6

6*6 8.4 13 18.2 16.6

7*7 13 15 24.6 19.4

8*8 18.4 27 31.8 31

9*9 24.6 33 39.8 39.4

10*10 31.6 41 48.6 48.6

11*11 39.4 47 58.2 56.6

12*12 48 〜61 68.6 63.4

-α は, （n≡0,1,2,3,4 (mod 5) のとき、さらに-0, -4/5, -13/5, -2/5, -1/5, してよい。）を適用。