Lógica do Sudoku

A lógica do Sudoku é o processo de transformar um pequeno conjunto de restrições em conclusões que precisam ser verdadeiras.

No começo de um quebra-cabeça, as pistas dizem relativamente pouco quando olhamos cada célula isoladamente. A força aparece ao combinar restrições que se sobrepõem:

• cada linha precisa conter os dígitos de 1 a 9 exatamente uma vez;
• cada coluna precisa conter os dígitos de 1 a 9 exatamente uma vez;
• cada bloco 3×3 precisa conter os dígitos de 1 a 9 exatamente uma vez.

Uma etapa lógica de resolução extrai informação nova dessas restrições.

Às vezes, essa informação é um dígito que pode ser colocado.

Em outras, ela é apenas:

Este candidato é impossível.

Isso também é progresso real.

Quatro tipos de informação

A maioria das deduções da trilha de aprendizado pode ser entendida como um destes quatro tipos de informação.

1. Valor forçado

Esta célula precisa ser X.

Exemplos:

• último dígito faltando;
• Candidato Único Desnudo;
• Candidato Único Oculto.

2. Valor proibido

Esta célula não pode ser X.

Exemplos:

• Candidatos Bloqueados;
• subconjuntos;
• Fish;
• Wings;
• eliminações por Chains.

3. Reserva

Estes N dígitos pertencem a estas N células, embora a ordem exata ainda não esteja resolvida.

Exemplos:

• Par Desnudo;
• Par Oculto;
• Trios.

4. Implicação

Se este candidato tiver um estado, outro candidato será forçado a outro estado.

Exemplos:

• Enlaces Fortes/Fracos;
• Colorização;
• X-Chains;
• XY-Chains.

Candidatos são um modelo de incerteza

Um candidato não é um palpite fraco.

Ele significa:

Este dígito ainda não foi eliminado pelo estado atual da grade.

Para uma célula r4c7, o conjunto de candidatos poderia ser:

{2,5,8}

À medida que novas deduções aparecem, esse domínio diminui.

Se ele virar:

{8}

você encontrou um Candidato Único Desnudo.

Do ponto de vista matemático, gerenciar candidatos é uma forma legível para pessoas de propagação de restrições: cada valor resolvido restringe suas células relacionadas, e cada nova restrição pode desencadear outras restrições.

Raciocínio centrado na célula

A lógica centrada na célula pergunta:

O que esta célula pode conter?

Técnicas típicas:

• Candidato Único Desnudo;
• Par Desnudo;
• Trio Desnudo;
• XY-Wing / relações entre células bivalue.

Exemplo:

Duas células de uma mesma linha são {3,9}.

Essas células reservam 3 e 9.

As demais células da linha não podem usar nenhum desses dígitos.

A ordem exata ainda é desconhecida.

A reserva, porém, é certa.

Raciocínio centrado no dígito

A lógica centrada no dígito pergunta:

Onde este dígito pode ser colocado?

Técnicas típicas:

• Candidato Único Oculto;
• Candidatos Bloqueados;
• subconjuntos ocultos;
• X-Wing;
• Swordfish;
• Colorização Simples;
• X-Chain.

Exemplo:

Todos os candidatos 6 de um bloco estão na linha 4.

A célula exata que receberá o 6 ainda é desconhecida.

Mas o bloco garante que a linha 4 recebe seu 6 dentro daquele bloco.

Portanto, o candidato 6 pode ser eliminado da linha 4 fora do bloco.

Esse é um tema recorrente no Sudoku:

A posição exata pode continuar desconhecida enquanto uma informação posicional mais fraca já é forte o suficiente para eliminar candidatos.

Lógica local e lógica distribuída

Deduções locais

A prova acontece principalmente em uma célula, unidade ou interseção:

• Candidatos Únicos;
• Candidatos Bloqueados;
• Pares;
• Trios.

Deduções distribuídas

A prova conecta informação entre unidades ou células mais distantes:

• X-Wing;
• Swordfish;
• Skyscraper;
• W-Wing;
• Colorização;
• Chains.

Sudoku avançado não introduz regras novas para linhas, colunas ou blocos.

Ele combina as mesmas restrições dentro de uma estrutura maior de dependências.

Contagem é uma das ideias mais recorrentes no Sudoku

Várias técnicas que parecem diferentes são, no fundo, argumentos de contagem de conjuntos.

Contagem em subconjuntos

N células ↔ N dígitos

Se três células podem conter apenas três dígitos entre elas, esses dígitos ficam reservados.

Contagem em Fish

N unidades-base → N unidades de cobertura

Se N unidades-base precisam de N ocorrências de um dígito e todas as posições de origem estão cobertas por N unidades opostas, essas unidades de cobertura ficam comprometidas com as bases.

Contagem em subconjuntos ocultos

N dígitos → N células possíveis

Se N dígitos obrigatórios não têm posições fora de N células, essas células ficam reservadas para eles.

Os objetos mudam.

A lógica de conjuntos restritos permanece surpreendentemente parecida.

Lógica de implicação

A resolução avançada fica mais clara quando relações entre candidatos são escritas como implicações.

Enlace Forte

Dois estados candidatos não podem ser ambos falsos.

A falso
→ B verdadeiro

Enlace Fraco

