¿Número de tarjetas NxN Takuzu válidas, también conocidas como 0h h1 (detalles en el interior)?

Question

Takuzu un rompecabezas de lógica que tiene un $N \times N$ rejilla llena de $0$ y $1$ 's siguiendo estas reglas:

1. Cada fila/columna tiene el mismo número de $0$ y $1$ 's

2. No hay dos filas/columnas iguales

3. No hay tres números adyacentes (los tres horizontales o los tres verticales) iguales

Para más detalles: Takuzu . También ha sido recientemente popular como el juego 0h h1

Me preguntaba cuántas tablas de tamaño $N \times N$ ( $N$ es incluso) son posibles?

Para cualquier impar $N$ es $0$ (Ya que se violaría la regla 1), Para $N=2$ Es decir, es $2$ es decir, las tablas $[01,10]$ y $[10,01]$ , Para $N=4$ Creo que es $72$ pero no estoy muy seguro, para cualquier otro $N$ No estoy seguro de cómo contarlos.

Answer 1

Este es un problema difícil y dudo que se haya estudiado seriamente. Sin embargo, mi ordenador me dice que para las primeras tablas se puede conseguir:

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

Después de eso mi algoritmo es demasiado lento para seguir adelante.

He buscado en OEIS alguna variación de esta secuencia pero no la he encontrado. Así que volví a comprobarlo con otro método y luego intenté introducirlo en la base de datos, momento en el que el sitio web me advirtió de que la secuencia ya estaba allí, ¡sólo que era demasiado reciente y aún no había sido aceptada! Casi con toda seguridad, está ahí porque has preguntado por el problema.

Me preocupaba robarle el protagonismo a alguien, pero ha pasado una semana y está publicado, así que aquí está: A253316 . Desgraciadamente, por el momento la respuesta a 10 x 10 sigue siendo un misterio.