Pensando Sobre Matemática #64 - Sudoku

What!?

Esse post teve patrocínio do MathJax. Não eles nunca me pagaram então não é uma questão de orçamento eles não estarem presentes nesses dias.

Mas... Sudoku?

- O que diabos Sudoku tem a ver com matemática!? Só porque usa números?
- Tudo.

Sudoku é um joguinho besta com o qual você pode se distrair comprando uma revista coquetel nas bancas, ou até mesmo no jornal. Ele é um caso especial de um problema de satisfiabilidade booleana. Trata-se de conseguir fornecer uma solução lógica para uma dada expressão lógica, portanto todas as variáveis são variáveis lógicas, mas no caso específico do Sudoku a solução é (teoricamente) única.

- Ok agora você complicou.

Vamos devagar, mas eu não vou explicar exatamente tudo o que eu falei anteriormente. O problema e satisfiabilidade booleana é bastante conhecido e estudado especialmente na computação. Também não vou falar muito sobre lógica, o que você precisa saber que é existem apenas dois valores possíveis para elas: Verdadeiro ou Falso, 0 ou 1, Chocolate ou Morango, etc...

Legal, mas o que isso tem a ver com os númeroszinhos do Sudoku? Os números na verdade são resultados dessas variáveis lógicas. Enquanto você vê 81 quadradinhos em um jogo típico de Sudoku, existem 729 variáveis lógicas por trás fazendo a mágica da matemática acontecer. Eu não sei se você notou mas esses dois números são particularmente sugestivos. $$9.9=9^2=\mathrm{81}$$ $$9.9.9=9^3=\mathrm{729}$$ Enquanto o Sudoku se apresenta como um quadrado de variáveis, podemos entendê-lo como um cubo de variáveis lógicas. Isso gera algumas coisas interessantes. Se os números são gerados devido a uma visualização específica do cubo, podemos girar o cubo e obter um problema relacionado, que é logicamente idêntico.

Vamos reduzir um pouco a dimensão do problema aqui, até porque o Sudoku não precisa ser exatamente 9 x 9 para ser um Sudoku. Ele certamente precisa ser quadrado, mas podemos usar um 4x4 por exemplo. Dessa forma a quantidade de variáveis lógicas cai pra 64. Eu vou montar as 4 matrizes 4x4, ou em outras palavras eu vou montar o cubo lógico que se forma para o seguinte jogo de Sudoku completo: $$\begin{array}{cccc}\hfill 1\hfill & \hfill 2\hfill & \hfill 3\hfill & \hfill 4\hfill \\ \hfill 3\hfill & \hfill 4\hfill & \hfill 1\hfill & \hfill 2\hfill \\ \hfill 2\hfill & \hfill 1\hfill & \hfill 4\hfill & \hfill 3\hfill \\ \hfill 4\hfill & \hfill 3\hfill & \hfill 2\hfill & \hfill 1\hfill \end{array}$$ $$\begin{array}{cccc}\hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill \end{array}$$ $$\begin{array}{cccc}\hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill \\ \hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill \end{array}$$ $$\begin{array}{cccc}\hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill \\ \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill \end{array}$$ $$\begin{array}{cccc}\hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill \\ \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \end{array}$$ Sobreponha as matrizes binárias sobre a matriz principal do Sudoku pra entender mais ou menos como a coisa funciona.

Sacaram? Agora eu vou deixar a brincadeira de olhar o cubo de outras formas para vocês. Os jogos de Sudoku tem diversas técnicas de solução que podem ser encontradas até na internet facilmente.

Saudações matemáticas!


Créditos na imagem.