Notícias

A ciência do Sudoku

Solucionar um desses quebra-cabeças não requer cálculos nem habilidade aritmética. Mas nem por isso o jogo deixa de propor problemas matemáticos interessantes

É de esperar que um jogo de lógica desperte o interesse de pouquíssimas pessoas – matemáticos, fanáticos por computador, apostadores compulsivos. O sudoku, porém, tornou-se imensamente popular em um curto período de tempo, fazendo lembrar a febre do cubo mágico do começo dos anos 80.

Ao contrário do cubo, que é tridimensional, um quebra-cabeça sudoku é formado por um quadrado bidimensional. Na versão mais comum, contém 81 casas (distribuídas em nove linhas e nove colunas), agrupadas, por sua vez, em nove quadrados menores (subgrades) com nove casas cada um. O jogo começa com algumas casas já preenchidas por números, cabendo ao jogador completar as casas restantes com algarismos de 1 a 9, de modo que nenhum deles se repita na mesma coluna ou linha, nem dentro da mesma subgrade. Cada quebra-cabeça tem uma única solução.

Embora envolva números, o sudoku não exige conhecimento matemático: nenhuma operação numérica contribui para o preenchimento do quadrado, que em princípio poderia ser completado com qualquer conjunto de nove símbolos diferentes (letras, cores, figuras etc.). Apesar disso, o sudoku oferece vários desafios a matemáticos e especialistas em computação.

Árvore genealógica
O ancestral do Sodoku não é, como muitas vezes se imagina, o quadrado mágico – estrutura em que a soma dos algarismos de todas as linhas, colunas e diagonais produz o mesmo resultado. A não ser pela presença de números e pelo formato, o sudoku não guarda quase nenhuma relação com o passatempo árabe – mas tem tudo a ver com o quadrado latino . De ordem n, ele é uma matriz com n2 células (n células de cada lado), preenchida com n símbolos de tal forma que o mesmo símbolo nunca se repete na mesma linha ou coluna (cada um dos n símbolos é, portanto, utilizado exatamente n vezes). A origem desses quadrados remonta à Idade Média; posteriormente, o matemático Leonhard Euler (1707-1783) os batizou de quadrados latinos e os estudou em detalhe.,Um sudoku padrão se assemelha a um quadrado latino de ordem 9, diferindo apenas por conta da exigência de que cada subgrade de nove casas contenha os números de 1 a 9. O primeiro passatempo desse tipo surgiu na edição de maio de 1979 da revista Dell Pencil Puzzles and Word Games e, segundo pesquisa realizada por Will Shortz, editor de palavras cruzadas do New York Times, teria sido criado por um arquiteto aposentado chamado Howard Garns, que morreu em Indianápolis em 1989 (ou 1981, os relatos variam) sem poder testemunhar o sucesso de sua invenção.

O jogo, publicado pela Dell com o nome de Number Place (lugar dos números), apareceu em uma revista japonesa em 1984 batizado de Sudoku (número único). A revista registrou o nome e, por isso, outras editoras locais passaram a usar a expressão Number Place. Ironicamente, os japoneses se referem ao jogo pelo nome em inglês, enquanto os falantes de inglês adotam o termo japonês.

O sucesso do passatempo se deve ao juiz aposentado Wayne Gould, que o conheceu em visita ao Japão em 1997 e criou um programa de computador para gerar diferentes configurações do quadrado. No fim de 2004, o Times de Londres aceitou uma proposta de Gould para publicar o quebra-cabeça e, em janeiro de 2005, o Daily Telegraph fez o mesmo.

Desde então, jornais do mundo todo passaram a publicar o passatempo, alguns na primeira página, para atrair mais leitores. Na esteira desse sucesso, surgiram revistas e livros sobre o assunto, além de sites e blogs na internet.

