🤖 machine learning

Graph Coloring Approach to Solving Sudoku with Oscillatory Neural Networks

Este artigo introduz um resolvedor de Redes Neurais Oscilatórias (ONN) otimizado que reformula o Sudoku como um problema de Coloração de Grafos, alcançando uma precisão significativamente maior do que as abordagens existentes de HNN e ONN em quebra-cabeças de $4 \times 4$ e $9 \times 9$ .

Autores originais: Filip Sabo, Aida Todri-Sanial

Publicado 2026-07-20

📖 7 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Filip Sabo, Aida Todri-Sanial

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine um mundo onde os computadores não apenas processam números como uma calculadora superveloz, mas em vez disso dançam conforme um ritmo. Este é o reino das Redes Neurais Oscilatórias (ONNs), um tipo de computação "baseada na física". Em vez de usar interruptores eletrônicos padrão, essas redes usam unidades minúsculas e vibrantes chamadas osciladores. Pense nelas como uma sala cheia de metrônomos ou um coro de cantores. Neste sistema, a informação não é armazenada como um simples bit de "ligado" ou "desligado"; ela é armazenada no tempo das vibrações, conhecido como fases. Se dois osciladores vibram em sincronia perfeita, eles estão "em fase"; se vibram em tempos opostos, estão "fora de fase".

O objetivo dessas redes é encontrar um estado de harmonia perfeita, ou a energia mais baixa possível, onde todos os osciladores se estabilizam em um padrão estável. Esta abordagem é particularmente boa para resolver problemas de otimização combinatória — quebra-cabeças onde você tem que organizar várias peças para que se encaixem em regras específicas sem quaisquer conflitos. Você já deve ter ouvido falar do problema de Coloração de Grafos, que é como tentar colorir um mapa para que nenhum país vizinho compartilhe a mesma cor. Se você conseguir fazer com que uma rede de osciladores naturalmente se estabilize em um padrão onde nenhum "vizinho" esteja vibrando ao mesmo tempo, você resolveu um quebra-cabeça complexo usando as leis da física em vez de apenas matemática de força bruta. Isso importa porque os computadores tradicionais têm dificuldade com esses tipos de quebra-cabeças, muitas vezes consumindo quantidades massivas de eletricidade e tempo, enquanto esses osciladores dançantes podem oferecer uma maneira mais rápida e energeticamente eficiente de pensar.

O Grande Duelo de Dança do Sudoku

Agora, vamos falar de Sudoku. Você conhece o esquema: uma grade de números onde você tem que preencher os espaços vazios para que cada linha, coluna e pequeno bloco contenha os dígitos de 1 a 9 (ou de 1 a 4 para as versões menores) sem repetições. É um clássico quebra-cabeça de lógica, mas para um computador, é uma dor de cabeça enorme de tentativa e erro.

Os pesquisadores deste artigo, Filip Sabo e Aida Todri-Sanial, da Universidade Tecnológica de Eindhoven, decidiram enfrentar o Sudoku usando sua rede de "osciladores dançantes". Eles trataram a grade do Sudoku como um problema de Coloração de Grafos. Imagine que cada célula vazia na grade do Sudoku é um dançarino. A regra é simples: nenhum par de dançarinos na mesma linha, coluna ou bloco pode estar usando a mesma "cor" (que, neste caso, representa um número específico, como 1, 2 ou 3).

No mundo dos osciladores, "usar uma cor" significa vibrar em um ritmo específico. Para um Sudoku 9x9, existem 9 ritmos (fases) possíveis que os osciladores podem escolher. O trabalho da rede é fazer com que todos os dançarinos escolham um ritmo de modo que nenhum vizinho esteja fazendo o mesmo passo de dança.

O Problema com os Velhos Passos de Dança

