N皇后求解。萬萬沒想到，只用一個一維陣列就搞定了。還體現了回溯。

一、啥是N皇后？先從四皇后入手

給定一個4x4的棋盤，要在棋盤上放置4個皇后，他們的位置有這樣的要求，每一列，每一行，每一對角線都能有一個皇后，

你可能會對這個對角線有疑惑，其實就是每一個小正方形的對角線都不能有皇后，可以看圖理解一下，

二、解題思想

設皇后k擺放在x[k]的位置上，注意陣列下標從0開始，0<=k<n且0<=x[k]<n，

這里用陣列下標以及對應的值，模擬了一個棋盤的行和列，這是比較奇妙的地方，不需要二維陣列了，

演算法:setQueen(n)
輸入:皇后的個數n
輸出:n皇后問題的解x[n]，解是一個陣列，

1. 初始化 k=0 初始化解向量 x[n] ={-1}
2. 重復執行下面操作，擺放皇后k
   2.1. 把皇后k擺放在下一列的位置，即 x[k]++
   2.2. 如果皇后k擺放在x[k]位置發生沖突，則 x[k]++ 試探下一列，直到不沖突或 x[k] 出界
   2.3. 如果 x[k] 沒出界并且所有皇后都擺放完畢，則輸出一個解
   2.4. 如果 x[k] 沒出界但有皇后尚未擺放，則 k++ ，轉2.1擺放下一行的皇后
   2.5. 如果 x[k] 出界，則回溯，x[k]=-1 , k-- ,轉2.1重新擺放上一行皇后

三、代碼實作

#include <stdio.h>
#include <cstring>
#include <math.h>
class Queen
{
private:
    int Place(int k);
    int *x;
    int num;

public:
    Queen(int n);
    void setQueen();
    void PrintQueen();
    ~Queen();
};

Queen::Queen(int n)
{
    x = new int[n];
    memset(x, -1, n); //-1表示尚未擺放皇后
    num = n;
}

Queen::~Queen()
{
    delete[] x;
}

void Queen::setQueen()
{
    int k = 0, count = 0;
    while (k >= 0) //擺放皇后k，注意0<=k<n
    {
        x[k]++;                             //在下一列擺放皇后k
        while (x[k] < num && Place(k) == 1) //發生沖突
            x[k]++;                         //皇后k試探下一列，超出num將會跳出
        if (x[k] < num && k == num - 1)     //得到一個解
        {
            printf("第%d個解:", ++count);
            PrintQueen();
        }
        else if (x[k] < num && k < num - 1) //尚有皇后未擺放
            k = k + 1;                      //準備擺放下一個皇后
        else
            x[k--] = -1; //重置x[k],回溯，重新擺放皇后k
    }
}

//放置皇后，在一個位置上放置皇后，然后將結果回傳，
int Queen::Place(int k) //考察皇后k放置在x[k]列是否發生沖突
{
    for (int i = 0; i < k; i++)
        if (x[i] == x[k] || abs(i - k) == abs(x[i] - x[k])) //根據對角線原則
            return 1;                                       //沖突回傳1
    return 0;                                               //不沖突回傳0
}

//列印皇后的解
void Queen::PrintQueen()
{
    for (int i = 0; i < num; i++)
        printf("%d\t", x[i] + 1);
    printf("\n");
}

int main(void)
{
    int n;
    printf("請輸入皇后個數(n>=4):");
    scanf("%d", &n);
    Queen Q(n);
    Q.setQueen();
    return 0;
}

四、總結

這里面的代碼是來自「資料結構C++王紅梅版」

也知道了很多新穎的點

1. 代碼中就很好利用了陣列下標作為形象上理解的一行
2. 如何判定兩個皇后是不是在同一對角線，也很好地利用了正方形的特性，皇后所在位置的行差與列差是否相等，
3. 還有就是SetQueen()的邏輯結構，先用while回圈擺放皇后，然后根據這個結果來判斷是已經求解到了，還是該下一行或者回溯到上一行，

這里放一波我之前邏輯結構很混亂的代碼(就可以求解到正確答案，但是輸出的時機很難控制)

#include <stdio.h>
#include <string.h>
#include <math.h>
#define n 4 //設定n皇后的數目
int *x = new int[n];

void printA();
int place(int k);
int main(void)
{

    memset(x, -1, sizeof(int) * n);
    int k = 0;
    while (k > -1)
    {
        x[k]++;
        if (k < n && place(k) == 1) //不沖突,開始放置下一行   如果已經是最后一行呢？
        {
            if (k < n - 1)
                k++;
        }
        else if (k < n || x[k] == n) //要回溯到上一行
        {
            x[k] = -1;
            k--;
        }
        else if (k == n && x[k] < n)
        {
            //得到一組解答
            printA();
        }
    }

    return 0;
}

//在第k行放置皇后，回傳1代表沖突，回傳0代表不沖突
int place(int k)
{
    for (; x[k] < n; x[k]++)
    {
        bool flag = true;
        for (int i = 0; i < k; i++)
        {
            if (x[k] == x[i] || (abs(k - i) == abs(x[k] - x[i])))
            {
                flag = false;
                break;
            }
        }
        if (flag)
            return 1;
    }
    return 0;
}

void printA()
{
    for (int i = 0; i < n; i++)
    {
        printf("%d  ", x[i] + 1);
    }
    printf("\n");
}

標籤：其他

上一篇：演算法學習-整數反轉

下一篇：騰訊筆試題20210321