First, consider any proper \(3\)-coloring of the grid. Let’s denote the color of the cell \((i, j)\) as \(c_{i, j}\).

Then, we can construct an integer matrix \(a\) with same dimensions, with the following conditions:

• For every \(1 \le i, j \le N\), \(a_{i, j} = c_{i, j} \bmod 3\).

• Numbers in any two adjacent cells in \(a\) differ exactly by \(1\).

In fact, after we fix \(a_{1, 1}\), there is a unique such matrix \(a\). Just go over rows, and set the values in the cells one by one, depending on the values in the neighbor cells. It’s easy to see that these values would be consistent. Indeed, if the cell has only \(1\) neighbor with an already set value, there can’t be any inconsistency; otherwise, it’s \((i, j)\) with \(i, j\ge 2\). If \(a_{i-1, j} = a_{i, j-1}\), then there is no inconsistency, otherwise we have \(|a_{i-1, j} - a_{i, j-1}| = 2\), implying that the colors \(c_{i-1, j}\) and \(c_{i, j-1}\) are different, and so the colors in \(c_{i-1, j-1}, c_{i, j}\) are the same, so just set \(a_{i, j} = a_{i-1, j-1}\).

Note that from the colors on the border, after fixing \(a_{1, 1}\), we can uniquely determine all the values on the border by setting them one by one, going clockwise. Note that if the value that we have to set in \(a_{2, 1}\) won’t match the value in the cell \(a_{1, 1}\), we can output NO already.

Note one more necessary condition now. The difference between the values of the cells doesn’t exceed the Manhattan distance between these cells. So, for every \(i\), we must have \(|a_{1, i} - a_{N, i}| \le N-1\) and \(|a_{i, 1} - a_{i, N}| \le N-1\).

It turns out that these conditions are sufficient! Indeed, for any \(1 \le i, j \le N\), just set \(a_{i, j} = max(a_{i, 1} - (j-1), a_{i, N} - (N-j), a_{1, j} - (i-1), a_{N, j} - (N-i))\). It’s clear that these values match on the border and that the values in the adjacent differ by exactly \(1\). Now we can just set \(c_{i, j} = a_{i, j} \bmod 3\).