Os autores analisaram como outros cientistas tentaram resolver isso anteriormente. Um método envolvia uma fórmula matemática complexa que era muito cara de computar, como tentar coreografar uma dança calculando cada movimento muscular com antecedência. Outro método usava uma abordagem mais simples, mas tinha uma falha fatal: permitia que os dançarinos trapaceassem.

Imagine um cenário onde dois dançarinos na mesma linha decidem fazer a dança do "Número 1". Nos modelos antigos, mais simples, a rede poderia pensar: "Ei, eles estão ambos fazendo o ritmo do 'Número 1', o que é um ritmo válido, então estamos bem!". Mas no Sudoku, isso é um desastre. As regras dizem que você não pode ter dois 1s na mesma linha. Os modelos antigos não tinham uma maneira de expulsar os dançarinos desse estado ruim se eles acidentalmente sincronizassem no número errado.

O Novo Termo de "Chute"

Para corrigir isso, os autores inventaram uma nova maneira mais simples de fazer os osciladores dançarem e adicionaram um mecanismo especial de "chute".

O Ritmo Mais Simples: Em vez de usar a fórmula matemática complexa e cara, eles usaram uma equação mais limpa e direta. Isso fez com que a simulação do computador rodasse muito mais rápido e barata.
O "Chute" (O Ingrediente Secreto): Esta é a parte mais importante. Eles adicionaram um termo especial às equações que atua como um árbitro. Se dois dançarinos na mesma linha, coluna ou bloco começarem a vibrar acidentalmente na exata mesma frequência (significando que escolheram o mesmo número), este árbitro dá a eles um "chute" agudo. Isso os empurra para fora desse estado estável e confortável e os força a tentar um ritmo diferente.

Este "chute" garante que a rede só se estabilize quando o quebra-cabeça estiver realmente resolvido corretamente. É como um professor andando pela sala de aula: se dois alunos estiverem sussurrando a mesma resposta errada, o professor toca em seu ombro para fazê-los parar e pensar novamente.

Os Resultados: Uma Performance Impecável

A equipe testou seu novo resolvedor de osciladores de "chute de mestre" em milhares de quebra-cabeças de Sudoku, variando de grades 4x4 pequenas até as grades 9x9 padrão. Eles compararam seus resultados com outros dois resolvedores famosos: um baseado em Redes Neurais de Hopfield (HNN) e outro de Rede Neural Oscilatória padrão.

Aqui está o que descobriram:

Para os quebra-cabezas 4x4: Seu novo resolvedor foi praticamente perfeito. Resolveu quase 100% dos quebra-cabeças corretamente, independentemente de quantos números estavam faltando. Os outros resolvedores tiveram dificuldades, com a precisão caindo drasticamente à medida que os quebra-cabeças ficavam mais difíceis (mais números faltando).
Para os quebra-cabeças 9x9: Os resultados ainda foram impressionantes, embora não totalmente perfeitos. Quando os quebra-cabeças tinham menos números faltando (até cerca de 25% desconhecidos), seu resolvedor era impecável. Mesmo quando os quebra-cabeças ficavam mais difíceis (até 37,5% desconhecidos), ele ainda resolvia mais de 80% deles. No entanto, quando os quebra-cabeças se tornavam muito difíceis (mais de 50% de números desconhecidos), o resolvedor começava a tropeçar, acertando cerca de 50%. Os outros resolvedores falhavam muito antes, muitas vezes sendo incapazes de resolver qualquer quebra-cabeça corretamente assim que os números faltantes passavam de 40-50%.

Os pesquisadores também observaram um "parâmetro de ordem", que é basicamente uma pontuação de quão bem os osciladores conseguiram se estabilizar em seus ritmos finais e corretos. Eles descobriram que sempre que o resolvedor acertava o quebra-cabeça, os osciladores estavam muito bem organizados (alto parâmetro de ordem). Quando errava, os osciladores estavam caóticos e não conseguiam concordar em um padrão estável.

O Que Vem a Seguir?