Bilhões de Possibilidades
Não demorou para alguns matemáticos começarem a calcular quantos jogos de sudoku seria possível criar. E quantos quadrados preenchidos, ou “gabaritados”, poderiam ser construídos. Logicamente, a resposta deve ser menor do que o número de quadrados latinos por causa da exigência extra, no caso do sudoku, imposta pelas subgrades de nove casas.,Existem apenas 12 quadrados latinos de ordem 3 e 575 de ordem 4, mas 5.524.751.496.156.892.842.531.225.600 de ordem 9. A teoria dos grupos, entretanto, afirma que um quadrado que deriva de outro é equivalente ao original. Em outras palavras, se trocarmos todos os números de forma sistemática (por exemplo, o 1 pelo 2, o 2 pelo 7 e assim por diante), ou se invertermos duas linhas ou duas colunas, os resultados finais serão, em essência, os mesmos. Considerando apenas as formas reduzidas, o número de quadrados latinos de ordem 9 é 377.597.570.964.258.816 (valor publicado em Discrete Mathematics, em 1975, por Stanley E. Bammel e Jerome Rothstein, na época pesquisadores da Universidade do Estado do Ohio).

Determinar o número exato de quadrados de sudoku possíveis se revelou uma tarefa difícil. Hoje, só com o uso da lógica (para simplificar o problema) e de computadores (para analisar as possibilidades sistematicamente) é possível estimar o número de quadrados de sudoku válidos: 6.670.903.752.021.072.936.960. Esse montante inclui as soluções derivadas de qualquer quadrado, por meio de operações elementares (rotações, simetrias, trocas das três primeiras colunas, das três primeiras linhas etc.). O resultado foi obtido por Bertram Felgenhauer, da Universidade Técnica de Dresden, Alemanha, e por Frazer Jarvis, da Universidade de Sheffield, Inglaterra, e confirmado diversas vezes. Se contarmos apenas uma vez os quadrados que podem ser reduzidos a uma configuração equivalente, o número final cai para 5.472.730.538 – pouco menor que a população da Terra. Apesar dessa queda, os fãs do sudoku não precisam temer pela extinção do jogo: mesmo que solucionasse um quadrado por minuto e vivesse cem anos, um indivíduo mal daria conta de 1% do total.

Vale notar que uma grade completa de sudoku pode dar origem a várias grades de enunciados a partir de um dado quadrado inicial (ou seja, um quadrado parcialmente preenchido cuja solução é única). Ninguém ainda conseguiu determinar quantos quadrados iniciais existem. Além disso, um quadrado inicial só tem interesse para matemáticos se for mínimo e não puder ser reduzido – ou seja, se a remoção de um elemento implicar que a solução não é mais única. O desafio para o futuro é calcular o número de quadrados iniciais mínimos, o que representaria em última instância o número de configurações de sudoku possíveis.

Outro problema relativo à minimalidade continua sem resolução: qual deve ser o menor número de elementos do quadrado inicial para que a solução seja única? A resposta parece ser 17. Gordon Royle, da Universidade do Oeste da Austrália, coletou mais de 38 mil exemplos de quadrados que satisfazem esse critério e não podem ser transformados em outros por meio de operações elementares.

Gary McGuire, da Universidade Nacional da Irlanda, em Maynooth, coordena estudos em busca de um quadrado inicial com 16 elementos, mas até agora não identificou nenhum. Aparentemente, ele não existe. Por outro lado, Royle e outros pesquisadores que trabalham independentemente nessa área conseguiram encontrar um que apresenta apenas duas soluções. Não há outros exemplos. Mas isso significa que um sudoku válido com 16 casas não exista. Se fosse possível analisar um quadrado por segundo, diz o pesquisador, o estudo de todos os quadrados possíveis demoraria 173 anos. “Infelizmente, ainda não podemos fazer isso nem com ajuda de computadores.” Ele acredita que em breve a pesquisa de um quadrado talvez possa ser feita em um minuto, mas nesse ritmo a empreitada consumiria 10.380 anos. “Mesmo dividida em 10 mil computadores, a tarefa exigiria cerca de um ano”, acrescenta.,”Precisamos conhecer mais o problema para tornar factível a pesquisa de todos os quadrados. É necessário diminuir o espaço de busca ou elaborar um algoritmo muito melhor que os atuais.”

O que os matemáticos já conhecem é a resposta para o problema oposto: qual é o número máximo de elementos do quadrado inicial para o qual não há garantia de solução única? É 77. É fácil observar que com 80, 79 ou 78 elementos, se houver solução, ela é única. Mas o mesmo não pode ser dito para 77 .

Soluções por Computador
Matemáticos e cientistas da computação gostam de analisar o que o computador pode ou não fazer tanto para solucionar como para criar os jogos. Para o sudoku padrão (9 x 9), é relativamente simples escrever programas que resolvem todos os quadrados válidos.

