Ir para conteúdo
Fórum Script Brasil
  • 0

Problema com função recursiva backtracking


FernandoG

Pergunta

Estou criando um código para resolver o problema do cavalo no xadrez, o questão é que cheguei em problema que não consigo debugar no eclipse para identificar o erro, se alguém poder me ajudar, o erro está na função recursiva... Acredito que seja alguma coisa boba, mas já tentei de tudo aqui e essa função não funciona.

#include <stdio.h>

#include <stdlib.h>

/*--------------------------------VARIAVEIS GLOBAIS-----------------------------*/

int aiX[] = { 2, 1, -1, -2, -2, -1, 1, 2 }; //movimentos "X" do cavalo

int aiY[] = { 1, 2, 2, 1, -1, -2, -2, -1 }; //movimentos "Y" do cavalo/

int nFileiras; //número colunas ou linhas do tabuleiro

int nCasas; //número de posiçoes/casas no tabuleiro nFileiras * nFileiras

int **T; // tabuleiro - versão alocando dinamicamente...

/*-------------------------------------------------------------------------------*/

//Aceitável se estiver dentro do tabuleiro e a casa ainda não tiver sido vizitada

int nValido(int x, int y) {

int resultado = (x >= 0 && x <= nCasas - 1);

resultado = resultado && (y >= 0 && y <= nCasas - 1);

resultado = resultado && (T[x][y] == 0);

return resultado;

}

int mCavalo(int posicaoAtual, int posicaoInicialX, int posicaoInicialY) {

// Verifica a quantidade de movimentos

int teste = (posicaoAtual > nCasas);

int k = 0;

int u, v;

while (!teste && k < 8) {

u = posicaoInicialX + aiX[k]; // 8 movimentos possíveis em volta do cavalo

v = posicaoInicialY + aiY[k];

if (nValido(u, v)) {

T[v] = posicaoAtual;

teste = mCavalo(posicaoAtual + 1, u, v); // tenta outro movimento

if (!teste) {

T[v] = 0; // sem sucesso. Descarta movimento

}

}

++k; // passa para o próximo movimento possível

}

return teste;

}

int mostraPasseio(int x, int y) {

int i, j;

int pronto = mCavalo(2, x, y);

T[x][y] = 1;

if (pronto) {

printf("Tabuleiro:\n");

for (i = 0; i < nFileiras; i++) {

for (j = 0; j < nFileiras; j++) {

printf("%03d ", T[j]);

}

printf("\n");

}

printf("Fim do Tabuleiro\n");

} else {

printf("Não há passeio possível");

}

return 1;

}

int main(int argc, char *argv[]) {

int i;

if (argc != 2) /*tem que utilizar assim: passeio (5>n<20) */

{

printf("Utilizacao: passeio numero (numero de fileiras entre 5 e 20)");

return -1;

}

nFileiras = atoi(argv[1]);

if (nFileiras < 5 || nFileiras > 20) {

printf(

"Numero errado... Utilizacao: passeio numero (fileiras entre 5 e 20 )");

return -1;

}

nCasas = nFileiras * nFileiras;

T = (int **) malloc(sizeof(int) * nFileiras); // aloca memoria

if (!T) {

printf("Erro alocando memória...");

return -1;

}

for (i = 0; i < nFileiras; i++) //para o tabuleiro

{

T = (int *) malloc(sizeof(int) * nFileiras);

if (!T) {

printf("Erro alocando memória...");

return -1;

}

}

mostraPasseio(0, 0);

return 1;

}

Link para o comentário
Compartilhar em outros sites

1 resposta a esta questão

Posts Recomendados

  • 0

int mCavalo(int posicaoAtual, int posicaoInicialX, int posicaoInicialY) {

// Verifica a quantidade de movimentos

int teste = (posicaoAtual > nCasas);

int k = 0;

int u, v;

while (!teste && k < 8) {

u = posicaoInicialX + aiX[k]; // 8 movimentos possíveis em volta do cavalo

v = posicaoInicialY + aiY[k];

if (nValido(u, v)) {

T[v] = posicaoAtual;

teste = mCavalo(posicaoAtual + 1, u, v); // tenta outro movimento

if (!teste) {

T[v] = 0; // sem sucesso. Descarta movimento

}

}

++k; // passa para o próximo movimento possível

}

return teste;

}

Pelo que vi o problema está no valor que ele está recebendo na variável u, fiz um printf pra ver esses valor mais não sai nada de anormal... Aguem tem ideia do que pode estar atrapalhando o funcionamento dessa função?

Link para o comentário
Compartilhar em outros sites

Participe da discussão

Você pode postar agora e se registrar depois. Se você já tem uma conta, acesse agora para postar com sua conta.

Visitante
Responder esta pergunta...

×   Você colou conteúdo com formatação.   Remover formatação

  Apenas 75 emoticons são permitidos.

×   Seu link foi incorporado automaticamente.   Exibir como um link em vez disso

×   Seu conteúdo anterior foi restaurado.   Limpar Editor

×   Você não pode colar imagens diretamente. Carregar ou inserir imagens do URL.



  • Estatísticas dos Fóruns

    • Tópicos
      152k
    • Posts
      651,8k
×
×
  • Criar Novo...