　問題文において, 箇条書きで示された $3$ 条件をそれぞれ条件 $1$, 条件 $2$, 条件 $3$ と呼ぶ.\
　まず左上のマスに $1$ を入れる場合のみを考え, 一般に $8$ を $n$ としたとき, 題意をみたす数の書き込み方が $2^{n-1}-n$ 通りであることを数学的帰納法によって示す. $n=1,2$ のとき明らかに $0$ 通りである.\
　ある $k\geq 2$ について $n\leq k$ で成立を仮定する. $xy$ 平面上において, $0\leq x\leq k$ かつ $-1\leq y\leq 0$ なる格子点全体を頂点集合とし, 距離が $1$ または $\sqrt{2}$ である $2$ 点の間にすべて辺を張ったグラフを $V$ とする. このグラフにおける原点 $(0,0)$ を始点とするハミルトン路は, 条件 $1$ をみたす数字の書き込み方と一対一に対応する. したがって, このようなハミルトン路であって, 条件 $2$ および条件 $3$ をみたすものの数を数えればよい\
　$2$ 番目の頂点が $(0,-1)$ であるとき, 次の頂点は $(1,-1)$ でなければならず, このとき $n=k$ の場合に帰着される. $2$ 番目の頂点が $(1,0)$ または $(1,-1)$ であるとき, $x=k-1$ なる点に到達するまでは $x$ 座標を $1$ ずつ増やし続けるような任意の経路をとれ, 残りの頂点については条件 $1$ および $3$ をみたすハミルトン路が一意に定まる. ここで, 条件 $2$ をみたさないものがちょうど $1$ 通り存在するので, これを除外する. 以上より, 求めるハミルトン路の数は
　　$$(2^{k-1}-k)+(2^{k-1}-1)=2^k-(k+1)$$
通りであるから, $n=k+1$ でも成立する.\
　同様にして, $(0,0)$ を始点とし, かつ条件 $2$ を無視したものは $2^{n-1}$ 通りあることがわかる.\
　以下, グラフ $V$ を用いた表現を引き続き用いる. このとき, 対称性より $m=1,2,3$ について $(m,0)$ を始点とするものを数えれば十分である. $0\leq x\lt m$, $m\lt x\leq 7$ なる頂点全体をそれぞれ**左領域**, **右領域**と呼ぶ.\
　まず左領域を辿るとき, この範囲では条件 $2$ を無視すれば上と同様に $2^{m-1}$ 通りであり, 特に条件 $2$ をみたさないものは $1$ 通りである. 続いて, $(m,-1)$ から $(m+1,0)$ と進む場合, 残りは上と同様に $2^{5-m}$ 通りである. $(m+1,-1)$ と進む場合は, 条件 $2$ を無視すれば $2^{6-m}$ 通りであり, 特に条件 $2$ をみたさないものは $7-m$ 通りである. 以上より, まず左領域を通り, かつすべての条件をみたすものの個数は, 以下で与えられる.
　　$$2^{m-1}\times(2^{5-m}+2^{6-m})-1\times(7-m)=41+m$$
　同様に, 右領域を先に通る場合も $48-m$ 通りだが, $m=1$ の場合のみ $31$ 通りであることに留意せよ.\
　以上より, 求める場合の数は $M=4\times(120+73+2\times89)=\textbf{1484}$ である.
公式解説
https://onlinemathcontest.com/contests/omc016/editorial/105
　$2\times 8$ のマス目の各マスに, $1$ 以上 $16$ 以下の整数をそれぞれ $1$ つずつ, 以下の条件をみたすように重複なく書き込みます. 

- $1$ 以上 $15$ 以下の任意の整数 $k$ について, マス $k$ とマス $k+1$ は頂点を共有する.
- $1$ 以上 $15$ 以下のある整数 $l$ が存在し, マス $l$ とマス $l+1$ は頂点のみを共有する.
- $1$ 以上 $14$ 以下の任意の整数 $m$ について, マス $m$ とマス $m+2$  は辺を共有しない.

　このとき, 数の書き込み方は $M$ 通りあります. $M$ を解答してください. 

　ただし, ここで $X$ の入ったマスをマス $X$ と呼び, 数字を書き込む向きは考えず, 回転したり裏返したりして一致する書き込み方も異なるものとして考えるものとします.