1

O problema do passeio do cavalo consiste em colocar o cavalo no tabuleiro vazio e, seguindo as regras do jogo, fazê-lo passar por todas as casas exatamente uma vez em movimentos consecutivos.

Ou seja, dado um tabuleiro de tamanho n, e a posição inicial do cavalo StartX, StartY, o algoritmo deve mostrar na tela uma matriz de tamanho NxN informando em que movimento o cavalo passou em suas casas. Se dada a posição inicial e o cavalo não encontrar um meio de andar por todas as casas 1 única vez então mostra na tela que o problema não tem solução.

No meu programa, ao digitar valores maiores que 8 para o tabuleiro 8x8, e se a posição do cavalo for diferente de 1 para a linha ou coluna o programa simplesmente entra em loop infinito, não sei o motivo:

#include<stdio.h>
#define MAX 10

void imprimir(int n, int M[MAX][MAX]) 
{
    int x, y;
    for (x = 0; x < n; x++) {
        for (y = 0; y < n; y++)
            printf(" %3d ", M[x][y]);
        printf("\n");
    }   
}

int passeio(int n, int x, int y, int pos, int M[MAX][MAX], int xMove[], int yMove[]) 
{
    int k, nextX, nextY;
    if (pos == n*n) return 1;
    for (k = 0; k < 8; k++) {
        nextX = x + xMove[k];
        nextY = y + yMove[k];

        if ((nextX >= 0) && (nextX < n) && (nextY >= 0) && (nextY < n) &&
            (M[nextX][nextY] == 0)) {
            M[nextX][nextY] = pos + 1;
        if (passeio(n, nextX, nextY, pos + 1, M, xMove, yMove))
            return 1;
        else
            M[nextX][nextY] = 0; /* libera a posicao do tabuleiro */
        }
    }
    return 0;
}

int main() 
{
    int M[MAX][MAX], x, y, n, startX, startY;
    int xMove[8] = {2, 1, -1, -2, -2, -1,  1,  2};
    int yMove[8] = {1, 2,  2,  1, -1, -2, -2, -1};
    printf("Entre com o tamanho do tabuleiro: ");
    scanf("%d", &n);
    printf("Entre com a linha inicial do cavalo: ");
    scanf("%d", &startX);
    printf("Entre com a coluna inicial do cavalo: ");
    scanf("%d", &startY);
    for (x = 0; x < n; x++)
        for (y = 0; y < n; y++)
            M[x][y] = 0;
        M[startX - 1][startY - 1] = 1;
        if (passeio(n, startX - 1, startY - 1, 1, M, xMove, yMove) == 0)
            printf("Nao existe solucao.\n");
        else
            imprimir(n, M);
        return 0;
}

1 Resposta 1

-2

Existem três métodos para resolver este problema: o backtracking que é o que estás a utilizar, força bruta e a regra de Warnsdorff.

O teu programa está correto mas o algoritmo demora muito tempo para tabuleiros maiores.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .