leiyahui

八皇后問題是編程人員需要解決的重要得問題

它可以用遞歸來解決，但是遞歸的效率并不太高，也可以用數據結構來解決，因為只需要記錄有還是沒有，所以說用二維數組就OK，數據結構不用太復雜。

另外可以這樣想，既然結果只是記錄有還是沒有，所以說不用二維數組，把數組改為一維數組，只用記錄是在哪一行，哪一列就OK。

如int a[8];

a[i]=3表示第i行的位置是在3

所以說這樣用一維數組就可以表示出位置。

代碼如下

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define INTABLE  -1
void Init(int* a ,int n)        //初始化
{
    int i;
    for (i = 0; i < n; i++)
    {
        a[i] = INTABLE;
    }
}
int IsValid(int* a, int row, int col)        //判斷第row行，第col列是否可以放皇后,行和列從0開始
{
    int i = 0;
    for (i = 0; i < row-1;i++)
    {
        if (a[i] == col || abs(i - row) == abs(a[i] - col))        //如果列沖突或者對角線沖突
        {
            return 0;
        }
    }
    return 1;
}
void print(int* a,int n)        //打印出正確的解
{
    int i;
    for (i = 0; i < n; i++)
    {
        printf("%d,%d\n", i, a[i]);
    }
}
void queue()        //隊列
{
    int a[8];
    Init(a,8);
    int i = 0;
    int j = 0;
    int m = 1;
    while (i < 8)
    {
        while (j < 8)
        {
            if (IsValid(a, i, j))
            {
                a[i] = j;
                j = 0;
                break;
            }
            else
            {
                j++;
            }
        }
        if (a[i] == INTABLE)        //如果說這一行沒有合適的位置
        {
            if (i == 0)        //回到第一行仍然沒有合適的位置，則說明所有的已經遍歷，退出該函數
            {
                break;
            }
            i--;
            j = a[i] + 1;
            a[i] = INTABLE;
            continue;
        }
        
        if (i == 7)        //說明已經遍歷到最后一行，找到了一個合適的解，打印出來
        {
            printf("%d", m);
            print(a, 8);        //打印出正確的解
            j = a[i] + 1;
            a[i] = INTABLE;
            m++;
            continue;

        }
        i++;

    }
}
int main()
{
    queue();　　　　//輸出所有數組
    getchar();
}

//未完待續，回頭再寫