thumb|upright=1.2|right|alt=Um sudoku automórfico de 24 pistas com simetria translacional.|Um Sudoku automórfico de 24 pistas com simetria translacional

A matemática pode ser usada para estudar quebra-cabeças de Sudoku para responder perguntas como "Quantas grades de Sudoku preenchidas existem?", "Qual é o número mínimo de pistas em um quebra-cabeça válido?" e "De que maneiras as grades de Sudoku podem ser simétricas?" através do uso de combinatória e teoria dos grupos.

A análise do Sudoku é geralmente dividida entre a análise das propriedades de quebra-cabeças não resolvidos (como o número mínimo possível de pistas fornecidas) e a análise das propriedades de grades resolvidas. A análise inicial foi amplamente focada na enumeração de soluções, com resultados aparecendo pela primeira vez em 2004..

Para o Sudoku clássico, o número de grades preenchidas é 6.670.903.752.021.072.936.960 (), que se reduz a 5.472.730.538 soluções essencialmente diferentes sob as transformações que preservam a validade. Existem 26 tipos possíveis de simetria, mas eles só podem ser encontrados em cerca de 0,005% de todas as grades preenchidas. Um quebra-cabeça comum com uma solução única deve ter pelo menos 17 pistas. Existe um quebra-cabeça solucionável com no máximo 21 pistas para cada grade resolvida. O maior quebra-cabeça minimal encontrado até agora tem 40 pistas em 81 células.

Terminologia As regiões do Sudoku também são chamadas de blocos ou caixas. Uma banda é uma parte da grade que encapsula três linhas e três blocos, e uma pilha é uma parte da grade que encapsula três colunas e três blocos. Um quebra-cabeça é uma grade parcialmente preenchida, e os valores iniciais são dados ou pistas. Um quebra-cabeça próprio tem uma solução única. Um quebra-cabeça minimal é um quebra-cabeça próprio do qual nenhuma pista pode ser removida sem introduzir soluções adicionais.

Quebra-cabeças Número mínimo de pistas Sudokus comuns (quebra-cabeças próprios) têm uma solução única. Um Sudoku minimal é um Sudoku do qual nenhuma pista pode ser removida mantendo-o um Sudoku próprio. Diferentes Sudokus minimais podem ter um número diferente de pistas. Esta seção discute o número mínimo de pistas para quebra-cabeças próprios.

Sudoku comum thumb|180px|Um Sudoku com 17 pistas thumb|180px|Um Sudoku com 17 pistas e simetria diagonal thumb|180px|Um Sudoku com 18 pistas e simetria ortogonal thumb|180px|Um Sudoku com 24 pistas e simetria geométrica completathumb|180px|Um Sudoku com 19 pistas e simetria ortogonal bidirecional Muitos Sudokus foram encontrados com 17 pistas, embora encontrá-los não seja uma tarefa trivial. Um artigo de 2014 de Gary McGuire, Bastian Tugemann e Gilles Civario provou que o número mínimo de pistas em qualquer Sudoku próprio é 17 através de uma busca computacional exaustiva baseada em enumeração de conjuntos de cobertura.

Sudoku simétrico Acredita-se que o menor número de pistas em um Sudoku com simetria diagonal bidirecional (uma simetria rotacional de 180°) seja 18, e em pelo menos um caso tal Sudoku também exibe automorfismo. Sabe-se que existe um Sudoku com 24 pistas, simetria diédrica (uma simetria rotacional de 90°, que também inclui uma simetria em ambos os eixos ortogonais, simetria rotacional de 180° e simetria diagonal), mas não se sabe se este número de pistas é mínimo para esta classe de Sudoku.. Veja em particular a Figura 7, p. 7.

Número total de quebra-cabeças minimais O número de Sudokus minimais (Sudokus nos quais nenhuma pista pode ser deletada sem perder a unicidade da solução) não é conhecido com precisão. No entanto, técnicas estatísticas combinadas com um gerador (), mostram que existem aproximadamente (com 0,065% de erro relativo): 3,10 × 1037 quebra-cabeças minimais distintos, 2,55 × 1025 quebra-cabeças minimais que não são pseudo-equivalentes (ou seja, mesma disposição onde todas as ocorrências de um dígito são trocadas por outro dígito).