O método de resolução mais comum é o backtracking (retorno a um estado anterior já analisado), uma forma sistematizada de tentativa e erro pela qual soluções parciais são propostas e, a seguir, ligeiramente modificadas à medida que se revelam erradas. O algoritmo básico funciona assim: o programa insere o número 1 na primeira casa vazia. Se a escolha é compatível com os números já presentes no quadrado, o programa segue para a próxima casa vazia e insere outro 1. Quando há um conflito (o que pode acontecer rapidamente), o algoritmo apaga o 1 que acabou de inserir e escreve 2 ou, se essa opção for inválida, 3 ou o próximo algarismo possível. Depois de chegar ao algarismo possível, passa para a próxima casa e recomeça com o número 1.

Se o número que precisa ser alterado é o 9 (valor máximo no sudoku padrão), o programa retorna e aumenta o número na casa anterior (o penúltimo número inserido) em uma unidade. A seguir, avança novamente até haver novo conflito (às vezes, o programa retrocede várias vezes antes de avançar).

Em um programa bem escrito, esse método explora amplamente todas as hipóteses e termina por encontrar uma solução, se ela existir. Caso haja múltiplas soluções, o que ocorreria para um quadrado não-válido, o programa encontra todas. Para chegar à solução mais rapidamente, uma alternativa é a propagação restrita: depois que um novo número é inserido, o programa gera uma tabela com os algarismos restantes e leva em consideração apenas eles.

Técnicas de backtracking podem ser codificadas por algoritmos relativamente curtos. De fato, programas muito concisos já foram escritos em linguagem Prolog. Criada no final dos anos 70 por Alain Colmerauer e Philippe Roussel, da Universidade de Marselha, França, ela incorpora o backtracking.

Para seres humanos, essa técnica seria inviável porque exigiria paciência extraordinária. Assim, os mortais adotam regras mais variadas e inteligentes, e normalmente só usam tentativa e erro como último recurso. Alguns programas tentam emular métodos humanos: são mais longos que o normal, mas funcionam bem. Algoritmos que estimulam o raciocínio também são úteis para avaliar o nível de dificuldade do jogo, que pode variar de “fácil” (requer táticas simples) ao que muitos chamam de “diabólico” (por exigir regras de lógica complexas).

Uma das abordagens empregadas por cientistas da computação para solucionar sudokus é transformar a tarefa em um problema de colorir grafos, no qual duas células adjacentes (conhecidas em teoria da computação como “dois vértices unidos por uma aresta”) não podem ter a mesma cor, e a palheta disponível conta com nove cores. O grafo contém 81 vértices, alguns dos quais já estão coloridos desde o início. O problema é altamente complexo porque cada quadrado 9 x 9 tem centenas de arestas. Cada célula é parte de uma linha que inclui outras oito, uma coluna que inclui outras oito, e um quadrante que inclui outras oito (das quais quatro já foram contadas na coluna ou na linha). Assim, cada uma das 81 células está ligada indiretamente a 20 outras (8 + 8 + 4), o que totaliza 1.620 células que compartilham uma aresta com a adjacente – conseqüentemente, o número de arestas é 810 (1.620 dividido por 2).
O fato de o sudoku poder ser representado por um problema que envolve combinações de cores é significativo para os cientistas porque essa propriedade liga o passatempo a uma classe importante de problemas.

Takayuki Yato e Takahiro Seta, da Universidade de Tóquio, demonstraram recentemente que o sudoku pertence à categoria de problemas NP completos. Esses problemas são daqueles que não serão solucionados em um prazo realista, como o das três cores, que pergunta se é possível colorir os vértices (ou nós) de um grafo usando três cores de modo que dois vértices unidos por uma aresta nunca tenham a mesma cor. No caso do sudoku, o desafio aparentemente insuperável é escrever um programa eficaz que solucionasse sudokus de todos os tamanhos – ou seja, todo quadrado na forma n2 x n2 , e não apenas as versões 32 x 32 (9 x 9). Nenhum programa idealizado para resolver todos os quadrados funcionaria bem porque o tempo necessário para encontrar uma solução aumenta drasticamente à medida que n cresce.

