🤖 machine learning

Graph Coloring Approach to Solving Sudoku with Oscillatory Neural Networks

Este artículo presenta un resolvedor de Redes Neuronales Oscilatorias (ONN) optimizado que reformula el Sudoku como un problema de coloración de grafos, logrando una precisión significativamente mayor que los enfoques actuales de HNN y ONN tanto en rompecabezas de $4 \times 4$ como de $9 \times 9$ .

Autores originales: Filip Sabo, Aida Todri-Sanial

Publicado 2026-07-20

📖 7 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Filip Sabo, Aida Todri-Sanial

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina un mundo donde las computadoras no solo procesan números como una calculadora superrápida, sino que en su lugar bailan al ritmo de una música. Este es el reino de las Redes Neuronales Oscilatorias (ONN, por sus siglas en inglés), un tipo de computación "basada en la física". En lugar de usar interruptores electrónicos estándar, estas redes utilizan unidades diminutas y vibrantes llamadas osciladores. Piensa en ellas como una habitación llena de metrónomos o un coro de cantantes. En este sistema, la información no se almacena como un simple bit de "encendido" o "apagado", sino en el tiempo de las vibraciones, conocido como fases. Si dos osciladores vibran en perfecta sincronía, están "en fase"; si vibran en tiempos opuestos, están "fuera de fase".

El objetivo de estas redes es encontrar un estado de armonía perfecta, o el nivel más bajo de energía, donde todos los osciladores se asienten en un patrón estable. Este enfoque es particularmente bueno para resolver problemas de optimización combinatoria, que son acertijos donde tienes que organizar un montón de piezas para que encajen con reglas específicas sin que haya conflictos. Quizás hayas oído hablar del problema de Coloreo de Grafos, que es como intentar colorear un mapa para que ningún país vecino comparta el mismo color. Si logras que una red de osciladores se asiente naturalmente en un patrón donde ningún "vecino" esté vibrando al mismo tiempo, has resuelto un rompecabezas complejo utilizando las leyes de la física en lugar de solo matemáticas de fuerza bruta. Esto es importante porque las computadoras tradicionales tienen dificultades con este tipo de acertijos, consumiendo enormes cantidades de electricidad y tiempo, mientras que estos osciladores danzantes podrían ofrecer una forma más rápida y eficiente energéticamente de pensar.

El Gran Duelo de Baile de Sudoku

Ahora, hablemos del Sudoku. Ya conoces el juego: una cuadrícula de números donde tienes que rellenar los espacios en blanco para que cada fila, columna y pequeño recuadro contenga los dígitos del 1 al 9 (o del 1 al 4 para las versiones más pequeñas) sin repeticiones. Es un clásico acertijo de lógica, pero para una computadora, es un enorme dolor de cabeza de prueba y error.

Los investigadores de este artículo, Filip Sabo y Aida Todri-Sanial de la Universidad Tecnológica de Eindhoven, decidieron abordar el Sudoku utilizando su red de "osciladores danzantes". Trataron la cuadrícula de Sudoku como un problema de Coloreo de Grafos. Imagina que cada celda vacía en la cuadrícula de Sudoku es un bailarín. La regla es simple: no dos bailarines en la misma fila, columna o caja pueden llevar el mismo "color" (que, en este caso, representa un número específico como el 1, 2 o 3).

En el mundo de los osciladores, "llevar un color" significa vibrar a un ritmo específico. Para un Sudoku de 9x9, hay 9 ritmos posibles (fases) que los osciladores pueden elegir. El trabajo de la red es lograr que todos los bailarines elijan un ritmo de modo que ningún vecino esté haciendo el mismo paso de baile.

El problema con los viejos pasos de baile

Los autores analizaron cómo otros científicos habían intentado resolver esto anteriormente. Un método involucraba una fórmula matemática compleja que era muy costosa de computar, como intentar coreografiar un baile calculando cada movimiento muscular de antemano. Otro método utilizaba un enfoque más simple, pero tenía un fallo fatal: permitía que los bailarines hicieran trampa.

