前言

最近在學校數(shù)據(jù)結構與算法, 說實話第一次接觸這些東西, 有些地方學起來還是挺費腦子的! 其實好多都是建立在理解的基礎上, 當你理解了就好很多! 然后再自己去實踐! 完成那些經典算法的實現(xiàn)步驟! 可以更好地加深理解!
本篇文章相當于在學習是的學習筆記, 供以后復習使用! 當然若能幫助到遇到該問題的朋友, 也是非常榮幸的!
OZ8K, 正所謂光說不練, 凈是扯??......

問題

八皇后問題避消，是一個古老而著名的問題嗅回，即：在8×8格的國際象棋上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法瓮孙。 高斯認為有76種方案。1854年在柏林的象棋雜志上不同的作者發(fā)表了40種不同的解选脊，后來有人用圖論的方法解出92種結果杭抠。計算機發(fā)明后，有多種計算機語言可以解決此問題恳啥。

算法

本篇文章是用遞歸算法實現(xiàn)解決八皇后問題, 當然解決該問題也可以用回溯算法! 代碼有詳細注釋!

代碼

#include <stdio.h>

/*總共有多少種排列方法*/
int totalCount = 0;


// 檢查row行, col列 這個位置是否安全
int isSecurity(int row, int col, int chess[8][8]) {
    
    int j = 0, k = 0;

    int flag = 0;

    for (int i = 0; i < 8; ++i)
    {
        // 檢查在列上是否安全
        if (chess[i][col] != 0) {
            flag = 1;
            break;
        };
        
        // 檢查左上是否安全
        j = row - i;
        k = col - i;
        if ((j >= 0 && k >= 0)) if (chess[j][k] != 0) {
            flag = 1;
            break;
        };

        // 檢查右下是否安全
        j = row + i;
        k = col + i;
        if ((j < 8 && k < 8)) if (chess[j][k] != 0) {
            flag = 1;
            break;
        }

        // 檢查左下是否安全
        j = row + i;
        k = col - i;
        if ((j < 8 && k >= 0)) if (chess[j][k] != 0) {
            flag = 1;
            break;
        }
        

        // 檢查右上是否安全
        j = row - i;
        k = col + i;
        if ((j >= 0 && k < 8)) if (chess[j][k] != 0) {
            flag = 1;
            break;
        }
    }


    return !flag;
}

/*從第 row 行 開始, 總歸 n 列*/
void EightQueen(int row, int n, int chess[8][8])
{

    int chess2[8][8];

    for (int i = 0; i < 8; i++)
    {
        for (int j = 0; j < 8; j++)
        {
            chess2[i][j] = chess[i][j];
        }
    }

    // 先判斷結束條件
    if (row == 8)
    {
        printf("第 %d 種排列方法\n", totalCount + 1);

        // 輸出排列結構
        for (int i = 0; i < 8; i++)
        {
            for (int j = 0; j < 8; j++)
            {
                printf("%d ", chess[i][j]);
            }
            printf("\n");

        }
        printf("\n\n");
        totalCount ++;

    } else {
        // 不滿足結束條件, 則繼續(xù)排列
        for (int i = 0; i < 8; i++)
        {
            // 先判斷要插入的位置是否安全
            if (isSecurity(row, i, chess))
            {
                // 如果安全, 則插入
                for (int i = 0; i < 8; i++)
                {
                    // 先把該行的所有數(shù)據(jù)賦值為 0
                    chess2[row][i] = 0;
                }
                chess2[row][i] = 1;
                EightQueen(row + 1, n, chess2);
            }
        }
    }
}

int main(int argc, char const *argv[])
{
    int chess[8][8];

    for (int i = 0; i < 8; i++)
    {
        for (int j = 0; j < 8; j++)
        {
            chess[i][j] = 0;
        }
    }

    EightQueen(0, 8, chess);
    
    return 0;
}