1

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.

introducir la descripción de la imagen aquí introducir la descripción de la imagen aquí

1
  • ¿por qué el tag python-3.x? Yo diría que se trata más bien de un problema de combinatoria que de programación.
    – abulafia
    Commented el 29 may. 2018 a las 7:21

1 respuesta 1

1

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:

  • Combinaciones que ganarían en vertical. Éste es bastante trivial, pues cada columna tiene 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 horizontal. Es análogo al anterior, pero cambiando filas por 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:

    • Casos en la diagonal principal, considerando ésta la que comienza en la esquina superior izquierda. Si la longitud de esta diagonal es 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.

    • Casos en la mitad inferior. Es análogo a lo anterior, pero cambiando filas por columnas.

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
1
  • @@abulafia, su análisis corrobora el mío, precisamente esas fueron las posibles combinaciones que me dieron para filas, columnas y diagonales, fila = 1 ==> 0, 1, 2, 3, 4, 5, 6 , fila = 2 ==> 7, 8, 9, 10, 11, 12, 13 y no la coordenada como tal, ejemlo: def verificar(): if (t[0] == "X" and t[1]== "X" and t[2]=="X") or (t[3] == "X" and t[4] == "X" and t[5] =="X") or (t[6] == "X" and t[7] == "X" and t[8] == "X"): bloquear() messagebox.showinfo("Ganador","Ganaste jugador"+str(jugador1)) . De todas maneras su evaluación confirma mi análisis. Commented el 29 may. 2018 a las 15:10

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.