🧠 Resolvendo Quebra-Cabeças Suguru com Evolução: Construindo um Algoritmo Genético em Python

Se você é fã de quebra-cabeças de lógica como Sudoku, vai adorar o Suguru — e se você for programador como eu, vai curtir ainda mais resolvê-lo com código.

Recentemente, construí um solucionador de Suguru usando um Algoritmo Genético (AG), e neste post vou te mostrar o que é o Suguru, por que ele é tão interessante, e como utilizei princípios da evolução para solucioná-lo.

🧩 O que é Suguru?

Suguru é um quebra-cabeça de lógica menos conhecido, mas nem por isso menos desafiador — é um excelente exercício para o cérebro.

• Cada grade do puzzle é dividida em regiões irregulares.
• Cada região deve conter números únicos de 1 até n, onde n é o número de células da região.
• Células adjacentes (mesmo de regiões diferentes) não podem conter o mesmo número.

As regras são simples, mas a complexidade aumenta rapidamente conforme o tamanho da grade cresce.

🧮 Resolvendo Suguru com Backtracking

Além do algoritmo genético, também implementei um algoritmo clássico de backtracking para resolver puzzles Suguru. Essa abordagem usa busca em profundidade recursiva, muito comum na resolução de problemas de satisfação de restrições como o Sudoku.

Como Funciona

O algoritmo de backtracking percorre a grade célula por célula, tentando atribuições válidas de números de acordo com as regras do Suguru:

1. Encontra uma célula vazia na grade.
2. Testa todos os valores possíveis de 1 até o tamanho da região.
3. Verifica se o valor é válido, ou seja:

• Não se repete na mesma região.
• Não aparece em células adjacentes.

4. Se for válido, atribui o valor e passa para a próxima célula.
5. Se nenhum valor for possível, volta para a célula anterior e tenta outra opção (backtracking).

✅ Vantagens

• Garante a solução correta (se existir).
• Simples, determinístico e fácil de debugar.

❌ Limitações

• O desempenho se degrada rapidamente em puzzles grandes ou complexos.
• Não escala bem sem otimizações como propagação de restrições ou forward checking.

Quando Usar

O solucionador por backtracking é ótimo para:

• Puzzles pequenos e médios.
• Comparar desempenho com o algoritmo genético.
• Gerar soluções de referência durante o desenvolvimento ou testes.

🧬 Por que um Algoritmo Genético?

Resolver Suguru não é trivial. Técnicas tradicionais como o backtracking funcionam bem para puzzles pequenos, mas o custo computacional cresce com a dificuldade.

Aí entram os Algoritmos Genéticos.

Inspirados pela evolução biológica, um AG não tenta forçar uma solução perfeita. Em vez disso, ele:

• Começa com uma população de soluções aleatórias.
• Avalia quão “boa” é cada solução.
• Seleciona os melhores indivíduos para reprodução.
• Aplica cruzamento e mutação para gerar novas soluções.
• Repete esse ciclo por várias gerações até encontrar uma solução válida.

Não é garantido que funcione sempre, mas muitas vezes é rápido e eficaz, especialmente para puzzles maiores ou aleatórios.

🛠️ Como Construí o Solucionador com AG

Você pode encontrar o projeto completo no GitHub: 👉 luizcartolano2/suguru-ga

🧠 Por Dentro do Algoritmo Genético

O núcleo do solucionador é um AG que evolui candidatos de grade completa a cada geração. Cada indivíduo da população representa uma tentativa de solução, e o objetivo é minimizar violações das regras até encontrar uma solução válida.

🧬 Representação do Indivíduo

Cada indivíduo é representado como:

• Uma matriz 2D de inteiros — a grade completa do Suguru.
• Uma lista de regiões, onde cada grupo é uma lista de posições de células.
• Uma lista de células fixas — as dicas fornecidas no puzzle.

Para garantir as restrições do puzzle:

• Células fixas permanecem inalteradas ao longo do algoritmo.
• Cada grupo deve conter os números de 1 até n, onde n é o tamanho do grupo.

🎯 Função de Fitness

A função de fitness penaliza violações das regras do Suguru. O objetivo é minimizar esse escore:

• +10 para cada número duplicado em células adjacentes.
• +10 para valores repetidos dentro de um grupo.
• +5 para valores fora do intervalo 1...n em um grupo.
• +5 para valores faltando em um grupo.

Um escore 0 significa uma solução perfeita.

💡 Elitismo (Preservando os Melhores)

Para manter a estabilidade da busca e evitar perder boas soluções, os 10% melhores indivíduos são mantidos na próxima geração. Isso:

• Evita regressão entre gerações.
• Preserva soluções parciais de alta qualidade.
• Acelera a convergência para uma solução válida.

🧬 Cruzamento (Crossover)

O cruzamento combina características de dois pais para gerar novos indivíduos. Como cada indivíduo é uma grade completa, aplicamos dois tipos de lógica:

1. Cruzamento por linha:

• Para cada linha da nova grade, escolhemos aleatoriamente se ela virá do Pai 1 ou Pai 2.

2. Cruzamento por grupo:

• Para cada grupo, escolhemos aleatoriamente se os valores vêm do Pai 1 ou Pai 2.

A cada chamada de cruzamento, escolhemos aleatoriamente entre esses dois métodos. Essa estratégia mista garante a preservação de padrões globais e regionais.

🔀 Mutação

A mutação introduz pequenas alterações aleatórias para manter diversidade genética e explorar novas soluções. Duas estratégias foram implementadas:

1. Troca dentro de um grupo:

• Seleciona um grupo aleatório.
• Escolhe duas células não fixas.
• Troca os valores entre elas.

