i644 - 列舉八皇后問題所有解

🔗 前往 ZeroJudge 原題

題目描述

題目要求列舉所有 8x8 棋盤上放置 8 個皇后，且皇后之間互不攻擊的解法。輸出解法的數量，以及每個解法中皇后所在列的順序。

解題思路

本題採用 backtracking (回溯) 演算法來解決。jd 函數用於判斷在當前列放置皇后是否會與之前放置的皇后衝突。dfs 函數遞迴地嘗試在每一列放置皇后，如果找到一個合法的放置位置，則繼續遞迴到下一列。當所有列都放置了皇后時，輸出一個解法。

a[i] 儲存第 i 列皇后所在的行。ct 記錄解法的數量。jd(x, y) 檢查在第 x 列放置皇后在第 y 行是否安全，即是否與之前放置的皇后衝突。dfs(x, y) 遞迴函數，嘗試在第 x 列放置皇后，如果找到安全的位置，則繼續遞迴到下一列。

複雜度分析

• 時間複雜度: O(8^8)。在最壞的情況下，需要嘗試所有可能的皇后放置位置。
• 空間複雜度: O(8)。主要用於儲存當前解的狀態，以及遞迴調用的堆疊空間。

程式碼

#include <iostream>
using namespace std;
int a[8],ct;
bool jd(int x,int y){
	for(int i=0;i<x;++i)
		if(a[i]==y||abs(i-x)==abs(a[i]-y))return 0;
	return 1;
}
void dfs(int x,int y){
	if(x==8){
		cout << ++ct << ": ";
		for(int i=0;i<8;++i)
			cout << a[i]+1;
		cout << "\n";
		return;
	}
	for(int i=0;i<8;++i)
		if(jd(x,i))
			dfs(x+1,a[x]=i);
}
int main(){
	for(int i=0;i<8;++i)
		dfs(1,a[0]=i);
}