Os autores estão bastante confiantes de que seu termo de "chute" é a razão do sucesso, mas admitem que ainda há trabalho a fazer. Seu modelo possui alguns botões que eles tiveram que girar manualmente (parâmetros ajustáveis) para fazê-lo funcionar, o que levou muito tempo para ser descoberto. Eles também notaram que, para os quebra-cabezas 9x9 mais difíceis, os osciladores às vezes precisavam de mais tempo para "dançar" e se estabilizar, ou talvez o "chute" não fosse forte o suficiente.

Eles sugerem que as versões futuras deste resolvedor podem tentar usar osciladores ainda mais complexos e "não lineares" (dançarinos com movimentos mais complicados) ou ajustar a função de "chute" para ser ainda melhor em flagrar os infratores de regras. Mas, por enquanto, eles mostraram que, ao adicionar uma regra simples e inteligente à física dessas redes dançantes, podemos resolver quebra-cabeças de Sudoku muito melhor do que antes. É um pequeno passo, mas prova que, às vezes, tudo o que você precisa para consertar um sistema quebrado é um pequeno empurrão na direção certa.

Resumo Técnico: Abordagem de Coloração de Grafos para Resolver Sudoku com Redes Neurais Oscilatórias

Enunciado do Problema
O artigo aborda o desafio de resolver problemas de otimização combinatória restritos (COPs), especificamente o quebra-cabeça Sudoku, utilizando um paradigma de computação baseado em física. Arquiteturas de computação tradicionais enfrentam gargalos de memória-processamento e alto consumo de energia ao lidar com problemas NP-difíceis onde o tempo de solução escala exponencialmente com o tamanho do problema. Os autores propõem utilizar Redes Neurais Oscilatórias (ONNs), que minimizam uma função de energia subjacente através da dinâmica de osciladores acoplados, como uma alternativa às Redes Neurais Artificiais convencionais e às Redes Neurais de Hopfield (HNNs). O desafio específico reside em mapear as regras do Sudoku — onde nenhum dígito pode se repetir em qualquer linha, coluna ou bloco — para a dinâmica de fase dos osciladores sem permitir violações de regras (por exemplo, dois osciladores na mesma linha assentarem no mesmo "dígito" de fase).

Metodologia
Os autores formulam o Sudoku como um problema de Coloração de Grafos, onde cada célula é um nó e as arestas conectam células que compartilham a mesma linha, coluna ou bloco. O objetivo é atribuir uma "cor" (fase) única a cada nó.

Mapeamento de Fase: Para um Sudoku de tamanho $N \times N$ (onde $K=N$ ), as fases ideais são mapeadas para valores discretos: $\phi_{ideal} = \frac{2\pi(k-1)}{K}$ para $k \in \{1, ..., K\}$ .
EDO Modificada: Os autores criticam os modelos existentes de Coloração de Grafos para ONNs (especificamente a formulação Max-K-Cut) por serem computacionalmente caros devido aos parâmetros ajustáveis e por potencialmente permitirem raízes inválidas onde os osciladores assentam na mesma fase, apesar de estarem conectados. Eles propõem uma Equação Diferencial Ordinária (EDO) simplificada e computacionalmente mais barata para a dinâmica do oscilador:
$\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)$
- Primeiro Termo: Conduz os osciladores para serem separados por $\frac{2\pi}{K}$ (lógica Max-K-Cut).
- Segundo Termo ( $K_S$ ): Força os osciladores a assentarem nos valores de fase ideais específicos.
- Terceiro Termo (Contribuição Inovadora): Um termo adicional envolvendo uma função $g(\phi_i, \phi_j)$ que detecta se dois osciladores conectados assentaram na mesma fase (uma violação de regra). Se uma violação for detectada, este termo injeta um gradiente para "expulsar" os osciladores desse estado estável.
Matriz de Pesos ( $W_{ij}$ ): Os pesos são projetados de modo que dígitos conhecidos exerçam uma influência mais forte do que dígitos desconhecidos. Dígitos conhecidos são fixos (gradiente zero), enquanto dígitos desconhecidos interagem com seus vizinhos. O peso entre dois desconhecidos na mesma linha/coluna/bloco é negativo, mas de menor magnitude do que o peso envolvendo um dígito conhecido.
Parâmetro de Ordem ( $\kappa$ ): Uma métrica é definida para rastrear a convergência, onde valores próximos de 1 indicam convergência bem-sucedida para as fases ideais pré-estabelecidas.