2. Mutação inteligente (ciente das restrições):

• Seleciona um grupo com valor repetido ou faltando.
• Substitui o valor incorreto por um valor correto.

As mutações ocorrem com uma probabilidade configurável — e a taxa ideal depende do puzzle. Diversas taxas foram testadas durante os experimentos.

▶️ Primeiros Passos

Clone o repositório e instale as dependências:

git clone https://github.com/luizcartolano2/suguru-ga
cd suguru-ga
pip install -r requirements.txt

Execute o solucionador com:

python main_ga.py

Ou, se preferir usar backtracking:

python main_backtracking.py

📈 Experimentos e Resultados

Experimentos

Realizei vários experimentos para comparar o desempenho do Algoritmo Genético com o solucionador por backtracking. O objetivo era medir a rapidez com que cada método consegue resolver diferentes puzzles Suguru de vários tamanhos e níveis de complexidade.

Utilizei um conjunto de puzzles variando de fáceis a difíceis, com diferentes quantidades de células faltantes. Os puzzles foram obtidos de um site online que possui uma coleção jogável de Sugurus. No total, foram usados 240 puzzles para testar ambos os algoritmos.

🧮 Resultados do Backtracking

O algoritmo de backtracking teve um desempenho excelente em todos os puzzles, especialmente nos mais fáceis. Ele resolveu todos os puzzles e levou, em média, 0,2 segundos por puzzle, com o tempo mais alto sendo 12 segundos.

Na imagem abaixo, você pode ver a distribuição dos tempos de resolução do algoritmo de backtracking em diferentes puzzles. O boxplot mostra que a maioria dos puzzles foi resolvida rapidamente, com alguns poucos outliers nos mais complexos.

Outra análise feita foi a relação entre o tempo de resolução e o número de células faltantes no puzzle. O gráfico abaixo mostra que, conforme o número de células faltantes aumenta, o tempo de resolução também aumenta — como era esperado. Ainda assim, o algoritmo de backtracking conseguiu resolver todos os puzzles dentro de um tempo razoável.

🧬 Resultados do Algoritmo Genético

O Algoritmo Genético apresentou maior variabilidade no desempenho. Ele resolveu a maioria dos puzzles — 233 de 240 — mas teve dificuldades com alguns dos mais difíceis, especialmente aqueles com muitas células faltantes.

Como mostrado no boxplot abaixo, o tempo médio de resolução foi de cerca de 2 segundos, com alguns puzzles levando até 30 segundos. O algoritmo foi geralmente mais lento que o backtracking em puzzles com muitas células faltantes, mas foi igualmente rápido nos puzzles mais fáceis.

O gráfico abaixo mostra o tempo de resolução em função do número de células faltantes no puzzle. É possível observar que o tempo aumenta conforme o número de células vazias cresce — de maneira muito mais acentuada que no backtracking.

🙇‍ Discussão

De forma geral, o Algoritmo Genético teve um bom desempenho na maioria dos puzzles, especialmente nos mais fáceis. Ele foi capaz de resolver 97% dos puzzles, enquanto o algoritmo de backtracking resolveu 100%. No entanto, o AG demorou mais, em média, especialmente nos puzzles mais difíceis e incompletos.

Os resultados mostram que o AG é uma alternativa viável aos métodos tradicionais de backtracking para resolver puzzles Suguru, mas exige um ajuste cuidadoso de parâmetros como taxa de mutação e tamanho da população. Também destaca o trade-off entre exploração e exploração nas buscas heurísticas.

É evidente que a implementação atual pode ser aprimorada, principalmente em termos de desempenho e robustez. O AG poderia se beneficiar de estratégias de seleção mais sofisticadas, taxas de mutação adaptativas e melhor tratamento de casos extremos.

Embora os resultados do AG não tenham sido tão consistentes quanto os do backtracking, ele ainda conseguiu encontrar soluções para a maioria dos puzzles, demonstrando o poder dos algoritmos evolutivos na resolução de problemas combinatórios complexos. E com melhorias futuras, pode se tornar ainda mais eficiente — certamente vale a pena continuar explorando.

Dado que há poucas soluções existentes para Suguru que não se baseiam em backtracking na literatura atual, este projeto é um excelente ponto de partida para quem deseja aplicar algoritmos genéticos a quebra-cabeças de lógica.

📊 O Que Aprendi

Este projeto me ensinou muito sobre:

• Criar funções de fitness eficazes para problemas com restrições
• Evitar mínimos locais ajustando as taxas de mutação
• Balancear exploração e exploração em buscas heurísticas
• E sim, depurar lógica de grade é bem mais difícil do que parece

Mas também me deu uma nova apreciação por como algoritmos evolutivos conseguem encontrar estrutura no caos — até mesmo em algo tão humano quanto um quebra-cabeça lógico.

🌱 Próximos Passos

Aqui estão algumas ideias que quero explorar:

• Otimização de desempenho e paralelização
• Um jogo Suguru com interface web + solucionador integrado
• Integração com bibliotecas de satisfação de restrições como o Z3
• Quem sabe até treinar uma rede neural para prever boas populações iniciais?

🔗 Experimente

O repositório é totalmente open source — adoraria ouvir seu feedback ou receber pull requests:

📂 GitHub – luizcartolano2/suguru-ga

💬 Considerações Finais

Se você é um amante de puzzles, um entusiasta de algoritmos, ou só está procurando um projeto divertido de IA para o fim de semana, experimente resolver Suguru com Algoritmos Genéticos. É uma ótima forma de explorar otimização, estratégias de busca e resolução criativa de problemas.

Me avise se resolver algum puzzle com ele! 😄