🧠 Solving Suguru Puzzles with Evolution: Building a Genetic Algorithm in Python

If you're a fan of logic puzzles like Sudoku, you’ll love Suguru, and if you're a programmer like me, you'll love solving it with code even more.

I recently built a Suguru puzzle solver using a Genetic Algorithm (GA), and in this post, I’ll walk you through what Suguru is, why it’s such a fun challenge, and how I used evolutionary principles to crack it.

🧩 What is Suguru?

Suguru is a lesser-known logic puzzle, but don’t let that fool you, it's a beautiful brain-bender.

• Each puzzle grid is divided into irregular regions.
• Each region must be filled with unique numbers from 1 to n, where n is the number of cells in the region.
• Adjacent cells (even across regions!) can’t share the same number.

The rules are simple, but the complexity scales fast, especially as the size of the grid grows.

🧮 Solving Suguru with Backtracking

In addition to the Genetic Algorithm solver, I also implemented a classical backtracking algorithm to solve Suguru puzzles. This approach is based on recursive depth-first search, commonly used for solving constraint satisfaction problems like Sudoku.

How It Works

The backtracking algorithm explores the puzzle grid cell by cell, trying valid number assignments while respecting Suguru's rules:

1. Find an empty cell in the grid.
2. Try all possible values from 1 to the size of the region the cell belongs to.
3. Check if the value is valid, meaning:
4. It does not repeat within the region.
5. It does not appear in any adjacent cells.
6. If valid, assign the value and move to the next empty cell.
7. If no value fits, backtrack by resetting the current cell and trying a different value in the previous one.

Pros & Cons

✅ Advantages:

• Guarantees a correct solution (if one exists).
• Simple and deterministic.
• Easy to verify and debug.

❌ Limitations:

• Performance degrades quickly for large or complex grids.
• Does not scale well without optimizations like constraint propagation or forward checking.

When to Use It

The backtracking solver is great for:

• Small to medium-sized puzzles.
• Benchmarking the Genetic Algorithm.
• Generating ground-truth solutions during development or testing.

🧬 Why a Genetic Algorithm?

Solving Suguru isn't trivial. Traditional techniques like backtracking work well for small puzzles, but as difficulty increases, so does the time and computational effort.

That’s where Genetic Algorithms come in.

Inspired by biological evolution, a GA doesn't try to brute-force the perfect solution. Instead, it:

• Starts with a population of random solutions.
• Evaluates how “fit” each solution is.
• Selects the best ones to “reproduce.”
• Applies crossover and mutation to generate new solutions.
• Repeats this process for generations until it converges on a valid puzzle solution.

It’s not guaranteed to be perfect — but it’s often fast and effective, especially for larger or randomly generated puzzles.

🛠️ How I Built the Suguru GA Solver

You can find the full project on GitHub: 👉 luizcartolano2/suguru-ga

🧠 Under the Hood — How the Genetic Algorithm Works

The core of the solver is a Genetic Algorithm that evolves full Suguru grid candidates over generations. Each individual in the population is a complete puzzle attempt, and the algorithm aims to minimize rule violations until a valid solution is found.

🧬 Individual Representation

Each individual is represented as:

• A 2D matrix of integers — the full Suguru grid.
• A list of regions, where each group is a list of cell positions.
• A list of fixed cells — the given clues that should never change.

To preserve puzzle constraints:

• Fixed cells remain constant throughout the algorithm.
• Each group must contain numbers from 1 to n, where n is the group’s size.

🎯 Fitness Function

The fitness function penalizes violations of Suguru rules. The goal is to minimize this penalty score:

• +10 for each duplicate value in adjacent cells.
• +10 for duplicate values within a group.
• +5 for values out of the valid 1...n range in a group.
• +5 for missing values in a group.

A score of 0 means a perfect, valid solution.

💡 Elitism (Keeping the Best)

To maintain stability and avoid losing good solutions, the top 10% of individuals are directly passed to the next generation. This:

• Prevents regression from one generation to the next.
• Helps preserve high-quality partial solutions.
• Accelerates convergence toward valid answers.

🧬 Crossover

The crossover step combines traits from two parent solutions to generate offspring. Since each individual is a complete grid, we apply crossover in two domain-specific ways:

1. Row-wise crossover:

• For each row in the new grid, randomly choose whether it comes from Parent 1 or Parent 2.

2. Group-wise crossover:

• For each group, randomly choose whether the group’s values come from Parent 1 or Parent 2.

Each time a crossover is applied, one of these two strategies is randomly chosen. This mixed strategy ensures both global and regional patterns are preserved and recombined.

