OpenJ Bailian - 2754 八皇後 —— 回溯思想+遞歸程式設計

一、題面

二、題解

首先畫出棋盤觀察一下會發現

皇後互相沖突的情況有兩種情形（假設我們不放在同一行）

①兩個皇後位于同一列        ②兩個皇後的行差絕對值等于列差絕對值，即它們在斜線上沖突

同時，我們可以用一維數組簡化遞歸過程，row[i] = j 表示第i行的皇後在第j列上

思路了解後，利用遞歸+回溯思想求解即可

三、實作代碼

#include<cmath>
#include<iostream>

using namespace std;
 
int q[92][8], row[8], num = 0;
void queen(int i)
{   
    int j, k; 
    if(i == 8){
        for(j = 0; j < 8; j++)
            q[num][j] = row[j];
        num++;
        return;
    }
 
    for(int j = 1; j <= 8; j++){
        for(k = 0; k < i; k++)
            if(row[k] == j || abs(k-i) == abs(row[k]-j)) break; //判斷是否沖突
        if(k == i){
            row[k] = j; //放置新皇後
            queen(i+1);
        }
    }
}

int main()
{
    int n, i, b, j;
    queen(0);
    cin >> n;
    for(i = 0; i < n; i++){
        cin>>b;
        for(int j = 0; j < 8; j++)
            cout << q[b-1][j];
        cout << endl;
    }
    return 0;
}