Oito damas, cavalo de Euler, tabuleiro mutilado: os grandes quebra-cabeças matemáticos do tabuleiro

Estes quebra-cabeças jogam-se com as peças ou com a quadrícula do tabuleiro, mas não têm nada a ver com uma partida: são verdadeiros problemas de matemática, acessíveis desde o 3.º ciclo, e alguns ocuparam grandes nomes da disciplina. São ideais para um clube de matemática, uma apresentação ou um tema de exame oral.

Quadro-resumo

O problema das oito damas

Problema das oito damas

Colocar oito damas num tabuleiro de 8 × 8 de forma que nenhuma possa capturar outra: nunca duas damas na mesma linha, na mesma coluna ou na mesma diagonal.

O problema foi publicado em 1848 por Max Bezzel, um compositor de problemas de xadrez. Franz Nauck publicou as primeiras soluções em 1850 e generalizou-o para n damas num tabuleiro de n × n casas. Carl Friedrich Gauss figura entre os matemáticos que se interessaram por ele.

Objetivo do problema: encontrar uma disposição e, depois, todas. Existem 92. Muitas deduzem-se umas das outras por rotação ou simetria do tabuleiro; se as agruparmos, restam 12 soluções fundamentais. Eis uma delas, com as damas em d8, g7, c6, h5, b4, e3, a2 e f1:

Verifica-se facilmente que há uma dama por linha e por coluna. Quanto às diagonais, basta confirmar que, para duas damas quaisquer, a diferença de colunas nunca é igual à diferença de linhas.

Como se resolve?

O método clássico é o retrocesso (em inglês backtracking): coloca-se uma dama na primeira coluna, depois uma dama na segunda coluna numa casa não atacada, e assim por diante; quando nenhuma casa é possível, recua-se e desloca-se a dama anterior. É um exercício muito apreciado nas aulas de informática do secundário. A versão com n damas tem soluções para todo o n exceto 2 e 3: por exemplo, 2 soluções para n = 4, 10 para n = 5, 4 para n = 6, 40 para n = 7.

O problema do cavalo de Euler

Problema do cavalo

Encontrar uma sequência de lances de cavalo que passe uma só vez por cada uma das 64 casas. O percurso diz-se fechado se a última casa estiver a um salto de cavalo da primeira, o que permite recomeçar o ciclo.

O problema é muito antigo: um percurso do cavalo num meio tabuleiro já figura num tratado de poética sânscrita do século IX, o Kavyalankara de Rudrata. Leonhard Euler dedicou-lhe uma memória, « Solution d'une question curieuse qui ne paroit soumise à aucune analyse », apresentada em 1759 e publicada em 1766 nas memórias da Academia de Ciências de Berlim. Em 1823, H. C. von Warnsdorff propôs uma regra simples para encontrar um percurso: ir sempre para a casa de onde o cavalo tenha o menor número possível de saídas.

Existe um número gigantesco de percursos fechados no tabuleiro comum: 26 534 728 821 064 contando o sentido do percurso, ou metade, 13 267 364 410 532, se considerarmos que um percurso e o seu inverso são o mesmo.

Um percurso para verificar num tabuleiro de 5 × 5

Para treinar, pode começar-se por um tabuleiro mais pequeno. Eis um percurso aberto que visita as 25 casas de um tabuleiro de 5 × 5: siga os números de 1 a 25; cada número está a um salto de cavalo do anterior.

Este percurso foi obtido com a regra de Warnsdorff, e cada salto foi verificado. Desafio: encontrar outro que comece no centro.

O problema do cavalo no exame oral

O tema presta-se bem à prova oral do exame nacional de matemática ou de informática: modelação por um grafo (as casas são os vértices, os saltos possíveis são as arestas), procura de um caminho que passe por todos os vértices, algoritmo de retrocesso, regra de Warnsdorff e a sua eficácia. Pode também explicar-se por que não existe percurso fechado num tabuleiro de 5 × 5: o cavalo muda de cor a cada salto, logo um ciclo tem necessariamente um número par de casas, ora 25 é ímpar.

O tabuleiro mutilado

O filósofo Max Black apresentou o problema em 1946 no seu livro Critical Thinking. Retiram-se dois cantos opostos de um tabuleiro (por exemplo a1 e h8). É possível cobrir as 62 casas restantes com 31 dominós, cada dominó cobrindo duas casas vizinhas?

Resposta: não. Cada dominó cobre necessariamente uma casa branca e uma casa preta. 31 dominós cobririam, portanto, 31 casas brancas e 31 pretas. Ora os dois cantos opostos são da mesma cor: restam 32 casas de uma cor e 30 da outra. A cobertura é impossível, sem ser preciso experimentar uma única disposição. Martin Gardner deu a conhecer este problema ao grande público em 1957, na sua rubrica da Scientific American.

E se retirarmos uma casa branca e uma casa preta? Ralph Gomory demonstrou (resultado publicado em 1973) que a cobertura é então sempre possível, quaisquer que sejam as duas casas retiradas.

Poliominós e pentominós

Um poliominó é uma figura formada por quadrados iguais colados pelos lados; o dominó tem dois, o pentominó cinco. O matemático Solomon Golomb introduziu e estudou estas figuras a partir de 1953. Existem 12 pentominós diferentes (considerando que uma peça virada ou rodada continua a ser a mesma), que juntos cobrem 60 casas.

Ora um tabuleiro tem 64 casas, ou seja 60 + 4: pode-se, pois, procurar dispor os 12 pentominós no tabuleiro deixando livre um quadrado de 2 × 2 no centro. Em 1958, Dana Scott mandou resolver este problema por um computador, um dos primeiros usos do método de retrocesso: existem 65 soluções. Outro desafio célebre: o retângulo de 6 × 10 pode ser coberto de 2 339 maneiras diferentes com os 12 pentominós.

Quantos quadrados há num tabuleiro?

A resposta « 64 » está errada, ou antes incompleta: conta apenas os quadradinhos. É preciso contar também os quadrados de 2 × 2, de 3 × 3… até ao grande quadrado de 8 × 8.

O total é a soma dos quadrados dos inteiros de 1 a 8: 1 + 4 + 9 + … + 64 = 204. Para ir mais longe: um tabuleiro contém 1 296 retângulos (quadrados incluídos), pois um retângulo fica determinado pela escolha de 2 linhas entre as 9 linhas da quadrícula e de 2 colunas entre 9, ou seja 36 × 36.

Para continuar

Estes problemas mobilizam noções precisas: paridade, coloração, contagem, grafos. Detalhamo-las, com exercícios para o 1.º e 2.º ciclos, na página as noções matemáticas mobilizadas no tabuleiro. Para outros números muito grandes, veja-se o tabuleiro de Sissa. E para quem gosta de enigmas, o blogue do Palais des Échecs propõe os desafios de lógica do Palais des Échecs, renovados regularmente.