Navegar

08/03/2023

Para que serve o problema do passeio do cavalo no xadrez?

 

Reprodução da coluna de Marcelo Viana na Folha de S. Paulo

Anos atrás, uma colega me recomendou o livro “A Vida Modo de Usar” do francês Georges Perec, vencedor do prestigioso prêmio Médicis em 1978. Dizer que fiquei fascinado seria pouco. A forma meticulosa, obsessiva, como Perec descreve até a última minúcia o conteúdo –mobiliários, decorações, acessórios– e as histórias dos cômodos de um edifício parisiense, para construir um quebra-cabeças vertiginoso das vidas e pensamentos de seus moradores, não poderia ser mais diferente de qualquer coisa que eu tivesse lido antes (ou depois).

O que eu não sabia na época era que a estrutura dessa obra notável está baseada num problema matemático antigo e famoso. Perec concebe o prédio como um “tabuleiro”, formado por dez cômodos em cada um dos dez andares, e faz com que a sua narrativa se desloque nesse tabuleiro conforme o movimento do cavalo no xadrez: duas casas numa direção e uma na direção ortogonal. Assim, o livro contém uma solução para o problema do passeio do cavalo num tabuleiro com dez linhas e dez colunas.

Leia mais: Secretária de Ambiente e Clima do Rio visita sede do IMPA
Aluno do IMPA se dedica à combinatória desde a escola
IMPA desenvolve projeto de machine learning para Hurb

Contei na semana passada que esse problema –percorrer com um cavalo todas as casas do tabuleiro de xadrez sem passar duas vezes pela mesma casa– remonta ao século 9°, na Índia. No Ocidente, o primeiro a estudá-lo de forma sistemática foi Leonhard Euler, em 1759. Ele encontrou um método para calcular soluções e percebeu que elas existem em grande número.

Em 1823, o alemão H. C. von Warnsdorf propôs uma regra heurística para calcular soluções: em cada passo, o cavalo deve ser deslocado para a casa acessível “menos promissora”, aquela a partir da qual o número de movimentos disponíveis no passo seguinte será menor. Esse método é bastante eficiente e foi implementado computacionalmente em 1984.

Assim, o “problema curioso” que chamou a atenção de Euler mais de 250 anos atrás continua motivando progresso científico. Entre os avanços recentes está o uso de inteligência artificial para encontrar passeios do cavalo de modo eficiente. 

Para ler o texto na íntegra acesse o site do jornal.

Leia também: Diego Guajardo conclui ciclo de oito anos no IMPA
Inscrições para 18ª OBMEP terminam em 17 de março