Jump to content
Fórum Script Brasil
  • 0

Problema com função recursiva backtracking


FernandoG

Question

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 to post
Share on other sites

1 answer to this question

Recommended Posts

  • 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 to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Answer this question...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.



  • Forum Statistics

    • Total Topics
      148854
    • Total Posts
      644872
×
×
  • Create New...