Está provado que um quebra-cabeça Sudoku padrão deve ter pelo menos 17 pistas para ter uma solução única.
Regras do Sudoku:
Preencha os números de 1 a 9 em cada linha, coluna e subgrade 3x3 em uma grade 9x9.
Cada número só pode aparecer uma vez em cada linha, coluna e subgrade 3x3.
Preencha os espaços em branco com os números de 1 a 9 para que cada linha, coluna e subgrade 3x3 tenham todos os números de 1 a 9.
Sudoku é um quebra-cabeça de colocação de números baseado em lógica. O objetivo é preencher uma grade 9x9 com os números de 1 a 9, de modo que cada linha, coluna e subgrade 3x3 contenha todos os nove números exatamente uma vez.
Em 2009, Gary McGuire e sua equipe provaram que qualquer quebra-cabeça Sudoku com 16 pistas deve ter pelo menos duas soluções. Eles fizeram isso usando uma técnica chamada “padrões mortos”.
Um padrão morto é uma configuração do Sudoku que possui duas ou mais soluções possíveis. McGuire e sua equipe descobriram que qualquer quebra-cabeça de Sudoku com 16 pistas deve conter pelo menos um padrão morto. Portanto, esses quebra-cabeças devem ter pelo menos duas soluções.
Este resultado tem várias implicações. Primeiro, significa que não existe um quebra-cabeça Sudoku de 16 pistas com uma solução única. Em segundo lugar, significa que qualquer quebra-cabeça Sudoku de 16 pistas pode ser resolvido de várias maneiras. Terceiro, significa que há um número infinito de quebra-cabeças Sudoku de 16 pistas.
Aqui está uma explicação mais técnica da prova de que os quebra-cabeças de Sudoku devem ter pelo menos 17 pistas para ter uma solução única:
A prova começa considerando um quebra-cabeça Sudoku com 16 pistas. Podemos pensar neste quebra-cabeça como um conjunto de restrições aos números que podem ser colocados nos quadrados vazios.
Podemos então usar uma técnica chamada “backtracking” para tentar encontrar uma solução para o quebra-cabeça. Backtracking é um algoritmo recursivo que tenta todas as combinações possíveis de números nos quadrados vazios até encontrar uma solução.
Se houver uma solução única para o quebra-cabeça, o retrocesso acabará por encontrá-la. No entanto, se houver múltiplas soluções, o retrocesso poderá nunca encontrar uma solução.
McGuire e sua equipe usaram o retrocesso para mostrar que se existe um quebra-cabeça Sudoku de 16 pistas com uma solução única, então deve haver uma maneira de iniciar o algoritmo de retrocesso de forma que ele sempre encontre a solução.
Eles então mostraram que isso não é possível. Eles fizeram isso construindo um conjunto de 16 pistas que levavam a um padrão morto. Esse padrão morto significa que há duas soluções possíveis para o quebra-cabeça e não há como iniciar o algoritmo de retrocesso de forma que ele sempre encontre a mesma solução.
Este resultado mostra que qualquer quebra-cabeça Sudoku de 16 pistas deve ter pelo menos duas soluções.