Imagina un escenario donde dos bailarines en la misma fila deciden hacer el baile del "Número 1". En los modelos antiguos y más simples, la red podría pensar: "¡Oye, ambos están haciendo el ritmo del Número 1, lo cual es un ritmo válido, así que estamos bien!". Pero en el Sudoku, eso es un desastre. Las reglas dicen que no puedes tener dos 1 en la misma fila. Los modelos antiguos no tenían una forma de expulsar a los bailarines de ese mal estado si accidentalmente se sincronizaban en el número equivocado.

El nuevo término de "Patada"

Para solucionar esto, los autores inventaron una forma más simple de hacer que los osciladores bailen y añadieron un mecanismo especial de "patada".

El Ritmo Más Simple: En lugar de usar la fórmula matemática complicada y costosa, utilizaron una ecuación más limpia y directa. Esto hizo que la simulación por computadora funcionara mucho más rápido y de forma más económica.
La "Patada" (El ingrediente secreto): Esta es la parte más importante. Añadieron un término especial a las ecuaciones que actúa como un árbitro. Si dos bailarines en la misma fila, columna o caja accidentalmente comienzan a vibrar exactamente en la misma frecuencia (lo que significa que eligieron el mismo número), este árbitro les da una "patada" seca. Esto los empuja fuera de ese estado estable y cómodo y los obliga a probar un ritmo diferente.

Esta "patada" asegura que la red solo se asiente cuando el acertijo se ha resuelto correctamente. Es como un profesor que recorre un salón de clases: si dos estudiantes están susurrando la misma respuesta incorrecta, el profesor les da un toque en el hombro para que se detengan y vuelvan a pensar.

Los Resultados: Una actuación impecable

El equipo probó su nuevo resolvedor de osciladores "kick-ass" (con una patada increíble) en miles de acertijos de Sudoku, que iban desde cuadrículas pequeñas de 4x4 hasta las estándar de 9x9. Compararon sus resultados con otros dos resolvedores famosos: uno basado en Redes Neuronales de Hopfield (HNN) y otro de Red Neuronal Oscilatoria estándar.

Esto es lo que encontraron:

Para los acertijos de 4x4: Su nuevo resolvedor fue prácticamente perfecto. Resolvió casi el 100% de los acertijos correctamente, independientemente de cuántos números faltaran. Los otros resolvedores tuvieron dificultades, y su precisión cayó drásticamente a medida que los acertijos se volvían más difíciles (más números faltantes).
Para los acertijos de 9x9: Los resultados siguieron siendo impresionantes, aunque no fueron perfectos. Cuando los acertijos tenían menos números faltantes (hasta aproximadamente el 25% de desconocidos), su resolvedor era impecable. Incluso cuando los acertijos se volvían más difíciles (hasta el 37.5% de desconocidos), seguía resolviendo más del 80% de ellos. Sin embargo, cuando los acertijos se volvían muy difíciles (más del 50% de números desconocidos), el resolvedor empezaba a tropezar, resolviendo aproximadamente el 50% correctamente. Los otros resolvedores fallaban mucho antes, a menudo siendo incapaces de resolver cualquier acertijo correctamente una vez que los números faltantes pasaban del 40-50%.

Los investigadores también observaron un "parámetro de orden", que es básicamente una puntuación de qué tan bien lograron los osciladores asentarse en sus ritmos finales y correctos. Encontraron que siempre que el resolvedor acertaba el puzzle, los osciladores estaban muy bien organizados (parámetro de orden alto). Cuando fallaba el puzzle, los osciladores eran caóticos y no podían ponerse de acuerdo en un patrón estable.

¿Qué sigue?

Los autores están bastante seguros de que su término de "patada" es la razón de su éxito, pero admiten que aún queda trabajo por hacer. Su modelo tiene algunos controles que tuvieron que ajustar manualmente (parámetros sintonizables) para que funcionara, lo que tomó mucho tiempo descubrir. También notaron que para los acertijos de 9x9 más difíciles, los osciladores a veces necesitaban más tiempo para "bailar" y asentarse, o quizás la "patada" no era lo suficientemente fuerte.

