An Integer Linear Programming Model for the Evolomino Puzzle

Este artigo formaliza o quebra-cabeça lógico Evolomino como um modelo de programação linear inteira, apresenta um algoritmo para gerar instâncias com solução única e demonstra a eficácia de um solver CP-SAT na resolução de puzzles de até 18x18 em tempo computacional viável.

O essencial

Imagine que você está diante de um novo jogo de lógica, como um "Sudoku" ou "Slitherlink", mas com uma regra especial de crescimento. Esse jogo se chama Evolomino.

Aqui está a explicação do que os autores desse artigo fizeram, traduzida para uma linguagem simples e cheia de analogias:

1. O Que é o Jogo (Evolomino)?

Pense em um tabuleiro de xadrez onde algumas casas têm setas desenhadas. O seu objetivo é desenhar quadrados em algumas casas brancas para formar "blocos" (como peças de Tetris).

A mágica do jogo é a evolução:

• Cada seta deve guiar uma "família" de blocos.
• O primeiro bloco da família é pequeno (apenas 1 quadrado).
• O segundo bloco é um pouco maior (2 quadrados), mas tem exatamente a mesma forma do primeiro, apenas deslocado.
• O terceiro bloco é maior ainda (3 quadrados), mantendo a mesma forma, e assim por diante.
• É como se você estivesse criando uma "sombra" que cresce a cada passo, mas nunca muda de formato e nunca gira.

2. O Problema: Como Resolver Isso?

O jogo parece fácil de entender, mas é matematicamente muito difícil para computadores. É como tentar adivinhar a forma de uma nuvem que está crescendo, mas você só pode ver pequenas partes dela e precisa garantir que todas as peças se encaixem perfeitamente sem se chocar.

Os autores do artigo (Andrei e Yuri) queriam ensinar um computador a resolver esses quebra-cabeças. Eles não usaram "intuição" ou "tentativa e erro" comum. Em vez disso, eles criaram uma receita matemática rigorosa chamada Programação Linear Inteira (ILP).

3. A "Receita" Matemática (O Modelo ILP)

Imagine que você é um chefe de cozinha tentando organizar uma cozinha gigante. Você precisa de regras estritas para que nada dê errado. O modelo matemático deles funciona como um livro de regras com três partes principais:

• As Regras de Ocupação: "Se eu colocar um quadrado aqui, ele não pode pertencer a dois blocos ao mesmo tempo." (É como dizer: "Um ingrediente só pode estar em um prato por vez").
• A Regra do Crescimento (Evolução): "Se o bloco 1 tem um quadrado na posição X, o bloco 2 deve ter um quadrado na posição Y, que é exatamente X mais um passo." Eles usam equações para garantir que a forma do bloco não mude, apenas cresça.
• A Regra da Conexão (O Fluxo): Como garantir que os quadrados formem uma peça única e não várias pedacinhos soltos? Eles usaram uma ideia de "fluxo de água". Imagine que o quadrado na seta é uma torneira. A água (o fluxo) deve sair da torneira e encher todos os quadrados do bloco. Se houver um quadrado isolado, a água não chega lá, e o computador sabe que a solução está errada.

4. Criando os Jogos (Gerador de Quebra-Cabeças)

Não basta resolver o jogo; é preciso criar novos jogos que tenham uma única solução correta.
Os autores criaram um algoritmo (um robô criador) que:

1. Começa com um tabuleiro vazio.
2. Desenha setas aleatoriamente (como se estivesse desenhando com os olhos fechados, mas tentando não sair do papel).
3. Tenta preencher os blocos seguindo as regras.
4. Se o jogo ficar com várias soluções possíveis, o robô "apaga" algumas dicas e tenta de novo, até encontrar o ponto perfeito onde o jogo é desafiador, mas tem apenas uma resposta certa.

5. O Resultado: O Computador Venceu!

Eles testaram esse sistema em computadores poderosos.

• O que aconteceu? O computador (usando um software chamado CP-SAT) conseguiu resolver quebra-cabeças de tamanho médio (11x11) em menos de um segundo.
• O recorde: Ele conseguiu resolver tabuleiros grandes (18x18) em menos de um minuto.

Isso é impressionante porque, para um computador, tentar todas as combinações possíveis de um tabuleiro 18x18 seria como tentar encontrar uma agulha em um palheiro que é do tamanho de um planeta. Mas, graças às regras matemáticas inteligentes que os autores escreveram, o computador "pula" as combinações impossíveis e vai direto para a solução.

Resumo Final

Os autores pegaram um jogo de lógica novo e divertido, traduziram suas regras para uma linguagem que os computadores entendem perfeitamente (matemática pura) e criaram um método para gerar novos jogos automaticamente.

É como se eles tivessem ensinado um computador a jogar xadrez não apenas movendo peças, mas entendendo a lógica profunda de como as peças devem evoluir, permitindo que ele resolva desafios que antes pareciam impossíveis de serem feitos tão rápido.

Resumo técnico

Aqui está um resumo técnico detalhado do artigo "An Integer Linear Programming Model for the Evolomino Puzzle", apresentado em português:

Resumo Técnico: Um Modelo de Programação Linear Inteira para o Quebra-Cabeça Evolomino

