¿Cuántas situaciones de juego diferentes han conectado cuatro?

Question

En el juego conectar cuatro con un $7 \times 6$ como en la imagen de abajo, ¿cuántas situaciones de juego pueden ocurrir?

Reglas :

Conecta Cuatro [...] es un juego para dos jugadores en el que los jugadores primero elegir un color y luego tomar turnos dejando caer discos de color desde la parte superior en una cuadrícula de siete columnas y seis filas suspendida verticalmente. Las piezas caen directamente hacia abajo, ocupando el siguiente espacio disponible dentro de la columna. El objetivo del juego es conectar cuatro de los propios discos del mismo color uno al lado del otro verticalmente, horizontalmente, o ...en diagonal ante su oponente.

Fuente: Wikipedia

Fuente de la imagen: http://commons.wikimedia.org/wiki/File:Connect_Four.gif

Límite inferior :

$7 \cdot 6 = 42$ ya que es posible llenar la parrilla sin ganar

Límite superior :

Cada campo de la red puede tener tres estados: Vacío, disco rojo o amarillo. Por lo tanto, podemos tener $3^{7 \cdot 6} = 3^{42} = 109418989131512359209 < 1.1 \cdot 10^{20}$ situaciones de juego al máximo.

No hay mucho menos que eso, porque no puedes tener cuatro amarillos seguidos en la parte inferior, lo que hace que $3^{7 \cdot 6 - 4} = 1350851717672992089$ situaciones imposibles. Esto significa que un mejor límite superior es $108068137413839367120$

¿Cuántas situaciones hay?

Creo que podría ser posible calcular esto con el enfoque de restar todas las combinaciones imposibles. Así que podría tratar de encontrar todas las combinaciones posibles para colocar cuatro en una fila / columna / verticalmente. Pero supongo que habría muchas combinaciones más de una vez.

Answer 1

El número de situaciones posibles de juego de Conecta-Cuatro después de $n$ capas ( $n$ vueltas) se tabula en OEISA212693 . El total es de 4531985219092. Se puede encontrar una explicación más detallada en los enlaces proporcionados por el sitio de la OEIS. (Por ejemplo El parque infantil Connect Four de John )

Answer 2

Así que he trabajado en ello, pero no estoy realmente cualificado para hacerlo. Primero quería calcular todas las posibilidades como 7 y luego 49 y luego era complicado para evitar redundancias y me enfrentaba a otro problema, el hecho de que después de 6 piezas jugadas, había una posibilidad de tener una columna completa. Demasiado difícil para mí. Así que decidí calcular todos los posibles tableros completos de 21 0 y 21 1. Encontré 538257874440 posibilidades, pero, en primer lugar no estaba teniendo en cuenta el tablero ganador. Y el hecho de que no es posible tener las dos primeras líneas llenas de un tipo de pieza. Así que pensé que no estaba tomando el buen camino, ya que era sólo el tablero completo, inútil. Finalmente tuve una buena idea. Tomando una columna sola con 0 1 y 2, por lo que hizo 3^6 posibilidad entonces sólo tenía que restar el que tiene 0 a la derecha de otro número (cuestión de la gravedad) y no era tan difícil : 0000000, 0000001, 0000002, 0000011, 0000012 ,000021 ,0000022 ,0000111 ,0000112, 0000121, 0000122, 0000211, 0000212, 0000221, 0000222 Si no ves una paternidad, es 1 luego 2 luego 4 luego 8... , lo que nos da 2^0 + 2^1 ... + 2^6 = 2 ^7 - 1 = 127 posibilidad para una columna, lo que hace 127^7 = 532875860165503 tablero posible. Luego me di cuenta de que seguía habiendo el mismo problema con las dos líneas del principio y el tablero ganador. Así que me rendí.

Answer 3

Creo que:

"Cada campo de la parrilla puede tener tres estados: Vacío, disco rojo o amarillo. Por lo tanto, podemos tener (...) situaciones de juego como máximo".

no es correcto.

La razón es que al captar que cada celda puede tener 3 estados, estamos permitiendo discos "flotantes" en el tablero, y las reglas del juego (y la física :) restringen que los discos estén apilados.

Es decir, el estado "vacío" debe estar siempre "llenando" cualquier número de discos en la columna, y cada disco debe residir sobre otro disco, además de la fila cero.

Por lo tanto, el "Límite superior", tal y como se ha definido, es inferior en una buena parte ( https://oeis.org/A212693/b212693.txt parece ser como una buena respuesta)...