Sábado, 23 de Abril de 2005
Salto de cavalo
Quem diria que há um algoritmo extremamente simples para gerar aleatoriamente os mais diversos caminhos para o salto de cavalo (testado numa quadrícula de 11 x 11)?



por MCV às 01:41
endereço

3 comentários:
De Anónimo a 23 de Abril de 2005 às 14:04
Ora bem, meus amigos, como devem ter percebido meti-me a construir um vulgar salto de cavalo daqueles que apareciam nos jornais antigamente. Suponho que ainda existirão nessas revistas especializadas de quebra-cabeças.
Ao fazê-lo, percebi que não era assim à primeira que se conseguia preencher a quadrícula sem repetição. Mas isso é o preâmbulo.
Suponho que este assunto será até coisa já batida e bem estudada. Se não com este propósito, decerto com outros.
Fiz em excel uma rotina que preenchesse aleatoriamente a quadrícula. Na grelha 11 x 11 (121 quadrados) o melhor que obtinha era aí uns 70 ou 80 quadrados preenchidos.
Depois, introduzi uma pequena "inteligência" na coisa: quando o cavalo está numa determinada casa, ele verifica qual ou quais das oito (se oito forem) casas para que pode saltar, oferece MENOR expectativa de continuidade - ou seja tem ela menor número de casas livres para a jogada subsequente. Escolhendo essa ou uma dessas, a probabilidade de conseguir chegar ao final é, creio - que ainda não fiz a conta - superior a 95%.
Agora, uma questão: aqueles saltos de cavalo antigos dos jornais seguiam um número limitado de percursos bem conhecidos ou há um método ainda mais simples para criar estes trajectos?
Quanto ao xadrez, Ordisi, o problema é a profundidade da análise. Aqui, apenas se explora o nível seguinte. Esses algoritmos que aí há, exploram uma imensidão de níveis subsequentes, o que dá a tal complexidade de cálculo e a exigência de capacidade e de rapidez para a coisa ser eficiente.
Mas que estas coisas são o tal bichinho que se nos mete, lá isso são.
Um abraço aos dois.
Ah, outra coisa: os tais saltos de cavalo dos jornais eram em grelhas 8 x 8 ou 11 x 11, à semelhança da maioria das palavras cruzadas?Manuel
</a>
(mailto:gasolim@hotmail.com)


De Anónimo a 23 de Abril de 2005 às 03:24
A saber?...Santos Passos
(http://santospassos.blogspot.com)
(mailto:santos.passos@uol.com.br)


De Anónimo a 23 de Abril de 2005 às 03:15
Há séculos tentei escrever um programa para o computador jogar xadrês (em Fortran!). Nada! Fiquei perdido. Depois a coisa ficou comum, mas eu ainda não tenho idéia dos métodos, como esse algorítmo aí que você fala. Abrs.OrdisiRaluz
(http://ordisiraluz.zip.net)
(mailto:ordisi@uol.com.br)


Comentar post

ANO XV


EDITORIAL
. Posts recentes

Mourão, 2017

Albufeira de A...

Restos de colecção (82...

Fátima e o resto

Portugal, 2009

Rio Mira, 1988...

Alvor, 1989

São Salvador do Mundo,...

Janas, 2006

Portugal, 2008

. Arquivos
. Links