1. O Problema: Evolomino
O artigo foca no Evolomino, um novo quebra-cabeça lógico de papel e lápis publicado pela empresa japonesa Nikoli (famosa por Sudoku e Kakuro), que estreou em março de 2023.

• Mecânica: O jogo é jogado em um tabuleiro retangular com células brancas e sombreadas. O objetivo é desenhar quadrados em algumas células brancas para formar "blocos" (poliominós).
• Regras Principais:
  • Cada bloco deve conter exatamente um quadrado sobre uma seta pré-desenhada.
  • Cada seta deve atravessar pelo menos dois blocos.
  • Evolução: Os blocos subsequentes na trajetória de uma seta devem evoluir a partir do bloco anterior adicionando exatamente um quadrado, sem rotação ou reflexão.
• Complexidade Computacional: O problema de decidir se uma instância possui solução é NP-completo, e o problema de contar o número de soluções distintas é #P-completo.

2. Metodologia
Os autores propõem uma abordagem de "transformar e conquistar", formulando as regras do jogo como um Modelo de Programação Linear Inteira (ILP). O modelo utiliza variáveis e restrições lineares para garantir a validade da solução.

• Variáveis do Modelo:

  • Variáveis de célula ($x_i$): Indicam se uma célula contém um quadrado.
  • Variáveis de bloco ($y_{a,i}^k$): Indicam se a célula $i$ pertence ao $k$-ésimo bloco da seta $a$.
  • Variáveis de ativação ($b_a^k$): Indicam se o $k$-ésimo bloco de uma seta existe.
  • Variáveis de fluxo ($f_{ij}^{ak}$): Baseadas no modelo de Gavish e Graves, usadas para garantir a conectividade de cada poliominó (garantindo que o bloco seja uma peça única e não fragmentada).
  • Variáveis de tradução ($t_{j}^{ak}$): Garantem que a evolução do bloco (adicionar um quadrado) ocorra através de uma translação rígida, preservando a forma geométrica.

• Restrições Chave:

  • Consistência: Cada quadrado pertence a exatamente um bloco; células adjacentes não podem pertencer a blocos diferentes.
  • Evolução Geométrica: O tamanho do bloco $k$ deve ser exatamente o tamanho do bloco $k-1$ mais um. A forma do bloco $k$ deve ser uma cópia transladada do bloco $k-1$.
  • Conectividade: Um fluxo é gerado a partir do quadrado na seta e deve alcançar todas as outras células do bloco, garantindo que não haja componentes desconectados.

3. Geração de Instâncias
Para avaliar o modelo, os autores desenvolveram um algoritmo de geração de quebra-cabeças aleatórios (Algoritmo 1) que garante solução única:

1. Preenchimento: Começa com um tabuleiro vazio e adiciona setas via "caminhada aleatória enviesada" (preferindo continuar reto a virar).
2. Posicionamento de Blocos: Para cada seta, posiciona blocos iniciais e subsequentes, verificando conflitos e evoluções válidas.
3. Escultura (Carving): Após preencher o tabuleiro, o algoritmo remove aleatoriamente dicas (quadrados ou células sombreadas) e verifica, usando o solver ILP, se a remoção cria soluções alternativas. Se criar, a dica é restaurada. Isso resulta em um quebra-cabeça mínimo com solução única.

4. Resultados Computacionais
Os experimentos foram realizados utilizando o solver CP-SAT (do Google OR-Tools), comparado com SCIP, CBC e BOP. O hardware utilizado foi um Intel Core i7-13620H com 16 GB de RAM.

• Comparação de Solvers: Em uma amostra de 50 instâncias de 10x10, o CP-SAT foi superior, resolvendo 100% das instâncias dentro do limite de tempo (180s), enquanto os outros falharam em algumas.
• Desempenho por Tamanho:
  • Até 11x11: Tempo mediano de resolução < 1 segundo.
  • Até 14x14: Tempo mediano < 5 segundos.
  • Até 18x18: Tempo mediano < 1 minuto (48 segundos).
• Escalabilidade: O modelo cresce com complexidade $O(K \cdot |C|^2)$ em termos de restrições. Para instâncias de 18x18, o modelo continha cerca de 40.000 variáveis e 1 milhão de restrições lineares, demonstrando a eficiência dos solvers modernos.

5. Contribuições e Significância

• Primeira Formalização ILP: Este trabalho apresenta a primeira modelagem matemática formal do Evolomino como um problema de Programação Linear Inteira.
• Validação de Complexidade: Embora o problema seja NP-completo, o estudo demonstra que instâncias práticas de tamanho moderado (até 18x18) são tratáveis em tempo real com solvers de última geração.
• Ferramenta de Geração: O algoritmo de geração proposto permite a criação de bancos de dados de quebra-cabeças com garantia de unicidade de solução, essencial para testes e competições.
• Impacto Futuro: O trabalho abre caminho para futuras pesquisas em abordagens alternativas (como algoritmos de cobertura exata DLX ou programação por restrições) e estabelece uma base para a análise teórica de novos quebra-cabeças da Nikoli.

Em suma, o artigo demonstra que, apesar da complexidade teórica do Evolomino, a combinação de uma modelagem ILP rigorosa com solvers modernos (CP-SAT) torna a resolução e a geração desses quebra-cabeças viáveis e eficientes.