Symmetric Sudoku-Type Games from Perfect Codes

Resumo Técnico: Jogos do Tipo Sudoku Simétricos a Partir de Códigos Perfeitos

Declaração do Problema
Enquanto o Sudoku padrão $9 \times 9$ é um objeto combinatório bem estudado com rica simetria, muitas variantes (como o Sudoku de Quebra-Cabeça) alteram as partições da grade de maneiras que destroem as simetrias rotacionais e reflexivas. Essa perda de simetria torna inaplicáveis muitas estratégias de resolução padrão e ferramentas teóricas. O artigo aborda a necessidade de uma estrutura generalizada para construir jogos do tipo Sudoku que preservem altos níveis de simetria análogos ao jogo clássico, ao mesmo tempo que oferecem novas variações estruturais.

Metodologia
Os autores propõem um método de construção baseado em códigos perfeitos de distância de Lee e códigos perfeitos de diâmetro sobre anéis de inteiros módulo $n$ ($\mathbb{Z}_n$).

1. Fundamentação Teórica: O método utiliza a "propriedade de ladrilhamento" desses códigos. Um código perfeito $C$ particiona o espaço $\mathbb{Z}_n^2$ em bolas disjuntas de raio $t$. Um "código perfeito de diâmetro" alcança a igualdade no Limite Código-Anticódigo, particionando o espaço usando anticódigos de um diâmetro específico.
2. Construção da Grade:
   • Uma grade de paleta $I$ é construída onde cada célula $(x, y)$ recebe um símbolo baseado em qual bola de palavra-código (ou translado de anticódigo) contém aquela coordenada.
   • Uma grade de Sudoku $S$ é definida como um quadrado latino de ordem $n$ que é ortogonal à grade de paleta $I$. Essa ortogonalidade garante que cada símbolo apareça exatamente uma vez dentro das regiões definidas pelo ladrilhamento do código.
3. Relações de Equivalência: Os autores definem classes de equivalência para as grades resultantes sob:
   • Ressinalização: Permutação de símbolos.
   • Movimentos Rígidos: Um grupo específico $G_S$ gerado por rotações, reflexões e translações que preservam a estrutura subjacente do código.
4. Estudos de Caso: A estrutura é aplicada a dois casos mínimos:
   • Sudoku $5 \times 5$: Construído a partir de um código perfeito de correção de 1 erro em $\mathbb{Z}_5^2$ (onde $n=5$).
   • Sudoku $8 \times 8$: Construído a partir de códigos perfeitos de diâmetro 3 em $\mathbb{Z}_8^2$ (onde $n=8$).
5. Avaliação de Dificuldade: Um "resolvedor semelhante a humano" é implementado para avaliar a jogabilidade. Este resolvedor utiliza apenas deduções lógicas elementares (Único Nua e Único Oculto) combinadas com uma fase de tentativa e erro. A dificuldade é quantificada pelo número de inserções de tentativa e erro necessárias além das dicas iniciais.

Principais Contribuições e Resultados

• Enumeração de Soluções:
  • Para o caso $5 \times 5$, os autores identificaram 2.040 grades válidas. Até a ressinalização e a ação do grupo de movimentos rígidos, estas reduzem-se a 17 soluções inequivalentes.
  • Para o caso $8 \times 8$, dois tipos distintos de códigos perfeitos de diâmetro foram analisados. O primeiro tipo produziu aproximadamente $2,80 \times 10^{11}$ grades válidas, reduzindo-se a 232.735 soluções inequivalentes. O segundo tipo produziu aproximadamente $1,95 \times 10^{11}$ grades válidas, reduzindo-se a 304.014 soluções inequivalentes.
• Análise de Sudoku Mínimo:
  • Para o caso $5 \times 5$, os autores enumeraram quebra-cabeças de Sudoku mínimos (aqueles com o número mínimo de dicas necessárias para uma solução única). Eles encontraram um total de 15.898.200 quebra-cabeças mínimos (35.759 até a equivalência) com contagens de dicas variando de 4 a 7.
  • Para o caso $8 \times 8$, uma enumeração completa de quebra-cabeças mínimos foi considerada computacionalmente inviável. Em vez disso, os autores identificaram quebra-cabeças mínimos com contagens de dicas variando de 10 a 18.
• Grades Especiais: O estudo identificou "grades de Sudoku especiais" que satisfazem as restrições do Sudoku para qualquer código perfeito dos parâmetros dados, não apenas para o específico usado na construção. Existem 240 dessas grades para $5 \times 5$ e $4 \times 8!$ para $8 \times 8$.
• Distribuição de Dificuldade: A análise dos jogos $5 \times 5$ usando o resolvedor semelhante a humano revelou uma distribuição equilibrada de níveis de dificuldade. Os quebra-cabeças foram classificados como Fácil (pontuação 0), Médio (pontuação 1–10) e Difícil (pontuação >10). Os resultados mostraram uma mistura viável de dificuldades, com muitos quebra-cabeças solucionáveis por lógica básica e outros exigindo tentativa e erro significativa.

Significância e Afirmações
O artigo afirma que os códigos perfeitos fornecem uma estrutura sistemática e matematicamente rigorosa para gerar jogos do tipo Sudoku simétricos. A principal significância reside em demonstrar que:

1. Preservação de Simetria: Ao contrário de variantes irregulares, essas construções baseadas em códigos preservam inerentemente as simetrias rotacionais e reflexivas encontradas no Sudoku clássico, permitindo a aplicação de análise padrão de teoria de grupos.
2. Diversidade Estrutural: A estrutura gera grades válidas estruturalmente diversas, expandindo o cenário do Sudoku além do formato padrão $9 \times 9$.
3. Jogabilidade Prática: A análise de dificuldade confirma que esses jogos não são meros constructos teóricos, mas oferecem uma "distribuição equilibrada de níveis de dificuldade, variando de Fácil a Difícil", tornando-os alternativas viáveis ao Sudoku tradicional para recreação.

Os autores concluem que essa abordagem une a teoria dos códigos e a matemática recreativa, oferecendo uma nova via para gerar quebra-cabeças lógicos com estruturas algébricas ricas. Trabalhos futuros são sugeridos para estender essas construções a outros anéis e métricas de distância (por exemplo, métricas de Mannheim ou de posto).