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.

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.

Não precisamos nos ater ao tabuleiro oito por oito usual do xadrez: o problema tem sido estudado também para tabuleiros retangulares gerais, com qualquer número de linhas e de colunas. Em 1991, o norte-americano A. Schwenk caracterizou quais tabuleiros possuem passeios do cavalo. Em particular, sabemos que tais passeios sempre existem se os números de linhas e de colunas forem ambos maiores do que quatro. Além disso, nesse caso existem passeios fechados, ou seja, que voltam à casa de partida, desde que o número de casas do tabuleiro seja par.

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. A ideia é usar redes neurais em que cada possível movimento do cavalo é representado por um "neurônio". A rede pode então ser treinada para ativar neurônios que formem uma solução e desativar os demais. Tais algoritmos podem ser aplicados em diversos problemas práticos.