O Sudoku

Um dos fenómenos mais curiosos do ano de 2005, que não deve ter passado despercebido ao leitor, foi o aparecimento do Sudoku. Os jornais começaram a incluir este quebra-cabeças ao lado dos horóscopos e das habituais palavras cruzadas. (...) Mas terá o Sudoku alguma Matemática? À primeira vista, o leitor pode pensar que a resposta é afirmativa, tendo em conta que, num desafio de Sudoku, utilizam-se os primeiros nove números naturais, do 1 ao 9. E se tem números é porque tem Matemática! A verdade é que nem tudo o que tem números é Matemática. Além disso, a dinâmica e interesse do Sudoku não está propriamente na utilização de números. Os números estão no Sudoku apenas porque são 9 símbolos que estamos muito habituados a reconhecer e a distinguir e não porque cumprem qualquer função matemática na resolução deste quebra-cabeças. As estratégias utilizadas na resolução de um problema de Sudoku assentam essencialmente na lógica e na eliminação de possibilidades. Podemos mesmo substituir cada um dos números, do 1 ao 9, por quaisquer outros símbolos, por exemplo por nove letras do alfabeto, obtendo exatamente o mesmo tipo de problema na sua essência. (...) A estrutura deste quebra-cabeças baseia-se num quadrado, com n linhas e n colunas, que deve ser preenchido com n símbolos diferentes em que cada símbolo aparece uma e uma só vez em cada linha e cada coluna. Este tipo de estrutura tem um nome em Matemática. Chama-se quadrado latino e é estudo em diversas áreas da Matemática, como na Álgebra. (...)

O algoritmo de Damm

(...) Recentemente, em 2004, H. Michael Damm provou na sua tese de doutoramento a existência de quase-grupos totalmente anti-simétricos para ordens diferentes de 2 e 6. A tabela da imagem define um quase-grupo totalmente anti-simétrico de ordem 10, adaptado de um exemplo apresentado por Damm na sua tese. Esta tabela é o que se designa por quadrado latino: em cada linha e em cada coluna, cada um dos símbolos utilizados devem figurar uma e uma só vez. Os quadrados latinos surgiram pelas mãos de um grande matemático, talvez o maior matemático de todos os tempos: Leonhard Euler (1707-1783). Este tipo de tabelas não é totalmente estranho ao leitor. Se olhar com atenção, encontrará apenas duas diferenças em relação aos tradicionais desafios de Sudoku: não existem as chamadas "regiões" e utiliza-se o 0, para além dos algarismos 1-9. A descoberta de Damm impulsionou o desenvolvimento de um novo algoritmo com o seu nome, que tem a vantagem de apenas utilizar os algarismos tradicionais, do 0 ao 9, e de detetar 100% dos erros singulares e 100% das transposições de algarismos adjacentes. Em relação ao algoritmo de Verhoeff, tem uma implementação mais simples e deteta 100% dos erros fonéticos (por exemplo, quando se escreve 15 em vez de 50, devido à pronúncia semelhante destes números em inglês: "fifteen" e "fifty"). Na imagem, ilustra-se um exemplo de aplicação deste algoritmo para determinar o algarismo de controlo do número 201436571? (o ponto de interrogação representa o algarismo de controlo, por enquanto, desconhecido). (...)