Apague um número de um Sudoku e ele pode ficar mais difícil. Apague o número errado e você pode destruir a única resposta do quebra-cabeça. Em algum lugar entre uma grade completa e uma página em branco, existe um limite difícil de quebrar: 17 pistas iniciais. Por que o Sudoku para por aí?

A resposta começa com uma pergunta fácil de ignorar: o seu quebra-cabeça tem apenas uma solução?

Uma grade finalizada, uma resposta

No Sudoku clássico 9×9, cada linha, coluna e bloco 3×3 deve conter os dígitos 1 a 9 exatamente uma vez. Essas são as regras padrão publicadas pela Nikoli. Os números já impressos na grade são chamados de givens (pistas) ou clues.

Uma grade completa pode obedecer a todas essas regras sem ser a única resposta possível para as pistas iniciais. Se duas conclusões diferentes cabem, o jogador não tem como deduzir qual foi a intenção de quem montou o quebra-cabeça.

Por isso a unicidade importa. Um Sudoku clássico bem proposto fornece informação suficiente para identificar exatamente uma grade completa. Se você está começando pelas regras, nosso guia para jogar Sudoku é um bom lugar para começar.

Veja uma pista mudar tudo

Aqui vai um quebra-cabeça propositalmente quase finalizado. Um ponto marca uma célula vazia.

5 3 4 | 6 . 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 | . . 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

Ele tem 78 pistas e uma solução. A primeira linha precisa de um 7. A quarta linha então precisa de um 7 na coluna quatro e de um 6 na coluna cinco.

Agora apague o 6 da linha um, coluna quatro. Quatro células ficam em branco, e duas configurações funcionam:

CélulaConclusão AConclusão B
Linha 1, coluna 467
Linha 1, coluna 576
Linha 4, coluna 476
Linha 4, coluna 567

Todos os outros números permanecem iguais. As duas configurações satisfazem todas as linhas, colunas, blocos e pistas restantes. As quatro células formam um retângulo em que os 6 e 7 podem ser trocados sem quebrar uma regra. Nós conferimos as contagens de soluções: o primeiro quebra-cabeça tem exatamente uma conclusão; após a remoção, ele passa a ter exatamente duas.

Remover uma pista não pode invalidar uma solução que já funcionava: essa solução ainda satisfaz todas as pistas restantes. O que a remoção pode fazer é permitir outra resposta. Mesmo este quebra-cabeça com 77 pistas é ambíguo, então uma contagem grande de pistas, sozinha, não garante unicidade.

Por que 17 é o mínimo

Gary McGuire, Bastian Tugemann e Gilles Civario provaram que nenhum Sudoku clássico 9×9 com 16 pistas tem exatamente uma solução. O artigo de pesquisa original descreve a busca exaustiva por computador. Existem puzzles solucionáveis de forma única com 17 pistas, então 17 é o mínimo.

Isso não significa que qualquer arranjo de 17 números crie um quebra-cabeça válido. As posições e os valores importam. O resultado também se aplica ao Sudoku clássico; regras extras em variações mudam o problema.

Por que eliminar 16 também elimina contagens menores? Se um quebra-cabeça menor tivesse uma solução única, você poderia adicionar pistas corretas daquela solução até chegar a 16. Adicionar essas pistas preservaria a resposta única, o que contradiz o resultado.

Como provar que não existe um quebra-cabeça menor?

Encontrar um quebra-cabeça com 17 pistas mostra o que é possível. Provar que 16 não funciona exige descartar todas as possibilidades.

Os pesquisadores buscaram grades finalizadas de forma sistemática, levando em conta grades equivalentes. O método deles usou conjuntos inevitáveis: grupos de células que precisam conter uma pista para impedir uma conclusão alternativa. Eles desenvolveram um algoritmo eficiente para enumerar conjuntos de acerto, seleções que intersectam esses grupos, e verificaram conjuntos candidatos de pistas quanto à unicidade. O artigo explica o método.

O retângulo acima oferece uma pequena ilustração da ideia. Deixe todas as quatro células sem pistas e as duas conclusões sobrevivem. Fixe pelo menos uma daquelas células e você bloqueia aquela troca específica. Num quebra-cabeça esparso, muitas alternativas possíveis precisam ser bloqueadas ao mesmo tempo.

Pistas mínimas não significam dificuldade máxima

A contagem de pistas responde “quanto de informação é impresso?”. Ela não diz qual dedução você vai encontrar na próxima. Contar pistas não revela se o próximo passo será uma “única óbvia” ou um padrão que você ainda não aprendeu.

Existe outra distinção útil: mínimo e mínimo (minimal). O mínimo é a menor quantidade de pistas possível entre todos os Sudokus clássicos. Um quebra-cabeça minimal é aquele em que remover qualquer pista faz a unicidade desaparecer. Chamar um quebra-cabeça de minimal não significa que ele tenha 17 pistas.

Para o seu próximo jogo, tente explicar cada colocação antes de fazê-la: “Esta é a única célula no bloco que pode receber um 4.” Se você ainda não consegue explicar um movimento, verifique as possibilidades ou tente uma técnica do nosso guia de como resolver Sudoku.

Na próxima vez que você vir um Sudoku esparso, conte as pistas—e então procure o motivo de cada uma ser importante.

PARTICIPE DA CONVERSA

Comentários

0

Compartilhe uma ideia, faça uma pergunta ou ajude outro jogador.

Verificando a sessão…

Carregando comentários…