Implementação do Problema do Cavalo em C++ com Backtracking

Prévia do material em texto

Ministério da Educação Engenharia da Computação
Universidade Federal de Itajubá ECOI11 – PAA
Criada pela Lei nº 10.435, 24/04/2002 Prof. Giovani Bernardes Vitor
Treinamento#2
Obs.: Os códigos deverão ser enviados SOMENTE em arquivos com extensão .c, c++, .h
e .hpp. Não envie arquivo PDF como resposta para o desenvolvimento dos algoritmos.
Matŕıcula e nome completo:
Matŕıcula e nome completo:
Matŕıcula e nome completo:
1. Com base na técnica de projeto de algoritmos, em especial o backtracking, implemente uma
codificação em C++ do problema da cavalo usando classe e recursão. Tome como base o
pseudo algoritmo apresentado nas notas de aula.
Obrigatoriamente, a classe que será desenvolvida deverá conter os seguintes métodos:
� void realizaPasseio(); // Este método inicializa a execução do passeio do cavalo
para encontrar uma solução, admitindo que a posição inicial é sempre a coordenada
(0,0) do tabuleiro, onde o cavalo inicia.
� bool tentativa(posicao <variável>); // Método para realizar a tentativa de pas-
seio do cavalo em uma dada posição do tabuleiro, retornando verdadeiro se obteve
sucesso.
� bool e aceitavel(posicao <variável>); // Método que verifica se a posição é
aceitável, retornando verdadeira caso positivo.
� bool esta cheio(); // Método para avaliar se o tabuleiro está cheio.
Figura 1: Movimentos do cavalo.
A Figura 1 apresenta todos os posśıveis movimentos do cavalo. Ressalta-se que o tipo de
variável posicao é dado pela seguinte estrutura:
1 struct pos i cao {
2 int x , y ;
3 } ;
Boa atividade...