Backtrack sem recursão

[jotave97]

Preciso criar um algoritmo em C para resolver o problema das N Rainhas, porém estão impostas bastantes limitações. Uma delas é não poder usar recursão. Sendo assim, preciso reformular minha função de teste:

int teste(int tab[MAX][MAX], int N, int col, int b, int c, int r, int v){

int i, j;

/* caso os testes sejam executados até que col == N, uma solução foi encontrada */

if(col == N){

    if(v == 1){

    imprimir(tab, N, b, c, r);

    }

    sol ++;

/* caso seja encontrada uma solução, as posições são computadas no mapa de frequencias */

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

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

            mapafreq[i][j] = mapafreq[i][j] + tab[i][j];

    }

}

    return 1;

}

/* realiza os testes das posições */

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

    if(seguro(tab, N, i, col, b, c, r) == 1){

        tab[i][col] = 1;

        teste(tab, N, col + 1, b, c, r, v);

    }

/* backtrack (remove a rainha) */

    tab[i][col] = 0;

}

return 0;

}

*ignorar as variáveis b, c, r, v, elas não são interferem no problema.

[erinwoody]

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

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

            mapafreq[i][j] = mapafreq[i][j] + tab[i][j];

slope game

[line alice]

Aqui está um comentário que se adequa ao conteúdo do seu código:

c

/* Função teste: verifica a colocação das rainhas no tabuleiro e conta soluções sem usar recursão. */

Esse comentário resume a função e destaca a restrição de não utilizar recursão, que é uma parte importante do seu desafio. Se precisar de mais ajuda com o algoritmo ou com outro aspecto, sinta-se à vontade para perguntar.

 

slope game

[Emma Roberts]

int main() {
    int N = 8; // Exemplo para 8 rainhas
    teste_iterativo(N);
    printf("Soluções encontradas: %d\n", sol);
    return 0;
}
 

Survival race

[morven anselm]

Você tem o problema das N-Rainhas e precisa resolver sem recursão, ou seja, transformar a sua função teste em um algoritmo iterativo.

Hoje o seu código usa backtracking recursivo: chama teste(..., col+1, ...) e volta removendo a rainha. Para eliminar a recursão, você pode simular a pilha de chamadas manualmente, ou usar um laço que avance/retorne colunas conforme necessário.

Aqui vai uma ideia de como reescrever de forma iterativa:  melon playground

 

#include <stdio.h> #define MAX 20 int sol = 0; int mapafreq[MAX][MAX]; int seguro(int tab[MAX][MAX], int N, int linha, int col) { int i, j; // verifica linha à esquerda for (i = 0; i < col; i++) if (tab[linha][i]) return 0; // diagonal superior esquerda for (i = linha, j = col; i >= 0 && j >= 0; i--, j--) if (tab[i][j]) return 0; // diagonal inferior esquerda for (i = linha, j = col; j >= 0 && i < N; i++, j--) if (tab[i][j]) return 0; return 1; } void imprimir(int tab[MAX][MAX], int N) { int i, j; printf("Solução %d:\n", sol+1); for (i = 0; i < N; i++) { for (j = 0; j < N; j++) { printf("%c ", tab[i][j] ? 'Q' : '.'); } printf("\n"); } printf("\n");