Implementação (em Python) do algoritmo “Passeio do cavalo no tabuleiro

[nkzao]

Eu tava precisando de ajuda em um trabalho q tenho pra fazer ...

1. Introdução - Backtracking (Técnica de Tentativa e Erro)

Uma área muito interessante de projeto de algoritmos é quando se quer achar soluções para

problemas que não se conhece uma regra fixa de computação. Nesse caso, uma possível

alternativa é a técnica de tentativa e erro. Nesse tipo de problema, a abordagem mais comum é

decompor o processo em um número finito de tarefas parciais. Geralmente as tarefas são

expressas naturalmente em termos recursivos e devem ser exploradas de forma exaustiva. A

construção de uma solução é obtida através de tentativas (ou pesquisas) da árvore de sub-tarefas.

A técnica de tentativa e erro pode ser melhor explicada através de um exemplo: O Passeio do

Cavalo (Knight’s Tour). Seja um tabuleiro nxn com n2 posições e um cavalo que move seguindo as

regras do xadrez. O cavalo é colocado numa posição inicial (x0; y0). O objetivo do problema é

encontrar, se existir, um passeio do cavalo com n2 - 1 movimentos tal que todas as posições do

tabuleiro são visitadas uma única vez.

Algoritmos que usam a técnica de tentativa e erro não seguem uma regra fixa de computação. Em

geral, os passos em direção à solução final são tentados e registrados numa estrutura de dados.

Caso esses passos tomados não levem à solução final do problema, eles podem ser retirados e

apagados do registro.

2. Trabalho Prático

O trabalho consiste na implementação (em Python) do algoritmo “Passeio do cavalo no tabuleiro

de xadrez”.

Desde já

Obrigado