Estudio de caso: el problema de la existencia de cuasigrupos

Algunos teoremas matemáticos se pueden resolver mediante exploración combinatoria. En este artículo nos centramos en el problema de la existencia de algunos cuasigrupos. Demostraremos la existencia o no existencia de algunos cuasigrupos utilizando nucs. NuCs es un solucionador rápido de restricciones escrito 100% en Python que actualmente estoy desarrollando como un proyecto paralelo. Se publica bajo el licencia MIT.

Comencemos definiendo algún vocabulario útil.

Grupos

Citando wikipedia:

En matemáticas, un grupo es un conjunto con una operación que asocia un elemento del conjunto a cada par de elementos del conjunto (como lo hace toda operación binaria) y satisface las siguientes restricciones: la operación es asociativa, tiene un elemento identidad y cada elemento del conjunto El conjunto tiene un elemento inverso.

El conjunto de números enteros (positivos y negativos) junto con la suma forman un grupo. Hay muchos tipos de grupos, por ejemplo las manipulaciones del cubo de rubik.

Fuente: Wikipedia

cuadrados latinos

Un cuadrado latino es un norte × norte matriz llena de norte símbolos diferentes, cada uno de los cuales aparece exactamente una vez en cada fila y exactamente una vez en cada columna.

Un ejemplo de un cuadrado latino de 3×3 es:

Diseñado por el autor

Por ejemplo, un Sudoku es un 9×9 Cuadrado latino con propiedades adicionales.

Cuasigrupos

una orden metro cuasigrupo es un cuadrado latino de tamaño metro. Es decir, un m×m tabla de multiplicar (notaremos ∗ el símbolo de multiplicación) en la que cada elemento aparece una vez en cada fila y columna.

La ley de la multiplicación no tiene por qué ser asociativa. Si es así, el cuasigrupo es un grupo.

En el resto de este artículo nos centraremos en el problema de la existencia de algunos cuasigrupos particulares. Los cuasigrupos que nos interesan son idempotentes, es decir aa=a para cada elemento a.

Además, tienen propiedades adicionales:

  • Los problemas QG3.m son cuasigrupos de orden m para los cuales (a∗b)∗(b∗a)=a.
  • Los problemas QG4.m son cuasigrupos de orden m para los cuales (b∗a)∗(a∗b)=a.
  • Los problemas QG5.m son cuasigrupos de orden m para los cuales ((b∗a)∗b)∗b=a.
  • Los problemas QG6.m son cuasigrupos de orden m para los cuales (a∗b)∗b=a∗(a∗b).
  • Los problemas QG7.m son cuasigrupos de orden m para los cuales (b∗a)∗b=a∗(b∗a).

A continuación, para un cuasigrupo de orden metronotamos 0,…, m-1 los valores del cuasigrupo (queremos que los valores coincidan con los índices de la tabla de multiplicar).

Modelos de cuadrados latinos

Modelaremos el problema del cuasigrupo aprovechando el problema del cuadrado latino. El primero viene en 2 sabores:

  • el ProblemaCuadradoLatino,
  • el LatinSquareRCProblema.

El LatinSquareProblem simplemente establece que los valores en todas las filas y columnas de la tabla de multiplicar tienen que ser diferentes:

self.add_propagators([(self.row(i), ALG_ALLDIFFERENT, []) for i in range(self.n)])
self.add_propagators([(self.column(j), ALG_ALLDIFFERENT, []) for j in range(self.n)])

Este modelo define, para cada fila i y columna jel valor color(i,j) de la celda. Lo llamaremos el color modelo. Simétricamente podemos definir:

  • para cada fila i y color dola columna columna(i,c): llamamos a esto el columna modelo,
  • para cada color do y columna jla fila fila(c,j): llamamos a esto el fila modelo.

Tenga en cuenta que tenemos las siguientes propiedades:

  • fila(c, j) = i <=> color(i, j) = c

para un determinado columna j, fila(., j) y color(., j) son permutaciones inversas.

  • fila(c, j) = i <=> columna(i, c) = j

para un determinado color do, fila(c,.) y columna(.,c) son permutaciones inversas.

  • color(i, j) = c <=> columna(i, c) = j

para un determinado fila i, color(yo, .) y columna(yo, .) son permutaciones inversas.