Um algoritmo que solucione sudokus pode ser usado para obter outro software, que gere os quadrados. Embora os primeiros passatempos tenham sido criados à mão, hoje praticamente todos são produzidos por programas de computador. Os números são inseridos aleatoriamente no quadrado, e um algoritmo de solução (backtracking, por exemplo) é aplicado. Se o quadrado tem solução única, o programa pára. Se o quadrado parcialmente preenchido não apresentar solução, retira-se um algarismo e o programa é reiniciado. Se o quadrado tiver várias soluções, uma delas é escolhida e o algoritmo então acrescenta tantos números quantos forem necessários para garantir que a solução eleita seja única.

Estratégias dos Jogadores
Quem gosta de resolver sudokus manualmente conta com muitas táticas à disposição, mas duas abordagens básicas oferecem um bom ponto de partida. Primeiramente, identificam-se as casas vazias que pertencem a linhas, colunas ou quadrantes que já estejam bem preenchidos. Eliminar opções impossíveis (números que já ocupam casas na mesma linha, coluna ou quadrante) diminui consideravelmente as alternativas e às vezes resulta na descoberta de que apenas um algarismo cabe naquela casa.
Em segundo lugar, procuram-se buracos em que um dado elemento possa se encaixar em determinada coluna, linha ou quadrante (por exemplo, localizam-se os únicos lugares em que um 3 caberia na linha 4). Às vezes, a busca leva a uma única possibilidade de resposta. Em outros momentos, apenas o fato de saber que o 3 se encaixa em duas ou três casas pode ajudar . Sites que trazem estratégias estão listados no “Para Conhecer Mais”.

Diversos programas disponíveis na internet geram sudokus com o nível de dificuldade desejado, além de ajudar na solução (sem, claro, resolver o desafio para o jogador). Alguns permitem que o usuário coloque marcas temporárias nas casas, o que torna desnecessário o uso de lápis e borracha. Outros chegam a criar ligações entre as casas. Ao livrar o jogador de tarefas maçantes, como apagar números, esses programas estimulam o uso da sutileza e da habilidade.

Há ainda inúmeras variantes aos quadrados tradicionais – algumas sobrepõem vários quadrados; outras substituem as subgrades por outras estruturas geométricas ou acrescentam mais dificuldades. Essas alternativas são interessantes porque exigem a exploração de novas estratégias lógicas. Além disso, aqueles que precisam de apenas 15 minutos para completar um sudoku convencional podem dedicar um dia inteiro à resolução de versões gigantes, que combinam várias casas e números.,Apresentamos aqui algumas maneiras de solucionar um sudoku. Os métodos 1 e 2 são os mais simples e, geralmente, são usados em conjunto. Infelizmente, essas técnicas não levam o jogador muito longe e, por isso, deve-se acrescentar o método 3 e, caso também este se revele insufi ciente, o método 4 – que sempre funciona, mas nem sempre de modo fácil.

MÉTODO 1
CASA FORÇADA
Considere uma casa fixa. Ao eliminar os outros algarismos que aparecem na mesma coluna, na mesma linha ou na mesma subgrade, é possível que sobre uma única possibilidade, com a qual a casa deve ser preenchida. Tal análise na grade a revela que os quadros contendo números em laranja, na grade b, são as casas forçadas.

MÉTODO 2
CASA ÚNICA
Aqui, um determinado algarismo é focado, por exemplo, o 5. Nas colunas 1 e 3 da grade a já existe um 5, mas não na coluna 2, que deve conter um 5. Onde ele deve fi car? Não nas três primeiras casas da coluna 2, pois a primeira subgrade já contém um 5. Não na sétima casa da coluna 2, pois sua subgrade também já contém um 5. Assim, o 5 da coluna 2 só poderia entrar na quarta, na quinta ou na sexta casa dessa coluna. Como a quinta é a única disponível, o número vai para lá. As casas marcadas com números em azul na grade B são as casas únicas.

