UFSM > Ciência da Computação

Primeiro Semestre de 2013
Professora: Juliana Kaizer Vizzotto

Trabalho de Matrizes

1. Passeio do cavalo: Um dos desafios mais interessantes que os jogadores de xadrez enfrentam é o problema do Passeio do Cavalo, proposto originalmente pelo matemático Euler. O problema é o seguinte: a peça do xadrez chamada cavalo pode se movimentar por um tabuleiro de xadrez vazio e tocar cada uma dos 64 quadrados uma, e somente uma, vez? Vamos estudar esse problema e resolvê-lo em partes.

2. O cavalo se movimenta em forma de L (por duas casas em uma direção e depois por uma casa em uma direção perpendicular). Assim, por um quadrado no meio de um tabuleiro vazio, o cavalo pode fazer oito movimentos diferentes (numerados de 0 até 7). Preste atenção na explicação da profa. no quadro :)

3. Você deve fazer os seguintes exercícios:
   1. Vamos desenvolver um programa que movimentará o cavalo em um tabuleiro. O tabuleiro é representado por uma matriz 8X8. Cada um dos quadros é inicializado com 0.
   2. Descrevemos cada um dos 8 movimentos possíveis em termos de seus componentes vertical e horizontal. Por exemplo, um movimento do tipo 0, consiste em mover dois quadrados horizontalmente para direita e um quadrado verticalmente para cima (olhar a figura no quadro negro na aula). O movimento 2, por exemplo, consiste em mover dois quadrados verticalmente para cima e um quadrado horizontalmente para a esquerda. Movimentos horizontais à esquerda e verticais para cima são indicados por números negativos. Os oito movimentos podem ser descritos por dois vetores: um chamado `horizontal` e o outro `vertical`, da seguinte forma:

          horizontal[0]= 2
          horizontal[1]= 1
          horizontal[2]= -1
          horizontal[3]= -2
          horizontal[4]= -2
          horizontal[5]= -1
          horizontal[6]= 1
          horizontal[7]= 2
          vertical[0]= -1
          vertical[1]= -2
          vertical[2]= -2
          vertical[3]= -1
          vertical[4]= 1
          vertical[5]= 2
          vertical[6]= 2
          vertical[7]= 1
      

   3. Considere que temos duas variáveis `currentRow` e `currentColumn` que indiquem a linha e coluna da posição atual do cavalo no tabuleiro. Para fazer um movimento do tipo `moveNumber`, onde `moveNumber` está entre 0 e 7, seu programa usa as seguintes instruções:

        currentRow += vertical[moveNumber];
        currentColumn += horizontal[moveNumber];
      

   4. Mantenha um contador que varie de 1 a 64. Registre o maior contador em cada quadrado para onde o cavalo se mover. Lembre-se de testar cada movimento em potencial para verificar se o cavalo já visitou esse quadrado. E, naturalmente, teste cada movimento em potencial para garantir que o cavalo não saia do tabuleiro. Agora, escreva um programa para mover o cavalo pelo tabuleiro. Execute o programa. Quantos movimentos o cavalo fez?

   5. Data de entrega desta primeira parte do trabalho 1: (04/06/2012)

   6. DICA: Desenhe o problema em uma folha de papel e pense sobre ele antes de começar.