八皇后（回溯法）

題目描述

在8×8格的國際象棋上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處於同一行、同一列或同一斜線上，問有多少種擺法！

設計思路

皇后位置

用一維數組表示，數組下標是行，元素是列

int place[8] = { 0 };

衝突判斷

flag保存哪一列已經存在皇后

bool flag[8] = { 1, 1, 1, 1, 1, 1, 1, 1 };

d1記錄皇后的主對角線衝突

n - col + 7的範圍是0~14對應d1[15]

bool d1[15] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };

 

d2記錄皇后的次對角線衝突

d2 = n + col的範圍是0~14對應d2[15]

bool d2[15] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1  };

八皇后核心

void QueenVIII(int n)         //n是行數
{
    for (int i = 0; i < 8; ++i)    // 每個皇后有8中可能的列 
    {
        if ((flag[i] && d1[n - i + 7]) && d2[n + i])    // 判斷第n行第i列的位置是否危險
        {
            place[n] = i;        // 在第n行第i列擺放皇后 
            flag[i] = 0;        // 記錄第i列已經有皇后了 
            d1[n - i + 7] = 0;    // 記錄這條主對角線是危險的 
            d2[n + i] = 0;        // 記錄這條次對角線是危險的

            if (n < 7 )            // 判斷八個皇后放完了沒有 
            {
                QueenVIII(n + 1);  //沒放夠就繼續遞歸放 
            }
            else
            {
                output();        //放夠八個皇后就輸出
            }
            // 回溯（退回去看看有沒有新方法） 
                flag[i] = 1;
                d1[n - i + 7] = 1;
                d2[n + i] = 1;
        }
    }
}

完整程式碼

# include <stdio.h>

// 全局變數
int place[8] = { 0 };    // 保存皇后的位置，下標為行，儲存的數據為列。
bool flag[8] = { 1, 1, 1, 1, 1, 1, 1, 1 };    // 用來保存哪一列已經存在皇后 
bool d1[15] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };    // 從左上到右下的對角線為上對角線，每條上對角線上的行和列的差是一樣的。
bool d2[15] = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1  };    // 從左下到右下的對角線為下對角線，每條下對角線上的行和列的和是一樣的。
int key = 0;                    // 統計解的數量

// 函數聲明
void QueenVIII(int);            // 八皇后問題
void output(void);                // 輸出

// 主函數
int main(void)
{
    //output();
    QueenVIII(0);

    return 0;
}
void QueenVIII(int n)
{
    for (int i = 0; i < 8; ++i)    // 每個皇后有8中可能的列 
    {
        if ((flag[i] && d1[n - i + 7]) && d2[n + i])    // 判斷第n行第i列的位置是否危險
        {
            place[n] = i;        // 在第n行第i列擺放皇后 
            flag[i] = 0;        // 記錄第i列已經有皇后了 
            d1[n - i + 7] = 0;    // 記錄這條上對角線是危險的 
            d2[n + i] = 0;        // 記錄這條下對角線是危險的

            if (n < 7 )            // 判斷八個皇后放完了沒有 
            {
                QueenVIII(n + 1); //沒放夠就繼續遞歸放 
            }
            else
            {
                output();        //放夠八個皇后就輸出
            }
            // 回溯（退回去看看有沒有新方法） 
                flag[i] = 1;
                d1[n - i + 7] = 1;
                d2[n + i] = 1;
        }
    }
}

void output(void)
{
    printf("第%d種解法：\n", ++key);
    for (int n = 0; n < 8; ++n)
    {
        for (int i = 0; i < 8; ++i)
        {
            if (place[n] == i)
            {
                printf("1 ");
            }
            else
            {
                printf("0 ");
            }
        }
        printf("\n");
    }
    printf("\n");
}

 

Tags:

VirMach 便宜 VPS