Variantes

Existem muitas variantes de Sudoku, parcialmente caracterizadas pelo tamanho (N), e pela forma de suas regiões. Salvo indicação em contrário, a discussão neste artigo assume o Sudoku clássico, ou seja, N=9 (uma grade 9×9 e regiões 3×3). Um Sudoku retangular usa regiões retangulares de dimensão linha-coluna R×C. Outras variantes incluem aquelas com regiões de formato irregular ou com restrições adicionais (hipercubo).

A resolução de Sudokus do ponto de vista de um jogador foi explorada no livro de Denis Berthier "The Hidden Logic of Sudoku" (2007) que considera estratégias como "cadeias xy ocultas".

Contexto matemático O problema geral de resolver quebra-cabeças Sudoku em grades n2×n2 de blocos n×n é conhecido por ser NP-completo.

Um quebra-cabeça pode ser expresso como um problema de coloração de grafos.Lewis, R. A Guide to Graph Colouring: Algorithms and Applications. Springer International Publishers, 2015. O objetivo é construir uma 9-coloração de um grafo particular, dada uma 9-coloração parcial. O grafo do Sudoku tem 81 vértices, um vértice para cada célula. Os vértices são rotulados com pares ordenados (x, y), onde x e y são inteiros entre 1 e 9. Neste caso, dois vértices distintos rotulados por (x, y) e (x′, y′) são unidos por uma aresta se e somente se: x = x′ (mesma coluna) ou, y = y′ (mesma linha) ou, ⌈ x/3 ⌉ = ⌈ x′/3 ⌉ e ⌈ y/3 ⌉ = ⌈ y′/3 ⌉ (mesma célula 3×3) O quebra-cabeça é então completado atribuindo um número inteiro entre 1 e 9 a cada vértice, de tal forma que vértices unidos por uma aresta não tenham o mesmo inteiro atribuído a eles.

Uma grade solução do Sudoku é também um quadrado latino. Há significativamente menos grades de Sudoku do que quadrados latinos porque o Sudoku impõe restrições regionais adicionais.

Sudokus a partir de tabelas de grupo Como no caso dos quadrados latinos, as tabelas de (adição ou) multiplicação (tabela de Cayley) de grupos finitos podem ser usadas para construir Sudokus e tabelas de números relacionados. Ou seja, é necessário levar em conta subgrupos e grupos quocientes:

Tomemos por exemplo o grupo de pares, adicionando cada componente separadamente módulo algum . Ao omitir um dos componentes, de repente nos encontramos em (e este mapeamento é obviamente compatível com as respectivas adições, ou seja, é um homomorfismo de grupos). Diz-se também que este último é um grupo quociente do primeiro, porque alguns elementos outrora diferentes se tornam iguais no novo grupo. No entanto, também é um subgrupo, porque podemos simplesmente preencher o componente faltante com para voltar a .

Sob esta visão, escrevemos o exemplo, Grade 1, para .

Cada região do Sudoku parece igual no segundo componente (ou seja, como o subgrupo ), porque estes são adicionados independentemente do primeiro. Por outro lado, os primeiros componentes são iguais em cada bloco, e se imaginarmos cada bloco como uma célula, estes primeiros componentes mostram o mesmo padrão (ou seja, o grupo quociente ). Como delineado no artigo sobre quadrados latinos, este é um quadrado latino de ordem .