Sugieren que las versiones futuras de este resolvedor podrían intentar utilizar osciladores aún más complejos y "no lineales" (bailarines con movimientos más complicados) o ajustar la función de "patada" para que sea aún mejor detectando a los que rompen las reglas. Pero por ahora, han demostrado que, al añadir una regla simple y astuta a la física de estas redes danzantes, podemos resolver los acertijos de Sudoku mucho mejor que antes. Es un pequeño paso, pero demuestra que, a veces, todo lo que necesitas para arreglar un sistema roto es un pequeño empujón en la dirección correcta.

Resumen Técnico: Enfoque de Coloreado de Grafos para Resolver Sudoku con Redes Neuronales Oscilatorias

Planteamiento del Problema
El artículo aborda el desafío de resolver problemas de optimización combinatoria con restricciones (COP), específicamente el acertijo de Sudoku, utilizando un paradigma de computación basado en la física. Las arquitecturas de computación tradicionales enfrentan cuellos de botella entre memoria y cómputo, así como un alto consumo de energía al abordar problemas NP-duros donde el tiempo de solución escala exponencialmente con el tamaño del problema. Los autores proponen utilizar Redes Neuronales Oscilatorias (ONN), las cuales minimizan una función de energía subyacente mediante la dinámica de osciladores acoplados, como una alternativa a las redes neuronales artificiales convencionales y a las Redes Neuronales de Hopfield (HNN). El desafío específico radica en mapear las reglas del Sudoku —donde ningún dígito puede repetirse en ninguna fila, columna o caja— a la dinámica de fase de los osciladores sin permitir violaciones de las reglas (por ejemplo, que dos osciladores en la misma fila se asienten en la misma "fase de dígito").

Metodología
Los autores formulan el Sudoku como un problema de Coloreado de Grafos, donde cada celda es un nodo y las aristas conectan las celdas que comparten una fila, columna o caja. El objetivo es asignar un "color" (fase) único a cada nodo.

Mapeo de Fase: Para un Sudoku de tamaño $N \times N$ (donde $K=N$ ), las fases ideales se mapean a valores discretos: $\phi_{ideal} = \frac{2\pi(k-1)}{K}$ para $k \in \{1, ..., K\}$ .
EDO Modificada: Los autores critican los modelos existentes de Coloreado de Grafos en ONN (específicamente la formulación Max-K-Cut) por ser computacionalmente costosos debido a sus parámetros ajustables y por permitir potencialmente raíces inválidas donde los osciladores se asientan en la misma fase a pesar de estar conectados. Proponen una Ecuación Diferencial Ordinaria (EDO) simplificada y computacionalmente más barata para la dinámica de los osciladores:
$\dot{\phi}_i = -f_{unknown}(\phi_i) \left[ \frac{1}{N} \sum_{j} W_{ij} \sin\left(\frac{K}{2}(\phi_i - \phi_j)\right) + K_S \sin(K\phi_i) \right] + f_{unknown}(\phi_i) K_G \sum_{j} W'_{ij} g(\phi_i, \phi_j)$
- Primer Término: Impulsa a los osciladores a separarse por $\frac{2\pi}{K}$ (lógica de Max-K-Cut).
- Segundo Término ( $K_S$ ): Fuerza a los osciladores a asentarse en los valores de fase ideales específicos.
- Tercer Término (Contribución Novedosa): Un término adicional que involucra una función $g(\phi_i, \phi_j)$ que detecta si dos osciladores conectados se han asentado en la misma fase (una violación de la regla). Si se detecta una violación, este término inyecta un gradiente para "sacudir" a los osciladores fuera de ese estado estable.
Matriz de Pesos ( $W_{ij}$ ): Los pesos están diseñados de tal manera que los dígitos conocidos ejercen una influencia más fuerte que los dígitos desconocidos. Los dígitos conocidos están fijos (gradiente cero), mientras que los dígitos desconocidos interactúan con sus vecinos. El peso entre dos desconocidos en la misma fila/columna/caja es negativo pero de menor magnitud que el peso que involucra a un dígito conocido.
Parámetro de Orden ( $\kappa$ ): Se define una métrica para rastrear la convergencia, donde los valores cercanos a 1 indican una convergencia exitosa hacia las fases ideales preestablecidas.

