Su Doku
De: J Carvalho e Silva
Assunto: Su Doku o fenómeno do puzzle de números
Uma razão científica para começar a comprar o jornal "Público":
Su Doku o fenómeno do puzzle de números
Não é preciso saber matemática. Apenas
usar a lógica e ter paciência. E estar avisado:
este quebra-cabeças provoca vício
Na década de 1980, o mundo foi varrido por uma
loucura chamada "cubo de Rubik", um cubo
articulado e multicolorido que era preciso
manipular para deixar cada uma das seis faces
numa cor uniforme: vermelho, azul, amarelo,
laranja, branco e verde. Foi uma verdadeira
febre, um vício.
Agora, quase um quarto de século depois, há quem
arrisque que o mundo está à beira de cair nas
garras de outro vício. Chama-se Su Doku e, na era
dos jogos tecnólogicos, é um improvável puzzle
que se resolve com lápis, papel e com a cabeça -
nada de consolas, software, ecrãs, tecnologia.
Aparentemente, na sua simplicidade está boa parte
da explicação para o seu fascínio.
O Su Doku é, há muitos anos, um jogo com forte
implantação no Japão, onde cinco revistas com
problemas têm actualmente uma tiragem mensal
superior a 600 mil exemplares. Curiosamente, a
sua origem, tanto quanto se sabe, é ocidental: no
início dos anos 80, ao mesmo tempo portanto que a
"febre de Rubik" tomava conta do planeta, uma
revista americana publicou vários puzzles de
números.
Foi a editora japonesa Nikoli que percebeu o
potencial do quebra-cabeças para os seus
leitores: o japonês, por causa da natureza do seu
alfabeto, não se presta a palavras cruzadas. O
primeiro "puzzle de números" foi publicado no
Japão em 1984, sob o nome "Suji wa dokushin ni
kagiru", que significa literalmente "números
solteiros", e de onde resultou a abreviatura Su
Doku - ou Sudoku.
Em 2004, um neozelandês que vive em Hong Kong, o
juiz reformado Wayne Gould, apresentou a jornais
ingleses o resultado de uma obsessão de sete
anos: um programa de computador para gerar até ao
infinito novos problemas de Su Doku. Em Novembro,
The Times, de Londres, resolveu aceitar a
proposta de Gould e começou a publicar os puzzles
de números na sua página de jogos.
A resposta dos leitores depressa deu a perceber
que o Su Doku não seria um jogo como os outros.
Em breve, as cartas e respostas estavam ao nível
das históricas palavras cruzadas do diário
britânico. Outros jornais compreenderam que havia
um fenómeno: hoje, The Independent, The Guardian,
The Daily Mail, The Daily Telegraph, The Sun, têm
os seus problemas diários de Su Doku - anunciados
na primeira página. The Times já editou um livro
de problemas que se tornou um best-seller num
ápice; esta semana mesmo, o jornal criou um
serviço pago que envia puzzles para telemóvel.
Na sua análise dos números de vendas de jornais
em Abril, The Independent notava a semana passada
que, apesar do casamento real, da campanha
eleitoral, da morte do Papa, a imprensa escrita
tinha registado uma quebra. E garantia que esta
só não tinha sido maior por causa da adesão
maciça ao Su Doku, agora transformado em vício
nacional.
A febre ameaça espalhar-se pelo resto do
Ocidente. Os puzzles de números desembarcam
início dos anos 80, ao mesmo tempo portanto que a
"febre de Rubik" tomava conta do planeta, uma
revista americana publicou vários puzzles de
números.
Foi a editora japonesa Nikoli que percebeu o
potencial do quebra-cabeças para os seus
leitores: o japonês, por causa da natureza do seu
alfabeto, não se presta a palavras cruzadas. O
primeiro "puzzle de números" foi publicado no
Japão em 1984, sob o nome "Suji wa dokushin ni
kagiru", que significa literalmente "números
solteiros", e de onde resultou a abreviatura Su
Doku - ou Sudoku.
Em 2004, um neozelandês que vive em Hong Kong, o
juiz reformado Wayne Gould, apresentou a jornais
ingleses o resultado de uma obsessão de sete
anos: um programa de computador para gerar até ao
infinito novos problemas de Su Doku. Em Novembro,
The Times, de Londres, resolveu aceitar a
proposta de Gould e começou a publicar os puzzles
de números na sua página de jogos.
A resposta dos leitores depressa deu a perceber
que o Su Doku não seria um jogo como os outros.
Em breve, as cartas e respostas estavam ao nível
das históricas palavras cruzadas do diário
britânico. Outros jornais compreenderam que havia
um fenómeno: hoje, The Independent, The Guardian,
The Daily Mail, The Daily Telegraph, The Sun, têm
os seus problemas diários de Su Doku - anunciados
na primeira página. The Times já editou um livro
de problemas que se tornou um best-seller num
ápice; esta semana mesmo, o jornal criou um
serviço pago que envia puzzles para telemóvel.
Na sua análise dos números de vendas de jornais
em Abril, The Independent notava a semana passada
que, apesar do casamento real, da campanha
eleitoral, da morte do Papa, a imprensa escrita
tinha registado uma quebra. E garantia que esta
só não tinha sido maior por causa da adesão
maciça ao Su Doku, agora transformado em vício
nacional.
A febre ameaça espalhar-se pelo resto do
Ocidente. Os puzzles de números desembarcam
paulatinamente na Europa Ocidental, já voltaram
aos Estados Unidos e a semana passada começaram a
ser usados por jornais norte-americanos.
Parece inexplicável, num século XXI tão
tecnológico, este êxito de uma grelha de nove
quadrados por nove, em que só é preciso preencher
as 81 casas para que cada fila, coluna e quadrado
contenha os números de 1 a 9, sem repetições. Mas
os fenómenos raramente têm uma explicação. Este
fenómeno está a partir de hoje na última página
do PÚBLICO.
Assunto: Su Doku o fenómeno do puzzle de números
Uma razão científica para começar a comprar o jornal "Público":
Su Doku o fenómeno do puzzle de números
Não é preciso saber matemática. Apenas
usar a lógica e ter paciência. E estar avisado:
este quebra-cabeças provoca vício
Na década de 1980, o mundo foi varrido por uma
loucura chamada "cubo de Rubik", um cubo
articulado e multicolorido que era preciso
manipular para deixar cada uma das seis faces
numa cor uniforme: vermelho, azul, amarelo,
laranja, branco e verde. Foi uma verdadeira
febre, um vício.
Agora, quase um quarto de século depois, há quem
arrisque que o mundo está à beira de cair nas
garras de outro vício. Chama-se Su Doku e, na era
dos jogos tecnólogicos, é um improvável puzzle
que se resolve com lápis, papel e com a cabeça -
nada de consolas, software, ecrãs, tecnologia.
Aparentemente, na sua simplicidade está boa parte
da explicação para o seu fascínio.
O Su Doku é, há muitos anos, um jogo com forte
implantação no Japão, onde cinco revistas com
problemas têm actualmente uma tiragem mensal
superior a 600 mil exemplares. Curiosamente, a
sua origem, tanto quanto se sabe, é ocidental: no
início dos anos 80, ao mesmo tempo portanto que a
"febre de Rubik" tomava conta do planeta, uma
revista americana publicou vários puzzles de
números.
Foi a editora japonesa Nikoli que percebeu o
potencial do quebra-cabeças para os seus
leitores: o japonês, por causa da natureza do seu
alfabeto, não se presta a palavras cruzadas. O
primeiro "puzzle de números" foi publicado no
Japão em 1984, sob o nome "Suji wa dokushin ni
kagiru", que significa literalmente "números
solteiros", e de onde resultou a abreviatura Su
Doku - ou Sudoku.
Em 2004, um neozelandês que vive em Hong Kong, o
juiz reformado Wayne Gould, apresentou a jornais
ingleses o resultado de uma obsessão de sete
anos: um programa de computador para gerar até ao
infinito novos problemas de Su Doku. Em Novembro,
The Times, de Londres, resolveu aceitar a
proposta de Gould e começou a publicar os puzzles
de números na sua página de jogos.
A resposta dos leitores depressa deu a perceber
que o Su Doku não seria um jogo como os outros.
Em breve, as cartas e respostas estavam ao nível
das históricas palavras cruzadas do diário
britânico. Outros jornais compreenderam que havia
um fenómeno: hoje, The Independent, The Guardian,
The Daily Mail, The Daily Telegraph, The Sun, têm
os seus problemas diários de Su Doku - anunciados
na primeira página. The Times já editou um livro
de problemas que se tornou um best-seller num
ápice; esta semana mesmo, o jornal criou um
serviço pago que envia puzzles para telemóvel.
Na sua análise dos números de vendas de jornais
em Abril, The Independent notava a semana passada
que, apesar do casamento real, da campanha
eleitoral, da morte do Papa, a imprensa escrita
tinha registado uma quebra. E garantia que esta
só não tinha sido maior por causa da adesão
maciça ao Su Doku, agora transformado em vício
nacional.
A febre ameaça espalhar-se pelo resto do
Ocidente. Os puzzles de números desembarcam
início dos anos 80, ao mesmo tempo portanto que a
"febre de Rubik" tomava conta do planeta, uma
revista americana publicou vários puzzles de
números.
Foi a editora japonesa Nikoli que percebeu o
potencial do quebra-cabeças para os seus
leitores: o japonês, por causa da natureza do seu
alfabeto, não se presta a palavras cruzadas. O
primeiro "puzzle de números" foi publicado no
Japão em 1984, sob o nome "Suji wa dokushin ni
kagiru", que significa literalmente "números
solteiros", e de onde resultou a abreviatura Su
Doku - ou Sudoku.
Em 2004, um neozelandês que vive em Hong Kong, o
juiz reformado Wayne Gould, apresentou a jornais
ingleses o resultado de uma obsessão de sete
anos: um programa de computador para gerar até ao
infinito novos problemas de Su Doku. Em Novembro,
The Times, de Londres, resolveu aceitar a
proposta de Gould e começou a publicar os puzzles
de números na sua página de jogos.
A resposta dos leitores depressa deu a perceber
que o Su Doku não seria um jogo como os outros.
Em breve, as cartas e respostas estavam ao nível
das históricas palavras cruzadas do diário
britânico. Outros jornais compreenderam que havia
um fenómeno: hoje, The Independent, The Guardian,
The Daily Mail, The Daily Telegraph, The Sun, têm
os seus problemas diários de Su Doku - anunciados
na primeira página. The Times já editou um livro
de problemas que se tornou um best-seller num
ápice; esta semana mesmo, o jornal criou um
serviço pago que envia puzzles para telemóvel.
Na sua análise dos números de vendas de jornais
em Abril, The Independent notava a semana passada
que, apesar do casamento real, da campanha
eleitoral, da morte do Papa, a imprensa escrita
tinha registado uma quebra. E garantia que esta
só não tinha sido maior por causa da adesão
maciça ao Su Doku, agora transformado em vício
nacional.
A febre ameaça espalhar-se pelo resto do
Ocidente. Os puzzles de números desembarcam
paulatinamente na Europa Ocidental, já voltaram
aos Estados Unidos e a semana passada começaram a
ser usados por jornais norte-americanos.
Parece inexplicável, num século XXI tão
tecnológico, este êxito de uma grelha de nove
quadrados por nove, em que só é preciso preencher
as 81 casas para que cada fila, coluna e quadrado
contenha os números de 1 a 9, sem repetições. Mas
os fenómenos raramente têm uma explicação. Este
fenómeno está a partir de hoje na última página
do PÚBLICO.
posted by raiva at 5:05 AM
2 Comments:
A Matemática do Sudoku
Jorge Buescu
Professor de Matemática
IST
Em 2005, o Sudoku tomou o mundo de assalto. Até nas famosas aulas de prolongamento do Ensino Básico ele foi adoptado pelos professores. Mas... será Matemática?
Um dos fenómenos mediáticos do ano de 2005, que certamente não passou despercebido ao leitor, foi o do puzzle com o nome de Sudoku. Todos os jornais, diários, desportivos e até os vulgares guias de TV começaram a publicar problemas de Sudoku, ao lado dos horóscopos e palavras cruzadas. Ainda que dificilmente o leitor possa hoje em dia ignorar as regras, eis uma breve descrição do Sudoku.
Parte-se de um quadrado 9X9 formado por 9 subquadrados 3X3 (“regiões”). Cada um destes subquadrados está parcialmente preenchido com números entre 1 e 9 (“dados”). O objectivo é preencher todo o quadrado 9X9 com os números 1 a 9 de tal forma que (1) em cada linha e em cada coluna do quadrado 9X9 cada algarismo entre 1 e 9 apareça uma e uma só vez, (2) em cada uma das regiões 3X3 cada algarismo entre 1 e 9 apareça uma e uma só vez. Ao que se diz, o Sudoku é um puzzle com o poder viciante do crack: basta experimentar uma vez e é-se agarrado.
Se o leitor gosta de Sudoku e está a ler este artigo especificamente interessado em estratégias para resolver problemas de Sudoku, pode parar por aqui: o autor nunca terminou um único problema sequer (nem tenciona, de resto, vir a fazê-lo). Enquanto matemático, o interesse é outro: tentar responder à pergunta frequente “Mas o Sudoku é Matemática, não é? Afinal, até tem números!”.
A resposta sobre se o Sudoku é Matemática é “não”. Mas também é, a um nível mais profundo, “sim”.
Vamos por partes. No sentido superficial em que a pergunta é geralmente feita, a resposta é um claríssimo “não”. Nem toda a Matemática tem números (na verdade, a maior parte da Matemática não tem números); inversamente, nem tudo o que tem números é Matemática (o Relatório e Contas da empresa onde o leitor trabalha está cheio de números mas dificilmente implicará Matemática mais sofisticada do que a aritmética da escola primária).
No caso particular do Sudoku, a irrelevância de “conter números” para decidir sobre o “conteúdo matemático” é óbvia: basta substituir cada um dos números entre 1 e 9 por um qualquer outro símbolo para se obter exactamente o mesmo problema. Por exemplo, se se substituir o algarismo 1 por uma estrela, o 2 por uma bola, o 3 por uma cruz, e assim por diante, o problema do Sudoku fica exactamente na mesma. Tal como se se substituir cada número por, digamos, uma de 9 cores diferentes. Os números estão no Sudoku apenas porque são 9 símbolos que estamos muito habituados a reconhecer e distinguir, não porque cumpram qualquer função matemática no problema.
Assim, o Sudoku é simplesmente um passatempo de tipo cruzadístico com a característica suplementar de, por utilizar símbolos não-alfabéticos, ser independente da linguagem: ao contrário das palavras cruzadas, o mesmo problema de Sudoku faz tanto sentido em Portugal como em Inglaterra, na Alemanha, no Japão ou na China. No entanto, tal como nas palavras cruzadas, a sua resolução implica apenas a utilização da lógica, não da Matemática. Nem sequer envolve aritmética elementar. Assim, a este nível superficial a resposta é: não, o Sudoku nada tem a ver com Matemática. Resolver um problema de Sudoku tem tanto de actividade matemática como resolver passatempos de palavras cruzadas. O que provavelmente explica o absoluto desinteresse do autor destas linhas na resolução do Sudoku.
Contudo, a resposta muda bastante de figura se a pergunta for “qual é a Matemática relacionada com o Sudoku?”.
Em 1779 foi colocado o seguinte problema ao matemático Leonhard Euler. Suponhamos que temos trinta e seis oficiais do exército com a seguinte proveniência: cada um de seis diferentes regimentos nomeou seis representantes, tendo cada um destes representantes uma de seis diferentes patentes militares. Por exemplo, cada regimento nomeou um coronel, um tenente-coronel, um major, um capitão, um tenente e um subtenente. Pergunta: é possível dispor os trinta e seis oficiais num quadrado com seis linhas e seis colunas de forma a que em nenhuma linha ou coluna apareçam repetidos nem o regimento nem a patente? O viciado em Sudoku poderá estar interessado em deixar de ler neste ponto e pensar neste problema.
Para tentar resolver o problema, Euler foi conduzido à definição daquilo que hoje se chama um quadrado latino. Um quadrado latino de ordem n é um quadrado nXn em que cada célula está preenchida com um de n símbolos diferentes, sujeito à condição de que cada símbolo surge uma e uma só vez em cada linha e coluna. Apresenta-se na Figura 1 exemplos de quadrados latinos de ordem 3 e de ordem 4. O adjectivo latino provém do facto de Euler ter utilizado como símbolos não números, como no Sudoku, mas letras do alfabeto latino, como fazemos no quadrado de ordem 4. Assim, até no nome está patente a irrelevância de os símbolos serem ou não números.
Um problema de Sudoku corresponde, assim, à construção de um tipo particular de quadrado latino 9X9 – um quadrado latino em que cada “região” (subquadrado 3X3) contém todos os símbolos de 1 a 9. Assim, a Matemática que está por trás do Sudoku é a Matemática dos quadrados latinos.
Os quadrados latinos são entidades combinatoriais que surgem nos contextos mais inesperados. Por exemplo, as tabelas de multiplicação de grupos finitos (e mesmo de quasegrupos) são dadas por quadrados latinos. Outro exemplo mais concreto é a determinação de calendários desportivos. Se o leitor é adepto de futebol (ou de voleibol, ou andebol, ou hóquei em patins, ou qualquer jogo em que o campeonato se disputa num regime de todos contra todos), sabe bem que num campeonato com 18 equipas, como a nossa Liga de Futebol, a sua equipa tem de disputar 17 jogos (a segunda volta é a repetição da primeira).
Agora, imagine que lhe é pedido para organizar um torneio de futebol no regime de todos contra todos. Isto é, quer construir uma sucessão de 17 jornadas, com 9 jogos cada uma, tal que ao fim das 17 jornadas cada equipa jogou uma e uma só vez contra cada uma das outras. Sugiro que antes de continuar a ler tente fazê-lo. Se acha demasiado complicado tente com um número mais pequeno (mas par) de equipas – digamos, 6.
Para 4 equipas é fácil encontrar uma solução: na 1.ª jornada os jogos são 1-2 e 3-4; na 2.ª jornada são 1-3 e 2-4; na 3.ª jornada são 1-4 e 2-3. Esta informação pode ser coligida na Figura 2; na linha i estão os jogos da equipa i, na coluna j os da equipa j, e o número na célula ij indica em que jornada a equipa i defronta a equipa j.
Fig. 2 - Calendário possível para um campeonato com 4 equipas
Observe-se que, se a diagonal (obviamente vazia) for preenchida com o número 4, obtém- -se um quadrado latino de ordem 4. Mais: esse quadrado é simétrico em relação à diagonal (se A joga com B na jornada k, então B joga com A na jornada k).
O problema do calendário do campeonato com 2n equipas é, assim, uma curiosa variação sobre o Sudoku: construir um quadrado latino simétrico de ordem 2n. Não é difícil fazê-lo, por exemplo, a partir da tabela de adição do grupo soma modular (mod 2n-1).
O leitor interessado em fazê-lo pode começar por observar que, se na Figura 2 eliminar a diagonal em branco e realizar a “fusão” dos dois triângulos que sobram sobrepondo as duas diagonais (1-3-1), obtém um quadrado latino simétrico 3X3 que representa a soma modular (mod 3), com a única diferença que o sistema de resíduos é {1,2,3} em vez do usual {0,1,2}. Inversamente, dado um número par arbitrário 2n, se partir da tabela de adição modular (mod 2n-1) e realizar o processo de “fissão” em dois triângulos e deixando a diagonal em branco, obtém o seu calendário desportivo. É interessante constatar que, quando a Liga de Clubes procede no Verão ao sorteio do calendário dos clubes para a próxima época de futebol, o que está na verdade a acontecer é muito simples: a Liga de Clubes dispõe à partida de um quadrado latino simétrico 18X18, que determina a época desportiva; a única coisa que se sorteia in loco é a atribuição de cada um dos 18 números correspondentes às linhas e colunas do quadrado latino a cada um dos clubes. O mesmo é verdade, evidentemente, para qualquer campeonato em sistema de “todos-contra-todos”, desde hóquei em patins a berlinde.
Os quadrados latinos são por vezes utilizados em concepção de experiências, para proteger contra enviesamentos estatísticos. Suponhamos, por exemplo, que temos 6 castas de uva e queremos verificar qual a que se dá melhor num terreno. Como podem existir variações nas características do terreno, o melhor procedimento experimental será distribuir 6 amostras de cada casta num quadrado latino 6X6, para diminuir os efeitos médios desta variação.
Haverá alguma vez falta de quadrados latinos? Acabará num futuro próximo, como o petróleo, o stock de problemas de Sudoku? Embora não se conheça uma fórmula explícita para o número de quadrados latinos de ordem n para todo o n, conhecem-se os primeiros valores: por exemplo, há apenas um quadrado latino de ordem 1, dois de ordem 2, e doze de ordem 3.
Como se vê na Figura 3, o número de quadrados latinos cresce de uma forma assustadora com a ordem. Ninguém sabe de quantas formas diferentes se pode organizar a calendarização de um campeonato de futebol como a Liga Portuguesa (n=18, simétricos), mas é muito superior a 10100.
Os problemas de Sudoku correspondem a um subconjunto estrito do caso n=9 (correspondente à restrição suplementar de cada “região” 3X3 utilizar todos os algarismos de 1 a 9). O número total de problemas distintos é, pois, mais pequeno: cálculos combinatórios mais ou menos sofisticados permitem mostrar que este número é 6.670.903.752.021.072.936.960, ou mais de 1021. Portanto, é natural que o interesse pelo Sudoku arrefeça antes que se esgotem todos os problemas possíveis...
Finalmente, regressemos ao problema de Euler, ou dos 36 oficiais. Ele é mais complexo do que qualquer Sudoku: corresponde a exigir que os 36 oficiais formem um quadrado latino 6X6 Q1 relativamente às patentes, um outro quadrado latino Q2 relativamente aos regimentos, e que os dois quadrados sobrepostos originem uma e uma só vez todos os possíveis pares ordenados de 6 elementos. Dois quadrados latinos com estas propriedades chamam-se ortogonais.
É trivial verificar que não há quadrados latinos ortogonais de ordem 2. Para ordem 3, eles existem: por exemplo, o quadrado 3X3 apresentado na Figura 1 é ortogonal a como o leitor pode verificar. Assim, se o problema de Euler fosse relativo a 9 oficiais, e não 36, este par de quadrados forneceria uma solução.
Dado o crescimento supra-exponencional do número de quadrados latinos, seria de esperar que quanto maior a ordem, mais pares de quadrados ortogonais existissem. Por exemplo, há mais de 812 milhões de quadrados latinos de ordem 6; seria muito estranho que nenhum par fosse ortogonal. Seria muito estranho. Mas é verdade, e era provavelmente conhecido por Euler: não existem pares de quadrados latinos ortogonais de ordem 6. O problema dos 36 ofi ciais é impossível! Estas observações conduzem, com “alguma” naturalidade, à famosa conjectura de Euler sobre quadrados latinos: se a ordem é 2, 6, 10, 14..., ou seja, 4k+2, então não existem pares de quadrados ortogonais.
Os problemas combinatóricos, como esta conjectura, muito facilmente se tornam intratáveis. A conjectura de Euler resistiu 180 anos. Nova surpresa: em 1959 os matemáticos Parker, Bose e Shrikhande mostraram que ela é (quase totalmente) falsa: existem sempre pares de quadrados latinos ortogonais, excepto para n=2 e n=6. Ou seja, o problema dos oficiais tem sempre solução, excepto se forem 4 ou 36...
http://www.ordemengenheiros.pt/Default.aspx?tabid=1862
Post a Comment
<< Home