Dois estados candidatos não podem ser ambos verdadeiros.

A verdadeiro
→ B falso

Alternar esses papéis permite propagar um estado:

falso
→ verdadeiro
→ falso
→ verdadeiro

Uma Chain útil transforma essa propagação em uma conclusão sobre um extremo, um candidato-alvo ou uma contradição.

Contradição é um método de prova

Imagine que você assuma temporariamente:

o candidato A é verdadeiro.

Todas as inferências seguintes são então obrigatórias.

Se a Chain leva a um estado impossível, a suposição era falsa.

Isso não é a mesma coisa que simplesmente colocar A e torcer para funcionar.

A suposição temporária é usada para provar o estado oposto.

Contradições possíveis incluem:

• um dígito resolvido duplicado em uma unidade;
• uma célula não resolvida sem nenhum candidato;
• um dígito obrigatório sem posição legal dentro de uma unidade;
• um estado impossível em uma Chain.

Por que “legal” é mais fraco que “resolvido”

Um dígito pode ser legal em uma célula porque não cria nenhum conflito imediato.

Isso não significa que ele esteja logicamente determinado naquela posição.

Exemplo:

r5c4 {3,8}

Os dois candidatos podem ser legais.

Escolher 3 apenas porque ele cabe não é uma dedução.

Uma colocação lógica precisa explicar por que 8 foi eliminado ou por que 3 é forçado de outra forma.

Essa distinção é central tanto para as Regras quanto para o sistema de aprendizado.

Dedução útil vs padrão válido

Um padrão pode existir sem alterar a grade.

Por exemplo:

• um Par Desnudo cujos dígitos já não aparecem em nenhuma outra célula da unidade;
• um X-Wing cujas colunas de cobertura não contêm nenhum candidato externo;
• uma Chain cujos extremos não possuem um alvo comum.

A estrutura pode ser válida.

A jogada de resolução é improdutiva.

Um bom exercício de prática deve testar essa diferença, porque ela impede que colecionar padrões substitua a resolução real.

A cascata de dependências

Sudoku raramente avança como uma sequência de técnicas isoladas.

Uma sequência realista poderia ser:

X-Wing
↓
eliminação de candidato
↓
Candidato Único Oculto
↓
colocação
↓
atualização das células relacionadas
↓
Candidatos Bloqueados
↓
Candidato Único Desnudo

A jogada avançada importa porque expõe informação mais simples depois dela.

É por isso que os Guias de estratégia repetem uma recomendação:

Depois de qualquer eliminação, volte a procurar lógica simples.

Solucionador de correção vs solucionador no estilo humano

Software pode responder a perguntas diferentes.

Solucionador de correção / contagem de soluções

Existe uma solução?

Existe exatamente uma?

Ele pode usar:

• backtracking;
• exact cover;
• busca SAT/por restrições;
• outro algoritmo completo.

Analisador no estilo humano

Qual dedução compreensível está disponível agora?

Ele tenta uma biblioteca de técnicas em uma ordem definida e registra:

• colocações;
• eliminações;
• técnicas necessárias;
• dependências;
• características de dificuldade.

Um software de Sudoku pode se beneficiar dos dois tipos.

Usar um único solucionador para todas as tarefas misturaria correção, pedagogia e dificuldade.

Unicidade é uma premissa adicional

Unique Rectangle não decorre apenas das três restrições locais do Sudoku.

Ele também assume:

Este quebra-cabeça tem exatamente uma solução.

Essa premissa pode ser válida e útil, mas precisa estar explícita.

Deduções de unicidade só devem ser usadas quando o Sudoku foi verificado como único e o modelo de resolução escolhido permite esse tipo de técnica.

O que “lógico” significa nestes Guias

Nestes Guias, uma dedução lógica deve ser:

• derivada das restrições conhecidas do quebra-cabeça e de qualquer premissa adicional explícita;
• reproduzível a partir do estado atual;
• explicável passo a passo;
• verificável de forma independente a partir da grade;
• produtiva quando for apresentada como a próxima jogada de resolução.

O nome da técnica é secundário.

A prova é a parte importante.

FAQ

Eliminar um candidato é realmente uma jogada de Sudoku?

Sim. A resolução intermediária e avançada muitas vezes progride por eliminações antes que outro dígito possa ser colocado.

Técnicas avançadas usam regras diferentes?

Normalmente não. Elas combinam as mesmas restrições através de mais células ou unidades. Técnicas de unicidade acrescentam explicitamente a premissa verificada de solução única.

Contradição é adivinhação?

Não quando uma suposição temporária é usada dentro de uma prova válida e a conclusão é obrigatória.

Por que dois solucionadores podem encontrar jogadas diferentes?

Várias deduções podem estar disponíveis ao mesmo tempo. Um solucionador no estilo humano precisa de um modelo de prioridade, normalmente favorecendo a lógica produtiva mais simples.

Todo padrão válido precisa ser usado?

Não. Se ele não produz informação nova ou existe uma dedução mais simples disponível, pode ser melhor ignorá-lo.

O que aprender a seguir

Para a pergunta prática “Eu realmente preciso adivinhar?”, continue em É Preciso Adivinhar no Sudoku?

Para a representação matemática do quebra-cabeça, continue em Sudoku e Matemática.