Esto es exactamente lo que implementa LatinSquareRCProblem con la ayuda del propagador ALG_PERMUTATION_AUX (tenga en cuenta que en mi también se usó una versión menos optimizada de este propagador). artículo anterior sobre el problema del viajante):

def __init__(self, n: int):
super().__init__(list(range(n))) # the color model
self.add_variables([(0, n - 1)] * n**2) # the row model
self.add_variables([(0, n - 1)] * n**2) # the column model
self.add_propagators([(self.row(i, M_ROW), ALG_ALLDIFFERENT, []) for i in range(self.n)])
self.add_propagators([(self.column(j, M_ROW), ALG_ALLDIFFERENT, []) for j in range(self.n)])
self.add_propagators([(self.row(i, M_COLUMN), ALG_ALLDIFFERENT, []) for i in range(self.n)])
self.add_propagators([(self.column(j, M_COLUMN), ALG_ALLDIFFERENT, []) for j in range(self.n)])
# row[c,j]=i <=> color[i,j]=c
for j in range(n):
self.add_propagator(([*self.column(j, M_COLOR), *self.column(j, M_ROW)], ALG_PERMUTATION_AUX, []))
# row[c,j]=i <=> column[i,c]=j
for c in range(n):
self.add_propagator(([*self.row(c, M_ROW), *self.column(c, M_COLUMN)], ALG_PERMUTATION_AUX, []))
# color[i,j]=c <=> column[i,c]=j
for i in range(n):
self.add_propagator(([*self.row(i, M_COLOR), *self.row(i, M_COLUMN)], ALG_PERMUTATION_AUX, []))

Modelo de cuasigrupo

Ahora necesitamos implementar nuestras propiedades adicionales para nuestros cuasigrupos.

La idempotencia se implementa simplemente mediante:

for model in [M_COLOR, M_ROW, M_COLUMN]:
for i in range(n):
self.shr_domains_lst[self.cell(i, i, model)] = [i, i]

Centrémonos ahora en QG5.m. Necesitamos implementar ((b∗a)∗b)∗b=a:

  • esto se traduce en: color(color(color(j, i), j), j) = i,
  • o equivalente: fila(i, j) = color(color(j, i), j).

La última expresión establece que el color(j,i)ésimo elemento de la jth la columna es fila(i,j). Para hacer cumplir esto, podemos aprovechar el propagador ALG_ELEMENT_LIV (o un ALG_ELEMENT_LIV_ALLDIFFERENT más especializado optimizado para tener en cuenta el hecho de que las filas y columnas contienen elementos que son todos diferentes).

for i in range(n):
for j in range(n):
if j != i:
self.add_propagator(
(
[*self.column(j), self.cell(j, i), self.cell(i, j, M_ROW)],
ALG_ELEMENT_LIV_ALLDIFFERENT,
[],
)
)

De manera similar, podemos modelar los problemas. QG3.m, QG4.m, QG6.m, QG7.m.

Tenga en cuenta que este problema es muy difícil ya que el tamaño del espacio de búsqueda es mᵐᵐ. Para metro=10esto es 1e+100.

Los siguientes experimentos se realizan en una MacBook Pro M2 con Python 3.13, Numpy 2.1.3, Numba 0.61.0rc2 y NuCS 4.6.0. Tenga en cuenta que las versiones recientes de NuCS son relativamente más rápidas que las anteriores desde que se actualizaron Python, Numpy y Numba.

Las siguientes pruebas de existencia/no existencia se obtienen en menos de un segundo:

Experimentos con instancias pequeñas.

Centrémonos ahora en QG5.m sólo donde está el primer problema abierto QG5.18.

Experimentos con QG5 (en la segunda línea usamos un MultiprocessingSolver)

¡Ir más allá requeriría alquilar una máquina potente en un proveedor de nube durante al menos unos días!

Como hemos visto, algunos teoremas matemáticos pueden resolverse mediante exploración combinatoria. En este artículo estudiamos el problema de la existencia/no existencia de cuasigrupos. Entre estos problemas, algunos abiertos parecen ser accesibles, lo que resulta muy estimulante.

Algunas ideas para mejorar nuestro enfoque actual sobre la existencia de cuasigrupos:

  • refinar el modelo que todavía es bastante simple
  • explorar heurísticas más sofisticadas
  • ejecutar el código en la nube (usando Docker, por ejemplo)

Por automata