36-length snake in a 6x6 grid

Based on https://brilliant.org/weekly-problems/2017-05-29/advanced/?p=4

We need to fill a 6x6 grid using the numbers 1-36, each cell having a single unique number, such that:

• Every two consecutive numbers lie in cells that share an edge.


• No two cells that share an edge or a vertex exist that both contain multiples of 4.

I found a solution for this. Highlighting the cells with multiples of 4 gives

x x x x x #
# x # x x x
x x x x x #
# x # x x x
x x x x x #
# x # x x x

as pointed out by a user there. Can someone prove why any valid solution to this question causes the multiples of four to form the above arrangement, or else find a solution where they don't.

P.S. Consider looking at the solution to the original question first.

Answer

Yes, this solution is unique, except obviously for mirroring and rotations.

Now the explanation is a bit long and not spoilered, proceed at your own risk. There might be a simpler formulation too.

We can safely ignore odd numbers and consider just even ones for now. We get a checkerboard pattern. We can easily see that half of the pattern is multiple of just 2 (not 4) and other half is multiple of 4 = 9 each. Now we need to place those multiple of 4 in such a way they don't touch diagonally. Lets consider 2 rows at a time, and in those rows just the checkerboard spots. So in the first 2 rows you have 6 spaces for 4 or 2. You can easily see you cannot fit more than 3 of 4, so you need to fit 3 to squeeze in all 9 in these 3 pairs of rows.

There are just 2 distinct options you have (note that 4 above prevents 4 down and down-right):

1:

4 4 4
2 2 2

2:
2 2 4
4 4 2

(there are also 2 4 4; 4 2 2 and 2 2 2; 4 4 4, but end up being the same as 1 and 2)

Now repeat this 3 times. This time 4 above prevents it down and down-left. Pretty obviously if you pick pattern 1 on top you can continue with either of 1 or 2; 2 can be continued by 2. So you end up with the following possible sequences for the rows:

111, 112, 122, 222

On the quick glance it seems just 111 and 222 are really distinct. 222 was proposed as the solution. Can we make it work with 111 too? Let's go back to the original square and mark 2s and 4s in it (.s are odd, which we continue ignoring).

.4.4.4
2.2.2.
.4.4.4
2.2.2.
.4.4.4
2.2.2.

We see that 4 must be preceded by 2 and followed by 2, except for one 4 which isn't followed by 2 - number 36. So, this last number needs to be in the top right corner, which has just one 2 that can be reached, which is then 34. OK, but now the problem is the middle 4 on the top and right. Both of those 4s have just one own 2 and share another 2 among them - the one with 34 on it. So you can make it work for one of them, not both. This means you cannot put 4s in the 111 pattern.