Hice un combinación de posibilidades y me dan 60, haciendo las posibles combinaciones por columnas, filas y diagonales.
Deseo tener la certeza de cuantas combinaciones posibles dan para que alguien gane 5 en línea en una matriz de 7x7.
El problema puede descomponerse en tres cálculos, y generalizarse a cualquier valor de n
(número de fichas a colocar en línea para ganar), filas
y columnas
(dimensión del tablero).
Esta sería la descomposición:
filas-n+1
posibilidades (en tu caso sale 3 combinaciones ganadoras por columna). Basta multiplicar esto por el número de columnas.Combinaciones que ganarían en diagonal. Este es más complicado, pero básicamente tenemos diagonales "directas" (Noroeste-Sureste) y diagonales "inversas" (Suroeste-Noreste). Por simetría, ambos casos tendrán el mismo número de combinaciones, por lo que basta resolver uno de ellos y multiplicar por dos.
Vamos por ejemplo con las diagonales directas (Noroeste-Sureste). Este caso puede descomponerse en tres sub-problemas para que sea más fácil de analizar:
L
, tendremos L-n+1
casos ganadores en ella. En tu ejemplo L=7
y n=5
, lo que nos da 3 casos. En general L=min(filas, columnas)
.Casos en la mitad superior. La diagonal anterior divide el tablero en dos mitades. ¿Cuántos casos ganadores en diagonal hay en la mitad superior? Tenemos que ir considerando sucesivamente los casos en los que la primera ficha esté a distancia 1, 2, etc. de esa diagonal, y ver qué longitud tiene la correspondiente "paralela" a la diagonal. En cada iteración se puede imaginar que estamos jugando sobre un tablero menguado, que tiene 1, 2, etc. columnas menos.
No necesitamos examinar todos los casos, sino sólo los columnas-n+1
primeros (pues a partir de él ya no habrá sitio en diagonal para colocar n
fichas. El algoritmo es, para cada casilla de inicio i
=1, 2, ..., columnas-n+1
calcular la longitud L
de la paralela a la diagonal correspondiente (su longitud será min(filas, columnas-i)
, según la interpretación del "tablero menguado"), y el número de combinaciones ganadoras sobre esa recta será L-n+1
.
Así que ya tenemos todos los ingredientes. Escribamos funciones separadas para cada uno de los tres casos:
def ganar_en_vertical(n, filas, columnas):
return (columnas-n+1)*filas
def ganar_en_horizontal(n, filas, columnas):
return (filas-n+1)*columnas
def ganar_en_diagonal(n, filas, columnas):
L = min(filas, columnas)
en_diagonal_principal = L - n + 1
mitad_superior = 0
for i in range(1, columnas-n+1):
L = min(filas, columnas-i)
mitad_superior += L - n + 1
mitad_inferior = 0
for i in range(1, filas-n+1):
L = min(filas-i, columnas)
mitad_inferior += L - n + 1
# Para hacer más sencilla la depuración devuelvo los tres
# valores separados en lugar de su suma
return en_diagonal_principal, mitad_superior, mitad_inferior
Probemos qué sale en tu caso:
>>> ganar_en_horizontal(5, 7, 7)
21
>>> ganar_en_vertical(5, 7, 7)
21
>>> ganar_en_diagonal(5, 7, 7)
3, 3, 3
Los resultados tienen buena pinta y coinciden con lo que se puede intuir dibujando el tablero. En el último caso los tres números que vemos serían las combinaciones ganadoras en diagonales NW-SE, respectivamente sobre la "diagonal principal", paralelas a ella en la mitad superior y paralelas a ella en la mitad inferior. Probando con un tablero de 7 filas y 8 columnas los números que salen son 3, 6, 3
, que también coinciden con lo que se puede ver sobre el papel.
Sólo queda el cómputo del total:
def combinaciones_ganadoras(n, filas, columnas):
return (ganar_en_vertical(n, filas, columnas)
+ ganar_en_horizontal(n, filas, columnas)
+ 2*sum(ganar_en_diagonal(n, filas, columnas)))
>>> combinaciones_ganadoras(5,7,7)
60
python-3.x
? Yo diría que se trata más bien de un problema de combinatoria que de programación.