1.基本原理

八皇后问题是一道趣味经典的算法问题。详细描述为：在8*8棋盘内使8个皇后棋子无冲突地摆放。在国际象棋中，皇后的移动方式为横竖交叉的，所以在一个皇后的水平竖直以及45度方向上都不能出现皇后。

2.代码实现

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

typedef struct {
        char x;
        char y;
} empress;

int check_flag(int *flag, int n)
{
        int s = -1;
        int i = 0;

        for(i=n-1; i>0; i--)
        {
                if(flag[i] == 0)
                        return i;
        }

        return -1;
}

int check_conflict(empress x, empress *q, int n)
{
        int u = 0;
        int e = 0;
        int i = 0;

        for(i=0; i<n; i++)
        {
                u = q[i].x - x.x;
                e = q[i].y - x.y;

                if(u == 0 || e == 0 || u == e || u + e == 0)
                {
                        return 1;
                }
        }

        return 0;
}

void add_empress(empress *q, empress x, int u)
{
        q[u].x = x.x;
        q[u].y = x.y;
}

void print_empress(empress *q, int n)
{
        int i = 0;

        for(i=0; i<n; i++)
        {
                printf("x=%d, y=%d\n", q[i].x, q[i].y);
        }
}

int main()
{
        empress s[100][8];
        empress q[8];
        empress a;
        int flag[8];
        int n = 8;
        int m = 0;
        int c = 0;
        int d = 0;
        int j = 0;

        memset(flag, 0x00, sizeof(flag));
        memset(s, 0x00, sizeof(s));
        memset(q, 0x00, sizeof(q));

        while(1)
        {
                a.x = m;
                a.y = j;

                /*d = check_flag(flag, n);
                //printf("d=%d\n", d);

                if(d == -1)
                        break;

                if(q[d].y == 7)
                        flag[d] = 1;*/

                if(j >= n)
                {
                        m--;
                        j = q[m].y + 1;
                        //if(c> 92) break;

                        continue;
                }

                if(check_conflict(a, q, m))
                {
                        j++;
                        continue;
                }

                add_empress(q, a, m);

                j = 0;

                m++;

                if(m == n)
                {
                        if(memcmp(s[0], q, sizeof(q)) == 0)
                        {
                                break;
                        }

                        memcpy(s[c], q, sizeof(q));
                        j = q[m-1].y + 1;
                        c++;
                        m--;
                }
        }

        for(j=0; j<c; j++)
        {
                print_empress(s[j], n);
                printf("\n");
        }

        printf("num=%d\n", c);

        return 0;
}

3.编译源码

$ gcc -o example example.c

4.运行程序

$ ./example