　四隅の $1$ マスのみでパズルを構成するもの $4$ 通りを先に除外しておく．\
　以下，各マスを白黒で塗り分け，各色がパズルをなすようにする問題と解釈する．ただし，このままでは同じ配置を二重に数えてしまうため，以下ではその重複を除きながら数え上げていく．\
　図のように，赤色で示された辺に $a_1$ から $a_{12}$ までの記号を与える．また，青色で示した $4$ マスを**内部**とよび，残りの $12$ マスを**外縁**とよぶ．$2$ つのパズルの境界はひとつながりの線となるから，赤色の $12$ 辺について，パズルの境界となるのは $0$ 本または $2$ 本である．\
　$0$ 本のとき，外縁はすべて同じ色である（黒としてよい）．このとき，内部は「すべて黒」「隣り合わない $2$ マスずつが同じ色」を除いて自由に塗れるから，全部で $13$ 通り存在する．以下，赤色の辺のうち $2$ 本が境界となる場合を考え，その $2$ 本の選び方を ${}\_{12}\mathrm{C}\_{2}-4=62$ 通りから一つ固定する（最後の $-4$ は冒頭の除外に基づく）．\
　内部の $4$ マスのうち，黒がいくつあるかで場合分けする．黒が $2$ つ以上であるとしてよい．

* $4$ マスとも黒い場合：\
　外縁の塗り方はつねに $2$ 通りずつ存在するから，$2\times 62=124$ 通り．
* $3$ マスが黒い場合（左上のみが白として，$4$ 倍すればよい）：\
　$a_{12},a_1$ から $1$ つ，$a_3, a_4, \ldots, a_{10}$ から $1$ つ選ぶときは外縁の塗り方は $2$ 通り，それ以外は $1$ 通りずつ存在するから，$2\times 16 + 46=78$ 通り．
* 隣り合う $2$ マスずつが同色の場合（左側が黒として，$2$ 倍すればよい）：\
　$a_{12},a_1,a_2, a_3, a_4$ から $1$ つ，$a_6, a_7, \ldots, a_{10}$ から $1$ つ選ぶときは外縁の塗り方は $2$ 通り，それ以外は $1$ 通りずつ存在するから，$2\times 25+37=87$ 通り．
* 隣り合わない $2$ マスずつが同色であるようにすることはできない．

　以上より，求める答えは $4+13+124+78\times 4+87\times 2 = \bf{627}$ 通りである．

![figure 1](\/images\/l0eho0g49vPz8ehgbiyEgFpiKDzoCCJFY615Scjx)
公式解説
https://onlinemathcontest.com/contests/omc172/editorial/4423
　おそらく様々な数え上げの方法があると思います．公式解説と異なる方法を書いておきます．\
　公式解説と同じように，各マスを白黒で塗り分け，各色がパズルをなすようにする問題と解釈します．また，$4×4$ のマス目について，$x$ 行 $y$ 列目のマスを $(x,y)$ と記すことにし，$(2,2),(2,3),(3,2),(3,3)$ の $4$ 点を**内部**，その他のマスを**外縁**と呼ぶことにします（内部・外縁については，公式解説と同じ表現です）．
___
（解１）内部に注目して数え上げる方法
- 内部の $4$ マスが全て同色の場合（黒とする）\
　黒が外縁のうち $0$ マスを塗る方法は $1$ 通り，$1$ マスを塗る方法は $8$ 通り，$2$ ～ $11$ マスを塗る方法はそれぞれ $12$ 通り存在する．よって，$1+8+10×12=\underline{129}$ 通り．
- 内部の $3$ マスが同色の場合．$3$ マスは黒とし，残りの $1$ マスは $(2,2)$ とする（最後に $4$ 倍しなければならない点に注意）．\
　$(1,2),(2,1)$ の $2$ マスが白か否かでさらに場合分けをする． \
　$2$ マスとも白である場合．$(1,1)$ は白で確定する．残りのうち， $9$ マスが黒である場合から $0$ マスが黒である場合までを考えて，$1+2+3+4+5+6+7+8+6+1=43$ 通り．\
　$1$ マスだけ白である場合．$(1,2)$ が白とすると，$(2,1)$ が黒である．$(1,1)$ の塗り方は $2$ 通りあり，その他の塗り方は $9$ 通りある（$(1,3)$ から$(3,1)$ まで，白がどこまで進めるかと考えればよい）．よって，$2×9×2=36$ 通り．\
　$0$ マスが白である場合．自明な $1$ 通りのみ．\
　以上をまとめて，$(43+36+1)×4=\underline{320}$ 通り．
- 内部が $2$ マス／$2$ マスと分かれる場合．$(2,2),(2,3)$ が白であるとする（最後に $2$ 倍しなければならない点に注意）．\
　$(2,1),(2,4)$ の $2$ マスが白か否かでさらに場合分けをする． \
　$2$ マスとも白である場合は，$(1,k)$ は全て白である．残りのうち， $6$ マスが黒である場合から $0$ マスが黒である場合までを考えて，$1+2+3+4+5+4+1=20$ 通り．\
　$1$ マスだけ白である場合．$(2,1)$ が白とすると，$(2,4)$ が黒である．$(1,k)$ の塗り方は $5$ 通りあり，$(3,1),(4,k)$の塗り方は $6$ 通りある．$5×6×2=60$ 通り．\
　$0$ マスが白である場合．$(2,1),(2,4)$ が黒で，$(3,k),(4,k)$ は全て黒である．$(1,k)$ の塗り方は $9$ 通り．\
　以上をまとめて，$(20+60+9)×2=\underline{178}$ 通り．

