回溯算法之n皇后问题

queen[i]表示第i个皇后放在棋盘第i行的第queen[i]列上.

1.递归回溯：

#include <stdio.h>
#include <stdlib.h>

#define MAXQUEENS 100
int queen[MAXQUEENS + 1];
int n, num;

void backtrack(int t);
int safe(int k);
int main(int argc, char **argv)
{
        printf("Input queen numbers:");
        scanf("%d", &n);
        getchar();

        backtrack(1);

        return 0;
}

void backtrack(int t)
{
        int i;

        if(t > n){//found

                num++;
                printf("Output choice %d: \n", num);
                for(i = 1; i <= n; i++){
                        printf("%d ", queen[i]);
                }
                printf("\n");
        }
        else{
                for(i = 1; i <= n; i++){
                        queen[t] = i;
                        if(safe(t)){
                                backtrack(t + 1);
                        }
                }
        }
}

int safe(int k)
{
        int j, flag = 0;

        for(j = 1; j < k; j++){
                flag = (queen[k] == queen[j]) || ((j - queen[j]) == (k - queen[k])) || \
                        ((j + queen[j]) == (k + queen[k]));
                if(flag){
                        return 0;
                }
        }

        return 1;//safe

}


2.迭代回溯：

#include <stdio.h>
#include <stdlib.h>

#define MAXQUEENS 100
int queen[MAXQUEENS + 1];
int n, num;

int safe(int k);
int main(int argc, char argv)
{
        int i, k = 1;
      
        printf("Input queen numbers:");
        scanf("%d", &n);
        getchar();

        while(k > 0){
                queen[k] += 1;
                while((queen[k] <= n) && (!safe(k))){
                        queen[k] += 1;
                }
                if(queen[k] <= n){
                        if(k == n){
                                num++;
                                printf("Output choice %d: \n", num);
                                for(i = 1; i <= n; i++){
                                        printf("%d ", queen[i]);
                                }
                                printf("\n");
                        }
                        else{
                                k++;
                                queen[k] = 0;
                        }
                }
                else{
                        k--;
                }
        }

        return 0;
}

int safe(int k)
{
        int j, flag = 0;

        for(j = 1; j < k; j++){
                flag = (queen[k] == queen[j]) || ((j - queen[j]) == (k - queen[k])) || \
                        ((j + queen[j]) == (k + queen[k]));
                if(flag){
                        return 0;
                }
        }

        return 1;//safe

}