Heurística para o passeio aberto do cavalo em tabuleiros multidimensionais

Resumen

Não se conhece algoritmo exato que resolva eficientemente o problema de encontrar um passeio aberto do cavalo em um tabuleiro de xadrez n  n, para n arbitrário e a partir de qualquer casa inicial. Um tal passeio consiste em uma sequência onde cada casa do tabuleiro aparece exatamente uma vez, e onde duas casas consecutivas estão separadas, no tabuleiro, pelo típico movimento do cavalo (em “L”), pelo qual o cavalo desloca-se duas unidades em uma dimensão e apenas uma unidade na outra dimensão. Em [1], propusemos uma heurıstica linear que obteve êxito em 100% dos casos testados, correspondendo a todas as casas iniciais plausíveis de tabuleiros quadrados com 5  n  5000. Neste trabalho, consideramos a extensão de tais resultados para tabuleiros d-dimensionais com n1  n2  . . .  nd casas. O movimento do cavalo, em d dimensões, tem preservada sua caracterıstica original, provendo um deslocamento de duas unidades em alguma dimensão, de uma unidade em outra dimensão, e mantendo inalteradas as coordenadas do cavalo nas demais dimensões. Em 1991, Schwenk [4] caracterizou os tabuleiros retangulares bidimensionais que admitem passeio fechado do cavalo, isto é, um passeio em que o cavalo, após passar por cada casa do tabuleiro exatamente uma vez, retorna em um único movimento para a casa inicial. Recentemente, Joshua Erde, Bruno Golénia e Sylvain Golénia estudaram a versão d-dimensional do problema [2]. Por se tratar de uma generalização do problema original, a frase que abre este resumo implica que ainda não é conhecido qualquer algoritmo eficiente para exibir um passeio aberto em d dimensões. Em face disto, nossa primeira abordagem, neste trabalho, consistiu em aplicar a mesma heurística bem-sucedida proposta em [1], adaptando-a para tabuleiros em d dimensões. A heurística adaptada consiste de quatro critérios para se decidir qual será a próxima casa a ser visitada pelo cavalo, a cada momento durante a construção do passeio. O primeiro deles é a conhecida regra de Warnsdorff [5]. Por essa regra, as casas ainda não visitadas que são atingíveis da casa atual do cavalo são avaliadas segundo a quantidade de casas não visitadas que poderão ser atingidas, no passo seguinte, a partir de cada uma delas. É escolhida, então, aquela que minimizar essa quantidade. Intuitivamente, a ideia é tentar sempre atacar primeiro as maiores restrições, visto que adiar a visita a casas que já apresentem poucas continuações possíveis pode ser fatal, uma vez que elas podem se tornar sumidouros, becos sem saída que não permitiriam ao cavalo prosseguir, exigindo por exemplo uma estratégia de backtracking que destruiria qualquer possibilidade de se obter o passeio em tempo linear. Em caso de empate de duas ou mais casas com respeito à regra de Warnsdorff, passa-se ao segundo critério, de acordo com o qual é priorizada a casa que se encontre mais próxima a um dos “cantos” do tabuleiro. Em d-dimensões, um canto é qualquer casa cujas coordenadas são todas extremas, isto é, uma casa cuja j-ésima coordenada é 0 ou nj  1, para 1  j  d. Em caso de novos empates, passa-se ao terceiro critério. O terceiro critério recomenda a escolha da casa mais próxima a uma das “bordas” do tabuleiro, bolsista de Iniciação Cientıfica PIBIC/CNPq que, para tabuleiros multidimensionais, seriam as casas com alguma — mas não todas — coordenada extrema. Até aqui, ativemo-nos à ideia intuitiva de atacar primeiro as maiores restrições. Como desempate final, caso necessário, passa-se ao quarto e último critério: randomização. Escolhe-se ao acaso uma das casas empatadas. Caso um passeio aberto não seja obtido, repete-se todo o algoritmo um número k constante de vezes. No caso bidimensional, o quarto critério com a abordagem randomizada havia se provado tão eficaz quanto o critério determinístico mais elaborado que foi apresentado em [1], mesmo para um k fixo tão pequeno quanto k  16, e independentemente do tamanho do tabuleiro. No entanto, heurística semelhante não obteve, em d  2 dimensões, a mesma taxa de 100% de sucesso obtida para d  2. Concebemos, então, uma maneira alternativa de utilizar a heurística de [1] no caso multidimensional. Ao invés de atacar o tabuleiro multidimensional como um todo, permitindo ao cavalo mover-se livremente (desde que respeitando seu movimento típico) por todo o hiperespaço discreto das casas do tabuleiro, passamos a enxergar um tabuleiro em d dimensões como um agrupamento de tabuleiros de apenas d 1 dimensões. Dessa forma, temos que, por recursão, todo o tabuleiro pode ser visto como um conglomerado de tabuleiros convencionais, em apenas duas dimensões. Decompondo assim o problema, e atacando um sub-tabuleiro bidimensional por vez, pudemos empregar na versão multidimensional a heurística 100% bem-sucedida proposta em [1]. A ideia é manter todas as coordenadas do cavalo fixas, exceto duas, e utilizarmos a heurística bidimensional para resolver todo aquele sub-tabuleiro. Passamos então para o próximo sub-tabuleiro, isto é, para a próxima fatia bidimensional do tabuleiro original em d dimensões. Para isso, basta o cavalo executar um movimento que o desloque   {1, 2} unidades em uma daquelas mesmas duas dimensões do último sub-tabuleiro completamente resolvido, e 3 unidades em uma das dimensões que estavam fixas, levando-o assim a certa casa inicial (arbitrária) de um novo tabuleiro bidimensional ainda totalmente não-visitado. Procedendo desta forma para todos os tabuleiros bidimensionais que compõem o tabuleiro original, o cavalo percorre todas as casas, no que constituirá o passeio aberto desejado. É possível mostrar que o método proposto funciona sempre que houver duas dimensões i, j, com 1  i  j  d, satisfazendo ni  nj  5, e sendo ni e nj pares. Quando não houver duas tais dimensões, o método não funciona para todas as casas iniciais. Uma das razões para isto é o fato de que, em um tabuleiro bidimensional com um número ımpar de casas, casas pretas e casas brancas não ocorrem em igual quantidade, mas com a diferença de uma unidade entre elas. Dessa forma, é necessário iniciar o passeio de uma casa cujas coordenadas (x, y) satisfaçam xy  0 (mod 2), isto é, de uma casa com cor igual à de um canto do tabuleiro, pois é essa a cor das casas que aparecem em maior quantidade — e o movimento do cavalo é tal que de uma casa branca o cavalo sempre passa a uma casa preta, e vice-versa. Uma segunda razão é o fato de que a própria heurística original de[1], aqui adaptada, não obtém caminho aberto a partir de todas as casas iniciais em tabuleiros bidimensionais não-quadrados.