Contribuciones Clave

Nueva Formulación de ONN: El artículo introduce un resolvedor ONN modificado que reformula el Sudoku como un problema de Coloreado de Grafos, pero añade un término de aplicación de restricciones a la EDO. Este término asegura que el sistema solo alcance un gradiente nulo (estado estable) cuando todas las restricciones del Sudoku se cumplen, evitando los "falsos positivos" donde los osciladores se asientan en fases idénticas para nodos conectados.
Eficiencia Computacional: Los autores reemplazan la compleja y pesada en parámetros EDO de Max-K-Cut por un modelo más simple y computacionalmente más económico que no requiere parámetros de ancho de pico ajustables para la función de interacción.
Evaluación Comparativa (Benchmarking): El estudio proporciona una comparación exhaustiva de precisión contra un resolvedor HNN establecido y un resolvedor de ONN convencional para acertijos de $4 \times 4$ y $9 \times 9$ con diferentes proporciones de dígitos desconocidos.

Resultados

Acertijos de $4 \times 4$ : El resolvedor propuesto logró una precisión casi impecable en todas las proporciones de desconocidos probadas (hasta el 87.5%), superando significativamente tanto al resolvedor HNN como al de ONN convencional. El resolvedor HNN falló completamente para proporciones de desconocidos superiores al 60%, mientras que el resolvedor ONN convencional cayó a un ~80% de precisión al 50% de desconocidos.
Acertijos de $9 \times 9$ : El resolvedor propuesto demostró un rendimiento superior comparado con los otros métodos. Logró una precisión perfecta para proporciones de desconocidos hasta el 25% y mantuvo más del 80% de precisión al 37.5% de desconocidos. Sin embargo, el rendimiento se degradó a medida que aumentaba el número de desconocidos, cayendo a ~50% al 50% de desconocidos y fallando en resolver correctamente los acertijos para proporciones de desconocidos superiores al 70%.
Parámetros de Orden: Hubo una fuerte correlación entre la precisión y el parámetro de orden. Una alta precisión correspondió a parámetros de orden cercanos a 1 (convergencia a fases ideales), mientras que una menor precisión se correlacionó con menores parámetros de orden, sugiriendo que el sistema no logró asentarse en un estado estable válido.

Significancia y Reivindicaciones
El artículo afirma que el enfoque propuesto supera significativamente a los resolvedores de Sudoku HNN y ONN existentes en términos de precisión, particularmente para cuadrículas pequeñas ( $4 \times 4$ ) y cuadrículas de $9 \times 9$ moderadamente restringidas. Los autores atribuyen este éxito al término adicional en la EDO, que elimina eficazmente los estados estables inválidos que satisfacen la minimización de energía pero violan las reglas del Sudoku.

Los autores reconocen modestamente las limitaciones, señalando que el modelo depende de cuatro parámetros ajustables, lo que hace que el barrido de parámetros sea costoso. Sugieren que para mayores proporciones de desconocidos en $9 \times 9$ , el término adicional puede no estar escalando con suficiente fuerza, o el sistema requiere más ciclos oscilatorios para estabilizarse. El artículo concluye que las EDOs expandidas con términos de aplicación de restricciones son una estrategia relevante para resolver COPs con ONNs y sugiere que trabajos futuros deberían explorar osciladores altamente no lineales y formulaciones alternativas para la función de aplicación de restricciones.

El Gran Duelo de Baile de Sudoku

El problema con los viejos pasos de baile

El nuevo término de "Patada"

Los Resultados: Una actuación impecable

¿Qué sigue?

Más como este