Agora, para produzir um Sudoku, vamos permutar as linhas (ou equivalentemente as colunas) de tal forma que cada bloco seja redistribuído exatamente uma vez em cada bloco – por exemplo, ordená-los . Isto, naturalmente, preserva a propriedade de quadrado latino. Além disso, em cada bloco, as linhas têm primeiro componente distinto por construção e cada linha em um bloco tem entradas distintas através do segundo componente, porque os segundos componentes dos blocos formavam originalmente um quadrado latino de ordem (a partir do subgrupo ). Assim, chegamos a um Sudoku (renomeie os pares para números 1...9 se desejar). Com o exemplo e a permutação de linhas acima, chegamos à Grade 2. 5 3 4 6 7 8 9 1 2 6 7 2 1 9 5 3 4 8 1 9 8 3 4 2 5 6 7 8 5 9 7 6 1 4 2 3 4 2 6 8 5 3 7 9 1 7 1 3 9 2 4 8 5 6 9 6 1 5 3 7 2 8 4 2 8 7 4 1 9 6 3 5 3 4 5 2 8 6 1 7 9 Para que este método funcione, geralmente não se precisa de um produto de dois grupos de tamanhos iguais. Uma chamada sequência exata curta de grupos finitos de tamanho apropriado já faz o trabalho. Tente por exemplo o grupo com quociente e subgrupo . Parece claro (já a partir de argumentos de enumeração), que nem todos os Sudokus podem ser gerados desta forma.

Sudokus jigsaw Um Sudoku cujas regiões não são (necessariamente) quadradas ou retangulares é conhecido como Sudoku Jigsaw. Em particular, um quadrado N×N onde N é primo só pode ser ladrilhado com N-ominós irregulares. Para pequenos valores de N, o número de maneiras de ladrilhar o quadrado (excluindo simetrias) foi computado . Para N ≥ 4 alguns desses ladrilhos não são compatíveis com nenhum quadrado latino; ou seja, todos os quebra-cabeças Sudoku em tal ladrilho não têm solução.

Soluções A resposta para a pergunta 'Quantas grades de Sudoku existem?' depende da definição de quando soluções semelhantes são consideradas diferentes.

Sudoku comum

Todas as soluções Para a enumeração de todas as soluções possíveis, duas soluções são consideradas distintas se qualquer um de seus valores de células correspondentes (81) diferir. Relações de simetria entre soluções semelhantes são ignoradas, por exemplo, as rotações de uma solução são consideradas distintas. As simetrias desempenham um papel significativo na estratégia de enumeração, mas não na contagem de todas as soluções possíveis.

A primeira solução conhecida para enumeração completa foi publicada por QSCGZ (Guenter Stertenbrink) no grupo de notícias rec.puzzles em 2003, obtendo 6.670.903.752.021.072.936.960 () soluções distintas.

Em um estudo de 2005, Felgenhauer e Jarvis. analisaram as permutações da banda superior usadas em soluções válidas. Uma vez identificadas as simetrias da Banda1 e as classes de equivalência para as soluções de grade parcial, as completações das duas bandas inferiores foram construídas e contadas para cada classe de equivalência. Somando as completações sobre as classes de equivalência, ponderadas pelo tamanho da classe, obtém-se o número total de soluções como 6.670.903.752.021.072.936.960, confirmando o valor obtido por QSCGZ. O valor foi subsequentemente confirmado inúmeras vezes de forma independente. Uma segunda técnica de enumeração baseada na geração de bandas foi posteriormente desenvolvida e é significativamente menos intensiva computacionalmente. Esta técnica subsequente resultou em aproximadamente 1/97 do número de ciclos de computação das técnicas originais, mas foi significativamente mais complicada de configurar.

Soluções essencialmente diferentes

O grupo de simetria do sudoku

A estrutura precisa do grupo de simetria do sudoku pode ser expressa sucintamente usando o produto entrelaçado (≀). As possíveis permutações de linhas (ou colunas) formam um grupo isomorfo a S3 ≀ S3 de ordem 3!4 = 1.296. Todo o grupo de rearranjo é formado permitindo que a operação de transposição (isomorfa a C2) atue em duas cópias desse grupo, uma para as permutações de linhas e outra para as permutações de colunas. Isto é S3 ≀ S3 ≀ C2, um grupo de ordem 1.2962 × 2 = 3.359.232. Finalmente, as operações de renomeação comutam com as operações de rearranjo, então o grupo (VPT) do sudoku completo é (S3 ≀ S3 ≀ C2) × S9 de ordem 1.218.998.108.160.

Pontos fixos e lema de Burnside