MÉTODO 3
SIMPLIFICAÇÃO DA GAMA DE POSSIBILIDADES
Essa técnica é extremamente efi ciente, mas requer lápis e borracha. Em cada casa, você anota os algarismos ainda possíveis ali. Então é preciso aplicar a lógica para tentar eliminar as alternativas. Por exemplo, a grade c mostra como a grade a fi caria se fossem marcadas todas as possibilidades sem a aplicação prévia dos métodos 1 e 2. Na terceira coluna, a série de possibilidades para as casas 2, 3, 4, 5 e 6 é, respectivamente {2, 3, 6, 7}, {3, 6, 9}, {2, 6}, {2, 6} e {6, 7}. A coluna deve conter um 2 e um 6, portanto esses números devem estar nas duas casas nas quais são as únicas possibilidades (circulados no primeiro destaque). Conseqüentemente, 2 e 6 não podem estar em nenhum outro lugar nesta coluna e podem ser apagados das outras casas (vermelho). A série de possibilidades da coluna simplifi ca-se, fi cando reduzida a: {3, 7}, {3, 9}, {2, 6}. {2, 6}, {7}. Com essa eliminação, descobre-se que o único número possível para a casa 6 é o 7, o que dita as posições do 3 (na casa 2) e do 9 (na casa 3). Assim fi camos com {3}, {9}, {2,6}, {2,6}, {7} (segundo destaque). A única dúvida que persiste é onde colocar o 2 e o 6. A regra geral de simplifi cação é a seguinte: se, entre uma gama de possibilidades (para uma linha, coluna ou subgrade) existirem m casas contendo conjuntos com m algarismos (mas não necessariamente todos em cada casa), os números poderão ser eliminados de acordo com as possibilidades das outras casas. Por exemplo, no esquema d {2,3}, {1,3}, {1,2}, {1,2,4,5}, {3,5,7} podem ser simplifi cados para {2, 3}, {1, 3}, {1, 2}, {4, 5}, {5, 7}, porque as casas {2, 3}, {1, 3}, {1, 2} vêm do subconjunto {1, 2, 3} e não têm outros números.

MÉTODO 4
TENTATIVA E ERRO
Com os três métodos anteriores é possível resolver muitos quebra-cabeças. Mas os níveis diabólicos freqüentemente requerem uma fase de tentativa e erro. Quando a incerteza persiste, é preciso fazer uma escolha e aplicar todas as estratégias para o preenchimento das demais casas. Se deparamos com uma impossibilidade (como o aparecimento de um número duas vezes em uma coluna), a escolha estava errada. Por exemplo, é possível tentar o 2 na quarta casa da terceira coluna na grade c. Se ele falhar, é preciso recomeçar o jogo daquele ponto, desta vez com o número 6. Infelizmente, algumas vezes é preciso fazer várias rodadas de tentativa e erro e estar preparado para voltar atrás. A idéia do método, aliás, é a mesma usada pelos algoritmos de retrocesso sistemático (backtracking), que os programas podem executar facilmente mas para o qual nossa memória tem difi culdade. É impressionante que o método mais efi ciente para as máquinas seja o menos efetivo para o ser humano.,Os quebra-cabeças ao lado são mais desafiadores que os sudokus tradicionais. Para resolvê-los, valem as regras já apresentadas, com algumas complicações extras. Em a, as letras das palavras MARTIN GARDNER substituem os números, e formas geométricas tomam o lugar dos quadrados menores. O inventor desse formato o batizou de Du-Sum-Oh. Em b, tem-se uma estrela com apenas seis sub-regiões triangulares; linhas e colunas inclinadas podem ser interrompidas no centro, e quando uma linha ou coluna tem apenas oito casas, a célula próxima que forma uma ponta da “estrela” serve como uma nona casa. Em c, os algarismos de três dígitos formados pelas linhas nos dois primeiros quadrados menores são somados e devem resultar no número que aparece na linha do terceiro quadrado menor. Em d, sinais de maior e menor () indicam as casas em que os números devem ser colocados. Em e, os dominós na parte de baixo da página devem ser encaixados nos espaços vazios. Em f, três quadrados se sobrepõem. As soluções estão em www.sciam.uol.com.br,1o Campeonato Mundial de Sudoku: www.wsc2006.com/eng/index.php

Math games. Ed Pegg Jr.: www.maa.org/editorial/mathgames/mathgames_09_05_05.html

The Mathematics of sudoku. Sourendu Gupta: theory.tifr.res.in/ffsgupta/sudoku/

The Mathematics of sudoku. Tom Davis: www.geometer.org/mathcircles/sudoku.pdf

Técnicas de sudoku: www.sadmansoftware.com/

Sudoku, uma visão geral: www.sudoku.com/howtosolve.htm

Variantes do sudoku: www.sudoku.com/forums/viewtopic.php?t=995