八皇后

八皇后

1、非递归

#include <stdio.h>
#include <string.h>

#define QUEENS 8

int queen[QUEENS];
int cnt = 0;

void output();

int main()
{
    int col = 0, i, j,tmp;
    int flag;
    
    for(;;)
    {
        if(0 == col && QUEENS == queen[col])
        {
            break;
        }
        if(queen[col] < QUEENS)
        {
            queen[col] ++;
        }
        else
        {
            queen[col] = 0;
            col --;
            continue;
        }
        flag = 1;
        for(i = 0; i < col; i ++)
        {
            if(queen[i] == queen[col])
            {
                flag = 0;
            }
        }
        
        for(i = col - 1; i >= 0; i --)
        {
            tmp = col - i;
            if((queen[i] == queen[col] - tmp) || (queen[i] == queen[col] + tmp))
            {
                flag = 0;
            }
        }
        
        if(flag)
        {
            if(col < QUEENS - 1)
            {
                col ++;
            }
            else
            {
                cnt ++;
                output();
                queen[col] = 0;
                col --;
            }
        }
    }
    return 0;
}

void output()
{
    int n;
    printf("%d: ", cnt);
    for(n = 0; n < QUEENS; n ++)
    {
        printf("%d ", queen[n]);
    }
    printf("\n");
}

2、递归 + 检测冲突优化

#include <stdio.h>
#include <string.h>

#define QUEENS 8

int queen[QUEENS];
int flag_row[QUEENS]; //行占领标志
int flag_x[(QUEENS - 1) * 2 + 1]; //左上-右下对角线占领标志
int flag_y[(QUEENS - 1) * 2 + 1]; //右上-左下对角线占领标志
int cnt = 0;

void put(int);
void output();

int main()
{
    put(0);
    return 0;
}

void put(int col)
{
    int n;
    
    if(QUEENS == col)
    {
        cnt ++;
        output();
        return;
    }
    
    for(n = 0; n < QUEENS; n ++)
    {
        if(!(flag_row[n]) && !(flag_x[col - n + QUEENS - 1]) && !(flag_y[col + n]))
        {
            flag_row[n] = 1;
            flag_x[col - n + QUEENS - 1] = 1;
            flag_y[col + n] = 1;
            queen[col] = n + 1;
            put(col + 1);
            flag_row[n] = 0;
            flag_x[col - n + QUEENS - 1] = 0;
            flag_y[col + n] = 0;
        }
    }
}

void output()
{
    int n;
    printf("%d: ", cnt);
    for(n = 0; n < QUEENS; n ++)
    {
        printf("%d ", queen[n]);
    }
    printf("\n");
}