C++——算法 回溯 八皇後問題

#include <iostream>
using namespace std;

bool isOk(int c[], int row);                        // 判斷能否在第row行第c[row]列插入一個皇後
void queen(int row, int c[], int n, int& total);    // 回溯核心部分

int main()
{
    int n;  // 皇後的數量
    cout << "enter the number of queen:\n";
    cin >> n;
    int* c = new int[n];    // 記錄皇後的行列位置，i為行j為列，如c[i]=j表示第i行的第j列 
    int total = 0;          // 方案種數
    queen(0, c, n, total);
    cout << "total = " << total;
    return 0;
}

void queen(int row, int c[], int n, int& total)
{
    if (row == n)   // 當row==n的時，擺放完畢，輸出，記數
    {
        for (int i = 0; i < n; i++)
            cout << c[i] << " ";
        cout <<"\n";
        total++;
　　　　 return;　　
    }
    // 皇後還未擺放完，則執行下面程式//周遊所有列，找到第row行應該放在第幾列
    for (int col = 0; col < n; col++)   
    {
        c[row] = col;
        // 如果可以放在row行col列則繼續擺放下一行
        if (isOk(c, row))  queen(row+1, c, n, total);
        // 如果不能放在row行col列，則目前分支的解被剪枝，col++繼續循環下一分枝
    }
    // 如果循環了所有的列都不能擺放，表示該行的所有解分枝都被剪去，則會回溯到前一層函數改變上一行皇後的擺放位置
}

bool isOk(int c[], int row)
{
    for (int i = 0; i < row; i++)
    {   //  第row行皇後不能和任意之前的皇後在同一列或 \方向或 / 方向
        //  \斜線上的元素差相等，因為通項為(i-x,j-x);  /斜線上的元素和相等，國為通項為(i-x,j+x)
        if (c[i] == c[row] || c[row]-row == c[i]-i || c[row]+row == c[i]+i)
            return false;
    }
    return true;
}