🔀 Mutation

Mutation introduces small, random changes in individuals to maintain genetic diversity and explore new solutions. Two mutation strategies are used:

1. Swap within a group:

• Select a random group.
• Randomly pick two non-fixed cells in that group.
• Swap their values.

2. Smart mutation (constraint-aware):

• Pick a group with duplicate or missing values.
• Attempt to fix the group by replacing a wrong value with a correct one.

Mutations occur with a configurable probability — and finding the right mutation rate is key. Different puzzles required different settings during testing.

▶️ Getting Started

Clone the repo and install dependencies:

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

Run the solver with:

python main_ga.py

Or, if you prefer classic backtracking:

python main_backtracking.py

📈 Experiments and Results

Experiments

I ran multiple experiments to compare the performance of the Genetic Algorithm against the backtracking solver. The goal was to see how quickly each method could solve various Suguru puzzles of different sizes and complexities.

I used a set of puzzles ranging from easy to hard, with varying numbers of missing cells. The puzzles were obtained from an online website that has a collection of Suguru puzzles that can be played online. A total of 240 puzzles were used for testing both algorithms.

🧮 Backtracking Results

The Backtracking Algorithm performed well on all puzzles, especially the easier ones. It solved every puzzle and took an average of 0.2 seconds per puzzle, with the highest time being 12 seconds.

At the image below, you can see the distribution of solving times for the backtracking algorithm across different puzzles. The boxplot shows that most puzzles were solved quickly, with a few outliers for more complex puzzles.

Another analysis made was the solving time vs. the number of missing cells in the puzzle. The graph below shows that as the number of missing cells increases, the solving time also increases, as expected. However, the backtracking algorithm still managed to solve all puzzles within a reasonable time frame.

🧬 Genetic Algorithm Results

The Genetic Algorithm was more variable in its performance. It solved most puzzles, 233 out of 240, but struggled with some of the harder ones, especially those with many missing cells.

As we can see in the boxplot below, the average solving time for the Genetic Algorithm was around 2 seconds, with some puzzles taking up to 30 seconds. The algorithm was generally slower than the backtracking algorithm when having too many missing cells, but it was equally fast for easier puzzles.

The graph below shows the solving time vs. the number of missing cells for the Genetic Algorithm. It shows that the solving time increases with the number of missing cells, but much more dramatically than the backtracking algorithm.

🙇‍ Discussion

In general, the Genetic Algorithm performed well on most puzzles, especially the easier ones. It was able to solve 97% of the puzzles, while the backtracking algorithm solved all of them. However, the GA took longer on average, especially for harder puzzles with many missing cells.

The results show that the GA is a viable alternative to traditional backtracking methods for solving Suguru puzzles, but it requires careful tuning of parameters like mutation rates and population size. It also highlights the trade-off between exploration and exploitation in heuristic search.

It's clear that the current implementation can be improved, especially in terms of performance and robustness. The GA could benefit from more sophisticated selection strategies, adaptive mutation rates, and better handling of edge cases.

Although the GA results were not as consistent as the backtracking algorithm, it still managed to find solutions for most puzzles, demonstrating the power of evolutionary algorithms in solving complex combinatorial problems. And future improvements could make it even more effective, so it's definitely worth exploring further.

Considering the lack of existing solutions for Suguru that are not based on backtracking in the current literature, this project is a great starting point for anyone interested in applying genetic algorithms to logic puzzles.

📊 What I Learned

This project taught me a lot about:

• Designing effective fitness functions for constraint problems
• Avoiding local minima by tweaking mutation rates
• Balancing exploration vs. exploitation in heuristic search
• And yes, debugging grid logic is way more painful than it looks

But it also gave me a deep appreciation for how evolutionary algorithms can find structure in chaos, even in something as human as a logic puzzle.

🌱 What’s Next?

Here are some ideas I want to explore:

• Speed optimization and parallelization
• Web-based Suguru puzzle game + solver
• Integration with constraint satisfaction libraries like z3
• Maybe even training a neural network to predict good initial populations?

🔗 Try It Out

The repo is fully open source, and I’d love to hear your feedback or see your PRs:

📂 GitHub – luizcartolano2/suguru-ga

💬 Final Thoughts

Whether you're a puzzle geek, an algorithm nerd, or just looking for a fun AI weekend project, give Suguru and Genetic Algorithms a try. It’s a great way to explore optimization, search strategies, and creative problem-solving.

Let me know what puzzles you solve with it!

📈 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! 😄