Principais Contribuições

Nova Formulação de ONN: O artigo introduz um solver de ONN modificado que reformula o Sudoku como um problema de Coloração de Grafos, mas adiciona um termo específico de imposição de restrição à EDO. Este termo garante que o sistema só atinja um gradiente nulo (estado estável) quando todas as restrições do Sudoku forem satisfeitas, evitando os "falsos positivos" onde os osciladores assentam em fases idênticas para nós conectados.
Eficiência Computacional: Os autores substituem a complexa e pesada EDO do Max-K-Cut por um modelo mais simples e computacionalmente mais barato, que não requer parâmetros de largura de pico ajustáveis para a função de interação.
Benchmarking: O estudo fornece uma comparação abrangente de precisão contra um solver HNN estabelecido e um solver de ONN convencional em quebra-cabeças $4 \times 4$ e $9 \times 9$ com diferentes proporções de dígitos desconhecidos.

Resultados

Quebra-cabeças $4 \times 4$ : O solver proposto alcançou uma precisão quase impecável em todas as proporções de desconhecidos testadas (até 87,5%), superando significativamente tanto o solver HNN quanto os solvers de ONN convencionais. O solver HNN falhou completamente para proporções de desconhecidos acima de 60%, enquanto o solver de ONN convencional caiu para ~80% de precisão com 50% de desconhecidos.
Quebra-cabeças $9 \times 9$ : O solver proposto demonstrou desempenho superior comparado aos outros métodos. Alcançou precisão perfeita para proporções de desconhecidos até 25% e manteve mais de 80% de precisão com 37,5% de desconhecidos. No entanto, o desempenho degradou conforme o número de desconhecidos aumentava, caindo para ~50% com 50% de desconhecidos e falhando em resolver os quebra-cabeças corretamente para proporções de desconhecidos superiores a 70%.
Parâmetros de Ordem: Houve uma forte correlação entre a precisão e o parâmetro de ordem. Alta precisão correspondeu a parâmetros de ordem próximos de 1 (convergência para as fases ideais), enquanto a precisão mais baixa correlacionou-se com parâmetros de ordem menores, sugerindo que o sistema falhou em assentar em um estado estável válido.

Significância e Alegações
O artigo alega que a abordagem proposta supera significativamente os solvers de Sudoku HNN e ONN existentes em termos de precisão, particularmente para grades menores ( $4 \times 4$ ) e grades $9 \times 9$ moderadamente restritas. Os autores atribuem esse sucesso ao termo adicional na EDO, que efetivamente elimina estados estáveis inválidos que satisfazem a minimização de energia, mas violam as regras do Sudoku.

Os autores reconhecem modestamente as limitações, observando que o modelo depende de quatro parâmetros ajustáveis, tornando a varredura de parâmetros custosa. Eles sugerem que, para maiores proporções de desconhecidos em $9 \times 9$ , o termo adicional pode não ser escalado fortemente o suficiente, ou o sistema pode exigir mais ciclos oscilatórios para estabilizar. O artigo conclui que expandir as EDOs com termos de imposição de restrição é uma estratégia relevante para resolver COPs com ONNs e sugere que trabalhos futuros explorem osciladores altamente não lineares e formulações alternativas para a função de imposição de restrição.

O Grande Duelo de Dança do Sudoku

O Problema com os Velhos Passos de Dança

O Novo Termo de "Chute"

Os Resultados: Uma Performance Impecável

O Que Vem a Seguir?

Mais como este