　以上で全ての場合を網羅したので，あとは足し合わせればよい．$129+320+178=\mathbf{627}$ 通り．
___
（解２）外縁に注目して数え上げる方法\
　外縁が $k$ マス／$12-k$ マスと分かれる場合（ $k$ マスの方を黒とする）を $0≦k≦6$ の範囲で考えていく．$1≦k$ の範囲では，外縁の塗り分け方は，適当な回転・反転を考えることで，本質的に $2$ 通りに帰着される点に注意せよ．
- 外縁のうち $0$ マスが黒である場合\
　内部について考えると，$\underline{13}$ 通り．
- 外縁のうち $1$ マスが黒である場合\
　$(1,1)$ が黒の場合，この $1$ 通りのみである．$(1,2)$ が黒の場合，内部は $8$ 通り考えられる．\
　よって，$4×1+8×8=\underline{68}$ 通り．
- 外縁のうち $2$ マスが黒である場合\
　$(1,1)$ 含む $2$ マスが黒の場合，内部は $8$ 通り考えられる．そうでない場合，内部は $11$ 通り．\
　よって，$4×11+8×8=\underline{108}$ 通り．
- 外縁のうち $3$ マスが黒である場合\
　$4×8+8×11=\underline{120}$通り．
- 外縁のうち $4$ マスが黒である場合\
　$4×11+8×10=\underline{124}$通り．
- 外縁のうち $5$ マスが黒である場合\
　$4×12+8×10=\underline{128}$通り．
- 外縁のうち $6$ マスが黒である場合\
　$2×9+4×12=\underline{66}$通り．

　以上で全ての場合を網羅した．$13+68+108+120+124+128+66=\mathbf{627}$ 通り．
ユーザー解説
https://onlinemathcontest.com/contests/omc172/editorial/4423/263
　$4\times 4$ のマス目において，$1$ つ以上のマスからなる集合 $P$ が**パズル**であるとは，次の条件をみたすことをさします：

* 任意の相異なる $P$ の $2$ マスの間を，隣接する $P$ に属するマスをいくつか辿って移動できる．ただし，$1$ マスのみからなる集合はパズルであるとする．

全部で $16$ 個のマスを $2$ つの空でない集合に分割する方法（順序は区別しない）であって，分割された集合のいずれもがパズルとなるものは何通りありますか？ただし，回転したり裏返したりして一致するものも区別するものとします．

<details>
<summary>集合の分割とは・パズルの分割の例<\/summary>
　$2$ つの空でない集合 $P_1, P_2$ が集合 $G$ の**分割**であるとは，
$$ P_1 \cap P_2 = \empty, \quad P_1 \cup P_2 = G$$
がともに満たされることをさします．\
　たとえば，下図左のようなマス目の分割は，灰色のマス・白のマスの集合がともにパズルであるため，問題文の条件を満たしますが，下図右のようなマス目の分割は，灰色のマスからなる集合がパズルでないため，問題文の条件を満たしません（なお，白のマスからなる集合もパズルではありません．条件をみたすには，分割後の集合の**両方**がパズルとなることが必要であることに注意してください）．

![figure 1](\/images\/PHISm81wsnztBlRpUA2YjGnXQzJm2OOl3l0EHt2E)
<\/details>