Caminhos em Tabuleiros de Xadrez – 2
No Enigma da Semana “Caminhos em Tabuleiros de Damasco – 1”, analisamos quando era possível, partindo de um ponto específico, criar um caminho em um tabuleiro de damas que visitasse todas as casas. Partindo do ponto preto, o primeiro tabuleiro de damas 3x4 possui um caminho, enquanto o segundo tabuleiro de damas 3x5 não.
Neste enigma, temos um ponto de partida e um ponto de chegada, e a questão é se existe um caminho que começa em um ponto e visita cada ponto exatamente uma vez até terminar no outro ponto.
O DESAFIO
Para esses dois tabuleiros de damas, identifique quais pares de posições inicial e final possuem um caminho que as conecta, visitando cada casa do tabuleiro uma vez, e quais não possuem. Qual é a diferença?
EXPLORAÇÃO
Crie tabuleiros de xadrez de outros tamanhos e experimente diferentes posições iniciais neles. Você consegue?
Você consegue identificar algum padrão em relação às posições iniciais que funcionam em cada tabuleiro?
Notas
O DESAFIO E A EXPLORAÇÃO
Em “Caminhos em Tabuleiros de Xadrez – 1”, vimos que a sequência de cores em um caminho se alterna à medida que se avança ao longo dele.
Como vimos no quebra-cabeça anterior, em tabuleiros de damas com um número par de casas, como o tabuleiro 3x4, devemos terminar na cor oposta à cor inicial. Em tabuleiros de damas com um número ímpar de casas, como o tabuleiro 3x5, devemos começar e terminar na cor que está em um dos cantos do tabuleiro.
Isso nos leva à seguinte questão: se seguirmos essas regras, será suficiente?
Uma maneira de analisar essa questão é definir a posição de um dos pontos e verificar quais são todos os pontos finais para bons caminhos. Podemos explorar a simetria de espelho (invertendo o centro do tabuleiro em uma direção ou na outra) para reduzir o número de casos possíveis a serem analisados. Aqui está o que obtemos para os dois tabuleiros. O ponto vermelho representa um ponto de partida fixo e os pontos pretos representam locais com pontos finais válidos.
Como você pode ver, a maioria das posições funciona. Para as que não funcionam, o problema não é a alternância de cores, mas sim o confinamento nos cantos. Esse problema de confinamento é ainda mais problemático em tabuleiros com apenas duas fileiras. Acredito que, para quatro ou mais fileiras, esse problema desaparece.