Number of valid NxN Takuzu Boards a.k.a 0h h1 (details inside)?

Question

Takuzu a logic puzzle which has a $N \times N$ grid filled with $0$'s and $1$'s following these rules:

1. Every row/column has equal number of $0$'s and $1$'s

2. No two rows/columns are same

3. No three adjacent (all three horizontal or all three vertical) numbers are same

For more details: Takuzu. It has also been recently popular as the game 0h h1

I was wondering how many number of boards of size $N \times N$ ($N$ is even) are possible?

For any odd $N$ it's $0$ (Since rule 1 would be violated), For $N=2$, it is $2$, i.e the boards $[01,10]$ and $[10,01]$, For $N=4$, I think it is $72$ but I'm not pretty sure, For any other $N$ I'm not sure how to count them.

Answer 1

This is a hard problem and I doubt it's been studied seriously. However, my computer tells me that for the first few boards, you can get:

• 2 x 2 ... 2
• 4 x 4 ... 72
• 6 x 6 ... 4,140
• 8 x 8 ... 4,111,116

After that my algorithm is too slow to keep going.

I searched on OEIS for any variation of this sequence but couldn't find it. So I double-checked with a different method and then tried to type it into the database, at which point the website warned me that the sequence was already there — it was just too recent and hadn't been accepted yet! Almost certainly, it's there because you asked about the problem.

I was worried about stealing somebody's thunder, but it's been a week, and it's published, so here it is: A253316. Unfortunately, at the moment the answer for 10 x 10 is still a mystery.