まず、盤面を意図通りに \(3\) 色で塗る任意の方法を考えます。マス \((i, j)\) の色を \(c_{i, j}\) と表します。

すると、同じサイズの整数行列 \(a\) であって、次の条件を満たすものを構成できます。

• すべての \(1 \le i, j \le N\) について、\(a_{i, j} = c_{i, j} \pmod 3\) である。
• \(a\) の中のどの二つの隣接する数も、ちょうど \(1\) 異なる。

実は、\(a_{1, 1}\) を固定すると、このような行列 \(a\) は一意に定まります。行を順に見ていき、要素の値を一つずつ、隣接する要素の値に基づいて設定していきましょう。このとき、値に不整合が生じないことが容易にわかります。実際、すでに値の定まった隣接要素が一つしかない場合には、不整合は生じようがなく、そうでない場合は \(i, j\ge 2\) であるような \((i, j)\) に限られます。もし \(a_{i-1, j} = a_{i, j-1}\) であれば、やはり不整合は生じず、そうでなければ \(|a_{i-1, j} - a_{i, j-1}| = 2\) であり、これは色 \(c_{i-1, j}\) と \(c_{i, j-1}\) が異なることを意味し、従って色 \(c_{i-1, j-1}\) と \(c_{i, j}\) は同じであり、\(a_{i, j} = a_{i-1, j-1}\) とできます。

盤面の最も外側の色を用いると、\(a_{1, 1}\) を固定すれば、行列の最も外側の要素を時計回りに一つずつ決めていくことで特定できることに注意します。もし \(a_{2, 1}\) に入れることになる値が \(a_{1, 1}\) の値と合わない場合は、この時点で答えを NO とできます。

必要条件がもう一つあります。要素の値の間の距離は、それらの要素の位置の間のマンハッタン距離を超えてはなりません。従って、すべての \(i\) について、\(|a_{1, i} - a_{N, i}| \le N-1\) かつ \(|a_{i, 1} - a_{i, N}| \le N-1\) でなければなりません。

実は、これらの必要条件で十分です。実際、すべての \(1 \le i, j \le N\) に対して、\(a_{i, j} = \max(a_{i, 1} - (j-1), a_{i, N} - (N-j), a_{1, j} - (i-1), a_{N, j} - (N-i))\) とすることができます。これらの値が最も外側で定めた値と合い、また隣接する値がちょうど \(1\) 異なることは明らかです。すると、\(c_{i, j} = a_{i, j} \bmod 3\) とできます。