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.
Backtrack sem recursão
em Tutoriais & Dicas - C, C++
Postado
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.